Decentralized and fair multilateral negotiation

Abstract

Negotiation is a fundamental mechanism in multiagent systems. It may be a complex mechanism involving multiple agents with conflicting interests that need to reach a joint agreement. Complexity intensifies when moving from bilateral to multilateral negotiation. An important issue in such negotiation is to define a specific and effective protocol that guides the interactions between the agents. In this paper, we propose a novel, fully decentralized mechanism for multilateral negotiation, that reduces the inherent complexity of the problem. We specifically reduce the complexity of searching in the agreement search space, utilizing the divide and conquer approach. The proposed negotiation mechanism structures the negotiation by dividing a set of agents into several groups. Proposals are initially exchanged only within groups, and only later across groups. This structure is enhanced with various interaction policies. These policies include rules that determine permissible behaviors of the agents within the structure. Via structure and policies our negotiation protocol controls the negotiation time and facilitates feasible multilateral negotiation. We provide theoretical and experimental results showing the efficiency of our protocol.