Open AccessOn the Communication Complexity of Multilateral Trading
Author(s) -
Ulle Endriss,
Nicolas Maudet
Publication year - 2004
Publication title -
hal (le centre pour la communication scientifique directe)
Language(s) - English
Resource type - Conference proceedings
DOI - 10.1109/aamas.2004.10091
Subject(s) - negotiation , computer science , task (project management) , order (exchange) , sequence (biology) , computational complexity theory , theoretical computer science , management science , business , algorithm , economics , sociology , social science , management , finance , biology , genetics
International audienceWe study the complexity of a multilateral negotiation framework where autonomous agents agree on a sequence of deals to exchange sets of discrete resources in order to both further their own goals and to achieve a distribution of resources that is socially optimal. When analysing such a framework, we can distinguish different aspects of complexity: How many deals are required to reach an optimal allocation of resources? How many communicative exchanges are required to agree on one such deal? How complex a communication language do we require? And finally, how complex is the reasoning task faced by each agent? This paper presents a number of results pertaining, in particular, to the first of these questions