On the communication complexity of multilateral trading: Extended report

被引：14
作者：
Endriss, U
Maudet, N
机构：
[1] Univ London Imperial Coll Sci Technol & Med, Dept Comp, London SW7 2AZ, England
[2] Univ Paris 09, LAMSADE, F-75775 Paris, France
来源：
AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS | 2005年 / 11卷 / 01期
关键词：
negotiation; multiagent resource allocation; social welfare; complexity;
D O I：
10.1007/s10458-005-1080-2
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We 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?
引用
收藏
页码：91 / 107
页数：17
相关论文
共 27 条
[1]  
Andersson M, 1999, SIXTEENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE (AAAI-99)/ELEVENTH INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE (IAAI-99), P3
[2]  
[Anonymous], 1996, COMMUNICATION COMPLE
[3]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[4]  
Arrow K. J., 2002, HDB SOCIAL CHOICE WE, V1
[5]  
Chavez A., 1997, Proceedings of the First International Conference on Autonomous Agents, P323, DOI 10.1145/267658.267736
[6]  
Chevaleyre Y., 2004, P DIMACS LAMSADE WOR, V3, P83
[7]   The complexity of contract negotiation [J].
Dunne, PE ;
Wooldridge, M ;
Laurence, M .
ARTIFICIAL INTELLIGENCE, 2005, 164 (1-2) :23-46
[8]   Extremal behaviour in multiagent contract negotiation [J].
Dunne, PE .
JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 2005, 23 :41-78
[9]  
Endriss U, 2003, LECT NOTES COMPUT SC, V3071, P93
[10]  
ENDRISS U, 2004, P 3 INT JOINT C AUT, P622
123