Date
2005
Dewey
Intelligence artificielle
Sujet
Resource Allocation; Negotiation; Allocation de ressources; Négociation
Conference name
3èmes Journées Francophones sur les Modèles Formels d'Interaction (MFI-2005)
Conference date
05-2005
Conference city
Caen
Conference country
France
Book title
MFI'05 Modèles formels de l'interaction
Author
Herzig, Andreas; Lespérance, Yves; Mouaddib, Abdel-Illah
Publisher
Cepadues
Year
2005
Pages number
260
ISBN
2854286979
Author
Chevaleyre, Yann
Maudet, Nicolas
Endriss, Ulle
Type
Communication / Conférence
Abstract (FR)
Cet article aborde l’allocation de ressources multiagent
par la négociation. Un des problèmes majeurs de cette approche, qui rend difficile la mise en pratique des résultats théoriques, est qu’il s’avère très complexe d’identifier les échanges potentiellement acceptables pour un ensemble donné d’agents. La solution que nous envisageons
ici est d’utiliser différents protocoles conçus afin d’exploiter certaines propriétés des fonctions d’utilités utilisées par les agents pour modéliser leurs préférences. Nous
considérons spécifiquement les domaines où les fonctions
d’utilité sont k-additives (c’est-à-dire que les synergies
entre les ressources sont restreintes aux lots d’au plus k
ressources), et structurées sous forme d’arbre, au sens où
les lots pour lesquels il existe une synergie ne se “chevauchent” pas.
Abstract (EN)
Negotiation over resources in multiagent systems is a timely and fruitful area of ongoing research. However, the
prohibitively high complexity of the task of identifying
rational deals, i.e. deals that are beneficial for all participants, currently hinders the successful transfer of theoretical results to practical applications. To address this issue,
we propose several protocols designed to tame the complexity of negotiation by exploiting structural properties
of the utility functions used by agents to model their preferences over alternative bundles of resources. In particular, we consider domains where utility functions are
k-additive (that is, synergies between different resources
are restricted to bundles of at most k items) and “tree-
structured” in the sense that the bundles for which there
are synergies do not overlap. We show how protocols exploiting these properties can enable drastically simplified
negotiation processes.