Journal Title
Title of Journal: Auton Agent MultiAgent Syst
|
Abbravation: Autonomous Agents and Multi-Agent Systems
|
|
|
|
|
|
|
|
Authors: Arnon Netzer Amnon Meisels Roie Zivan
Publish Date: 2015/02/27
Volume: 30, Issue: 2, Pages: 364-402
Abstract
Minimizing envy in distributed discrete resource or task allocation is an unusual distributed optimization challenge since the quality of the allocation for each of the agents is dependent not only on its own allocation but on the allocation of others as well Thus in order to perform distributed search for allocations with minimal envy there is a need to design innovative algorithms that can cope with the challenging constraint structure of an envy minimization problem Distributed methods for minimizing envy among agents in indivisible resource allocation problems are presented First Distributed Envy Minimization Problems DEMP are formulated as Distributed Constraint Reasoning problems When the DEMPs are large and cannot be solved by a complete search an incomplete local search algorithm is presented Each transfer of a good from one agent to another involves the change of state of more than one agent Thus a minimizing envy local search algorithm must build upon actions transfers that include multiple agents Since DEMPs are particularly susceptible to local minima during local search the paper proposes an algorithm that alternates between two different hill climbing search phases The first phase uses onetransfer steps while the other exploits envy cycle elimination steps An algorithm that minimizes envy while preserving efficiency is proposed The proposed algorithm finds a Pareto optimal allocation with low envy In the context of resource allocation problems a Pareto optimal solution is particularly desirable since it presents a stable solution The proposed algorithm first finds a divisible Pareto optimal envyfree allocation using a Fisher market equilibrium This allocation is transferred into an indivisible allocation of goods while maintaining the Pareto optimal characteristic of the allocation and a low envy level among agents
Keywords:
.
|
Other Papers In This Journal:
|