An Efficient Protocol for Negotiation over Combinatorial Domains with Incomplete Information

摘要

We study the problem of agent-based nego tiation in combinatorial domains. It is dif ficult to reach optimal agreements in bilat eral or multi-lateral negotiations when the agents' preferences for the possible alter natives are not common knowledge. Self interested agents often end up negotiating in efficient agreements in such situations. In this paper, we present a protocol for nego tiation in combinatorial domains which can lead rational agents to reach optimal agree ments under incomplete information setting. Our proposed protocol enables the negotiat ing agents to identify efficient solutions us ing distributed search that visits only a small subspace of the whole outcome space. More over, the proposed protocol is sufficiently general that it is applicable to most prefer ence representation models in combinatorial domains. We also present results of exper iments that demonstrate the feasibility and computational efficiency of our approach.