
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
View/ Open
Type
Communication / ConférenceDate
2007Conference title
22nd Conference on Artificial Intelligence (AAAI-2007)Conference date
2007-07Conference city
VancouverConference country
CanadaBook title
Proceedings of the 22nd Conference on Artificial IntelligenceBook author
Holte, Robert C.; Howe, AdelePublisher
AAAI Press
ISBN
978-1-57735-323-2
Pages
700–705
Metadata
Show full item recordAbstract (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 / Keywords
envy-freeness; allocation of resources; negotiation; Multiagent systemsRelated items
Showing items related by title and author.
-
Chevaleyre, Yann; Endriss, Ulle; Estivie, Sylvia; Maudet, Nicolas (2007) Communication / Conférence
-
Chevaleyre, Yann; Endriss, Ulle; Maudet, Nicolas (2008) Communication / Conférence
-
Chevaleyre, Yann; Endriss, Ulle; Maudet, Nicolas (2005) Communication / Conférence
-
Chevaleyre, Yann; Endriss, Ulle; Lang, Jérôme; Maudet, Nicolas (2007) Communication / Conférence
-
Chevaleyre, Yann; Endriss, Ulle; Lang, Jérôme; Maudet, Nicolas (2008) Article accepté pour publication ou publié