Complex Multi-Issue Negotiation Using Utility Hyper-Graphs
Rafik Hadfi and Takayuki Ito
Department of Computer Science and Engineering, Nagoya Institute of Technology
Gokiso, Showa-ku, Nagoya 466-8555, Japan
We propose to handle the complexity of utility spaces used in multi-issue negotiation by adopting a new representation that allows a modular decomposition of the issues and the constraints. This is based on the idea that a constraint-based utility space is nonlinear with respect to issues, but linear with respect to the constraints. This allows us to rigorously map the utility space into an issue-constraint hyper-graph. Exploring the utility space reduces then to a message passing mechanism along the hyper-edges of the hyper-graph by means of utility propagation. Optimal contracts are found efficiently using a variation of the Max-Sum algorithm. We evaluate the model experimentally using parameterized nonlinear utility spaces, showing that it can handle a large family of complex utility spaces by finding optimal contracts, outperforming previous sampling-based approaches. We also evaluate the model in a negotiation setting. We show that under high complexity, social welfare could be greater than the sum of the individual agents’ best utilities.
-  U. Chajewska and D. Koller, “Utilities as Random Variables: Density Estimation and Structure Discovery,” Proc. of the 16th Annual Conf. on Uncertainty in Artificial Intelligence (UAI-00), pp. 63-71, 2000.
-  F. Bacchus and A. Grove, “Graphical Models for Preference and Utility,” Proc. of the 11th Conf. on Uncertainty in Artificial Intelligence (UAI’95), pp. 3-10, San Francisco, CA, USA, 1995, Morgan Kaufmann Publishers Inc.
-  V. Robu, D. J. A. Somefun, and J. L. Poutre, “Modeling complex multi-issue negotiations using utility graphs,” Proc. of the 4th Int. Joint Conf. on Autonomous Agents and Multi-Agent Systems (AAMAS 2005), pp. 280-287, 2005.
-  I. Marsa-Maestre, M. A. Lopez-Carmona, J. R. Velasco, and E. d. l. Hoz, “Effective bidding and deal identification for negotiations in highly nonlinear scenarios,” Proc. of the 8th Int. Conf. on Autonomous Agents and Multiagent Systems – Vol.2, AAMAS’09, pp. 1057-1064, Richland, SC, 2009, Int. Foundation for Autonomous Agents and Multiagent Systems.
-  K. Fujita, T. Ito, and M. Klein, “An Approach to Scalable Multiissue Negotiation: Decomposing the Contract Space Based on Issue Interdependencies,” Pro. of the 2010 IEEE/WIC/ACM Int. Conf. on Web Intelligence and Intelligent Agent Technology – Vol.2, WI-IAT’10, pp. 399-406, Washington, DC, USA, 2010, IEEE Computer Society.
-  J. Kwisthout and I. v. Rooij, “Bridging the gap between theory and practice of approximate Bayesian inference,” Cognitive Systems Research: Special Issue on ICCM2012, Vol.24, No.0, pp. 2-8, 2013.
-  X. S. Zhang and M. Klein, “Hierarchical Negotiation Model for Complex Problems with Large-Number of Interdependent Issues,” 2012 IEEE/WIC/ACM Int. Conf. on Intelligent Agent Technology (IAT 2012), Macau, China, pp. 126-133, December 4-7 2012.
-  X. S. Zhang, M. Klein, and I. Marsa-Maestre, “Scalable Complex Contract Negotiation with Structured Search and Agenda Management,” Proc. of the 28th AAAI Conf. on Artificial Intelligence, Quebec City, Quebec, Canada., pp. 1507-1514, July 27-31, 2014.
-  I. Marsa-Maestre, M. Lopez-Carmona, J. Carral, and G. Ibanez, “A Recursive Protocol for Negotiating Contracts Under Nonmonotonic Preference Structures,” Group Decision and Negotiation, Vol.22, No.1, pp. 1-43, 2013.
-  T. Ito, H. Hattori, and M. Klein, “Multi-issue Negotiation Protocol for Agents : Exploring Nonlinear Utility Spaces,” Proc. of the 20th Int. Joint Conf. on Artificial Intelligence (IJCAI-2007), pp. 1347-1352, 2007.
-  M. A. Lopez-Carmona, I. Marsa-Maestre, E. De La Hoz, and J. R. Velasco, “A Region-based Multi-issue Negotiation Protocol for Non-monotonic Utility Spaces,” Computational Intelligence, Vol.27, No.2, pp. 166-217, 2011.
-  J. Pearl, “Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference,” Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1988.
-  K. Arrow, “Social Choice and Individual Values,” Cowles Foundation Monographs Series, Yale University Press, 1963.
-  A. Sen, “Collective choice and social welfare,” Mathematical economics texts, Holden-Day, 1970.
This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.