Automated Multilateral Negotiation on Multiple Issues with Private Information

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 nonempty and the agents concede up to their reservation utilities, agents generating offers using our offer-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. Through computational experiments, we demonstrate 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.