Multilateral Monotonic Concession Protocol for Task Negotiation
Donghae Kim, Maruthi Ram Akella · 2025
This paper introduces a multilateral negotiation protocol for multi-agent task allocation, extending the Monotonic Concession Protocol (MCP) beyond its traditional two-player framework. To accommodate scenarios with more than two agents, we generalize key MCP concepts, including concession, agreement, and risk. In particular, we define a generalized notion of risk, enabling agents to systematically rank task allocations. This risk metric is used to construct a Nash strategy that guides the negotiation toward a task partition maximizing the Nash product of the agents’ utilities. The proposed protocol ensures a fully distributed negotiation process, where agents operate in a multilateral manner with symmetry in actions, roles, states, and information. We demonstrate the protocol’s performance through a three-player task negotiation example, showing that the process converges monotonically toward an allocation optimizing the Nash product.