Approximate and online multi-issue negotiation

ABSTRACT

This paper analyzes bilateral multi-issue negotiation between self-interested autonomous agents. The agents have time constraints in the form of both deadlines and discount factors. There are m > 1 issues for negotiation where each issue is viewed as a pie of size one. The issues are "indivisible" (i.e., individual issues cannot be split between the parties; each issue must be allocated in its entirety to either agent). Here different agents value different issues differently. Thus, the problem is for the agents to decide how to allocate the issues between themselves so as to maximize their individual utilities. For such negotiations, we first obtain the equilibrium strategies for the case where the issues for negotiation are known a priori to the parties. Then, we analyse their time complexity and show that finding the equilibrium offers is an NP-hard problem, even in a complete information setting. In order to overcome this computational complexity, we then present negotiation strategies that are approximately optimal but computationally efficient, and show that they form an equilibrium. We also analyze the relative error (i.e., the difference between the true optimum and the approximate). The time complexity of the approximate equilibrium strategies is O(nm/ε²) where n is the negotiation deadline and ε the relative error. Finally, we extend the analysis to online negotiation where different issues become available at different time points and the agents are uncertain about their valuations for these issues. Specifically, we show that an approximate equilibrium exists for online negotiation and show that the expected difference between the optimum and the approximate is O(√m). These approximate strategies also have polynomial time complexity.

REFERENCES

• 1: Giorgio Ausiello , M. Protasi , A. Marchetti-Spaccamela , G. Gambosi , P. Crescenzi , V. Kann, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
• 2: M. Bac and H. Raff. Issue-by-issue negotiations: the role of information and time preference. Games and Economic Behavior, 13:125--134, 1996.
• 3: Allan Borodin , Ran El-Yaniv, Online computation and competitive analysis, Cambridge University Press, New York, NY, 1998
• 4: S. J. Brams. Fair division: from cake cutting to dispute resolution. Cambridge University Press, 1996.
• 5: L. A. Busch and I. J. Horstman. Bargaining frictions, bargaining procedures and implied costs in multiple-issue bargaining. Economica, 64:669--680, 1997.
• 6: S. S. Fatima, M. Wooldridge, and N. R. Jennings. Multi-issue negotiation with deadlines. Journal of Artificial Intelligence Research, 27:381--417, 2006.
• 7: C. Fershtman. The importance of the agenda in bargaining. Games and Economic Behavior, 2:224--238, 1990.
• 8: F. Glover. A multiphase dual algorithm for the zero-one integer programming problem. Operations Research, 13:879--919, 1965.
• 9: Mohammad Taghi Hajiaghayi , Robert Kleinberg , David C. Parkes, Adaptive limited-supply online auctions, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988784]
• 10: Oscar H. Ibarra , Chul E. Kim, Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems, Journal of the ACM (JACM), v.22 n.4, p.463-468, Oct. 1975 [doi>10.1145/321906.321909]
• 11: R. Inderst. Multi-issue bargaining with endogenous agenda. Games and Economic Behavior, 30:64--82, 2000.
• 12: R. Keeney and H. Raiffa. Decisions with Multiple Objectives: Preferences and Value Trade-offs. New York: John Wiley, 1976.
• 13: Sarit Kraus, Strategic negotiation in multiagent environments, MIT Press, Cambridge, MA, 2001
• 14: Daniel Lehmann , Liadan Ita Oćallaghan , Yoav Shoham, Truth revelation in approximately efficient combinatorial auctions, Journal of the ACM (JACM), v.49 n.5, p.577-602, September 2002 [doi>10.1145/585265.585266]
• 15: A. Lomuscio, M. Wooldridge, and N. R. Jennings. A classification scheme for negotiation in electronic commerce. International Journal of Group Decision and Negotiation, 12(1):31--56, 2003.
• 16: A. Marchetti-Spaccamela , C. Vercellis, Stochastic on-line knapsack problems, Mathematical Programming: Series A and B, v.68 n.1, p.73-104, Jan. 2, 1995 [doi>10.1007/BF01585758]
• 17: Silvano Martello , Paolo Toth, Knapsack problems: algorithms and computer implementations, John Wiley & Sons, Inc., New York, NY, 1990
• 18: M. J. Osborne and A. Rubinstein. A Course in Game Theory. The MIT Press, 1994.
• 19: H. Raiffa. The Art and Science of Negotiation. Harvard University Press, Cambridge, USA, 1982.
• 20: J. S. Rosenschein and G. Zlotkin. Rules of Encounter. MIT Press, 1994.
• 21: A. Rubinstein. Perfect equilibrium in a bargaining model. Econometrica, 50(1):97--109, January 1982.
• 22: T. Sandholm and V. Lesser. Levelled commitment contracts and strategic breach. Games and Economic Behavior: Special Issue on AI and Economics, 35:212--270, 2001.
• 23: Tuomas Sandholm , Nir Vulkan, Bargaining with deadlines, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.44-51, July 18-22, 1999, Orlando, Florida, United States
• 24: T. C. Schelling. An essay on bargaining. American Economic Review, 46:281--306, 1956.
• 25: Onn Shehory , Sarit Kraus, Methods for task allocation via agent coalition formation, Artificial Intelligence, v.101 n.1-2, p.165-200, May 1998 [doi>10.1016/S0004-3702(98)00045-9]
• 26: Satinder Singh , Vishal Soni , Michael Wellman, Computing approximate bayes-nash equilibria in tree-games of incomplete information, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988785]
• 27: I. Stahl. Bargaining Theory. Economics Research Institute, Stockholm School of Economics, Stockholm, 1972.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

General Terms:
Algorithms, Design, Theory

Keywords:
approximation, game-theory, negotiation, online computation