Allocating Goods on a Graph to Eliminate Envy
Chevaleyre, Yann; Endriss, Ulle; Maudet, Nicolas (2007), Allocating Goods on a Graph to Eliminate Envy, in Holte, Robert C.; Howe, Adele, Proceedings of the 22nd Conference on Artificial Intelligence, AAAI Press, p. 700–705
TypeCommunication / Conférence
Conference title22nd Conference on Artificial Intelligence (AAAI-2007)
Book titleProceedings of the 22nd Conference on Artificial Intelligence
Book authorHolte, Robert C.; Howe, Adele
MetadataShow full item record
Abstract (EN)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 / Keywordsenvy-freeness; allocation of resources; negotiation; Multiagent systems
Showing items related by title and author.