An efficient protocol for negotiation over combinatorial domains with incomplete information

Minyi Li, Quoc Bao Vo, Ryszard Kowalczyk

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

3 Citations (Scopus)


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. Selfinterested 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.
Original languageEnglish
Title of host publicationUncertainty in Artificial Intelligence
Subtitle of host publicationProceedings of the Twenty-Seventh Conference (2011), July 14-17, 2011, Barcelona, Spain
EditorsFabio G. Gozman, Avi Pfeffer
Place of PublicationCorvallis, Oregon
PublisherAUAI Press
Number of pages9
ISBN (Print)9780974903972
Publication statusPublished - 2011
Externally publishedYes
EventConference in Uncertainty in Artificial Intelligence 2011 - Universitat Pompeu Fabra, Barcelona, Italy
Duration: 14 Jul 201117 Jul 2011
Conference number: 27th (Proceedings)


ConferenceConference in Uncertainty in Artificial Intelligence 2011
Abbreviated titleUAI 2011
Internet address

Cite this