Distributed Local Search for Minimizing Envy
Arnon Netzer, Amnon Meisels · 2013 IEEE/WIC/ACM International Joint Conferences on Web Intelligence (WI) and Intelligent Agent Technologies (IAT) · 2013
The allocation of indivisible resources to multiple agents typically generate envy among the agents. An Envy Free allocation may not exist in general and one can search for a minimal envy allocation. The search problem of minimizing envy for indivisible resource allocation is presented and a negotiation based transfer algorithm for solving it is proposed. The proposed algorithm performs a distributed any time local search for minimal envy solutions. The algorithm is composed of two phases. One phase performs hill climbing by the transfer of a single good among agents. The other phase of search uses elimination of open-end envy cycles, thereby utilizing the transfer of whole bundles. An extensive experimental evaluation of the proposed algorithm demonstrates the advantage of using the combined two phase algorithm.