Multiagent resource allocation with sharable items
Airiau, Stéphane; Endriss, Ulle (2014), Multiagent resource allocation with sharable items, Autonomous Agents and Multi-Agent Systems, 28, 6, p. 956-985. 10.1007/s10458-013-9245-x
Type
Article accepté pour publication ou publiéDate
2014Nom de la revue
Autonomous Agents and Multi-Agent SystemsVolume
28Numéro
6Éditeur
Springer
Pages
956-985
Identifiant publication
Métadonnées
Afficher la notice complèteAuteur(s)
Airiau, Stéphane
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Endriss, Ulle
Résumé (EN)
We study a particular multiagent resource allocation problem with indivisible, but sharable resources. In our model, the utility of an agent for using a bundle of resources is the difference between the value the agent would assign to that bundle in isolation and a congestion cost that depends on the number of agents she has to share each of the resources in her bundle with. The valuation function determining the value and the delay function determining the congestion cost can be agent-dependent. When the agents that share a resource also share control over that resource, then the current users of a resource will require some compensation when a new agent wants to join them using the resource. For this scenario of shared control, we study the existence of distributed negotiation protocols that lead to a social optimum. Depending on constraints on the valuation functions (mainly modularity), on the delay functions (such as convexity), and on the structural complexity of the deals between agents, we prove either the existence of a sequences of deals leading to a social optimum or the convergence of all sequences of deals to such an optimum. We also analyse the length of the path leading to such optimal allocations. For scenarios where the agents using a resource do not have shared control over that resource (i.e., where any agent can use any resource she wants), we study the existence of pure Nash equilibria, i.e., allocations in which no single agent has an incentive to add or drop any of the resources she is currently holding. We provide results for modular valuation functions, we analyse the length of the paths leading to a pure Nash equilibrium, and we relate our findings to results from the literature on congestion games.Mots-clés
Multiagent resource allocation; Congestion gamesPublications associées
Affichage des éléments liés par titre et auteur.
-
Airiau, Stéphane; Endriss, Ulle (2010) Communication / Conférence
-
Maudet, Nicolas; Estivie, Sylvia; Endriss, Ulle; Chevaleyre, Yann (2004) Communication / Conférence
-
Chevaleyre, Yann; Endriss, Ulle; Estivie, Sylvia; Maudet, Nicolas (2004) Document de travail / Working paper
-
Estivie, Sylvia; Endriss, Ulle; Chevaleyre, Yann; Maudet, Nicolas (2008) Article accepté pour publication ou publié
-
Chevaleyre, Yann; Dunne, Paul; Endriss, Ulle; Lang, Jérôme; Lemaître, Michel; Maudet, Nicolas; Padget, Julian; Phelps, Steve; Rodríguez-Aguilar, Juan A.; Sousa, Paulo (2006) Article accepté pour publication ou publié