An Efficient Protocol for Negotiation over Combinatorial Domains with Incomplete Information
This addresses inefficiencies in bilateral or multi-lateral negotiations for self-interested agents, though it appears incremental as it builds on existing preference representation models.
The paper tackles the problem of reaching optimal agreements in agent-based negotiation over combinatorial domains under incomplete information, presenting a protocol that enables rational agents to identify efficient solutions through distributed search with computational efficiency demonstrated in experiments.
We study the problem of agent-based negotiation in combinatorial domains. It is difficult to reach optimal agreements in bilateral or multi-lateral negotiations when the agents' preferences for the possible alternatives are not common knowledge. Self-interested agents often end up negotiating inefficient agreements in such situations. In this paper, we present a protocol for negotiation in combinatorial domains which can lead rational agents to reach optimal agreements under incomplete information setting. Our proposed protocol enables the negotiating agents to identify efficient solutions using distributed search that visits only a small subspace of the whole outcome space. Moreover, the proposed protocol is sufficiently general that it is applicable to most preference representation models in combinatorial domains. We also present results of experiments that demonstrate the feasibility and computational efficiency of our approach.