06105878

a

06105878 Hao, Jianye Leung, Ho-fung An efficient negotiation protocol to achieve socially optimal allocation. Rahwan, Iyad (ed.) et al., PRIMA 2012: Principles and practice of multi-agent systems. 15th international conference, Kuching, Sarawak, Malaysia, September 3--7, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-32728-5/pbk). Lecture Notes in Computer Science 7455. Lecture Notes in Artificial Intelligence, 46-60 (2012). 2012 Berlin: Springer EN

doi:10.1007/978-3-642-32729-2_4

Summary: Negotiation-based resource allocation among agents is an important topic in multi-agent system research and it can be applied in various practical domains including network bandwidth allocation, robotics and grid computing. However, it is quite challenging to achieve efficient negotiation due to the huge space of all possible deals. A number of negotiation protocols have been proposed to guide the agents to reach desirable allocations over resources. However, previous work puts too much constraints on the negotiation environment and thus limits its applicability. To address this limitation, we present an efficient protocol within a more general negotiation framework, which can lead agents to achieve socially optimal allocation. We theoretically prove that the final allocation is guaranteed to be socially optimal provided that the agents are altruistic-individually rational. Besides, extensive simulation results show that the complexities of the negotiation process are greatly reduced under our protocol from both communication and computational aspects.