An Efficient Protocol for Negotiation over Combinatorial Domains with Incomplete Information

Minyi Li, Quoc Bao Vo, Ryszard Kowalczyk
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:493-501, 2011.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-li11a, title = {An Efficient Protocol for Negotiation over Combinatorial Domains with Incomplete Information}, author = {Li, Minyi and Vo, Quoc Bao and Kowalczyk, Ryszard}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {493--501}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/li11a/li11a.pdf}, url = {https://proceedings.mlr.press/r9/li11a.html}, abstract = {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.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T An Efficient Protocol for Negotiation over Combinatorial Domains with Incomplete Information %A Minyi Li %A Quoc Bao Vo %A Ryszard Kowalczyk %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-li11a %I PMLR %P 493--501 %U https://proceedings.mlr.press/r9/li11a.html %V R9 %X 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. %Z Reissued by PMLR on 04 October 2026.
APA
Li, M., Vo, Q.B. & Kowalczyk, R.. (2011). An Efficient Protocol for Negotiation over Combinatorial Domains with Incomplete Information. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:493-501 Available from https://proceedings.mlr.press/r9/li11a.html. Reissued by PMLR on 04 October 2026.

Related Material