Allocating Goods on a Graph to Eliminate Envy

Yann Chevaleyre, Ulle Endriss, Nicolas Maudet

We introduce a distributed negotiation framework for multiagent resource allocation where interactions between agents are limited by a graph defining a negotiation topology. A group of agents may only contract a deal if that group is fully connected according to the negotiation topology. An important criterion for assessing the quality of an allocation of resources, in terms of fairness, is envy-freeness: an agent is said to envy another agent if it would prefer to swap places with that other agent. We analyse under what circumstances a sequence of deals respecting the negotiation topology may be expected to converge to a state where no agent envies any of the agents it is directly connected to. We also analyse the computational complexity of a related decision problem, namely the problem of checking whether a given negotiation state admits any deal that would both be beneficial to every agent involved and reduce envy in the agent society.

Subjects: 7. Distributed AI; 7.1 Multi-Agent Systems

Submitted: Apr 20, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.