/Automated Multilateral Negotiation on Multiple Issues with Private Information

Automated Multilateral Negotiation on Multiple Issues with Private Information

Ronghuo Zheng, Nilanjan Chakraborty, Tinglong Dai and Katia Sycara
Journal Article, Carnegie Mellon University, INFORMS Journal on Computing, October, 2015

Download Publication (PDF)

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. These works may not be reposted without the explicit permission of the copyright holder.


In this paper, we propose and analyze a distributed negotiation strategy for a multi-agent multi-attribute negotiation in which the agents have no information about the utility functions of other agents. We analytically prove that, if the zone of agreement is non-empty and the agents concede up to their reservation utilities, agents generating o↵ers using our o↵er-generation strategy, namely the sequential projection strategy, will converge to an agreement acceptable to all the agents; the convergence property does not depend on the specific concession strategy. In considering agents’ incentive to concede during the negotiation, we propose and analyze a reactive concession strategy.We demonstrate through computational experiments that our distributed negotiation strategy yields performance sufficiently close to the Nash bargaining solution, and that our algorithms are robust to potential deviation strategies. Methodologically, our paper advances the state of the art of alternating projection algorithms, in that we establish the convergence for the case of multiple, moving sets (as opposed to two, static sets in the current literature). Our paper introduces a new analytical foundation for a broad class of computational group decision and negotiation problems.

Available at SSRN: http://ssrn.com/abstract=2677729 or http://dx.doi.org/10.2139/ssrn.2677729

BibTeX Reference
author = {Ronghuo Zheng and Nilanjan Chakraborty and Tinglong Dai and Katia Sycara},
title = {Automated Multilateral Negotiation on Multiple Issues with Private Information},
journal = {INFORMS Journal on Computing},
year = {2015},
month = {October},