An analysis of feasible solutions for multi-issue negotiation involving nonlinear utility functions

ABSTRACT

This paper analyzes bilateral multi-issue negotiation between self-interested agents. Specifically, we consider the case where issues are divisible, there are time constraints in the form of deadlines and discount factors, and the agents have different preferences over the issues. Given these differing preferences, it is possible to reach Pareto-optimal agreements by negotiating all the issues together using a package deal procedure (PDP). However, finding equilibrium strategies for this procedure is not always computationally easy. In particular, if the agents' utility functions are nonlinear, then equilibrium strategies may be hard to compute. In order to overcome this complexity, we explore two different solutions. The first is to use the PDP for linear approximations of the given nonlinear utilities. The second solution is to use a simultaneous procedure (SP) where the issues are discussed in parallel but independently of each other. We then compare these two solutions both in terms of their computational properties (i.e., time complexity of computing an approximate equilibrium and the associated error of approximation) and their economic properties (i.e., the agents' utilities and social welfare of the resulting outcome). By doing so, we show that an approximate equilibrium for the PDP and the SP can be found in polynomial time. In terms of the economic properties, although the PDP is known to generate Pareto optimal outcomes, we show that, in some cases, which we identify, the SP is better for one of the two agents and also increases the social welfare.

REFERENCES

• 1: M. Bac and H. Raff, Issue-by-issue negotiations: the role of information and time preference, Games and Economic Behavior, 13: 125--134, 1996.
• 2: S. S. Fatima and M. Wooldridge and N. R. Jennings, Multi-issue negotiation with deadlines, Journal of Artificial Intelligence Research, 27: 381--417, 2006.
• 3: S. S. Fatima and M. Wooldridge and N. R. Jennings, Approximate and online multi-issue negotiation, In Proceedings of the Sixth International Conference on Autonomous Agents and MultiAgent Systems (AAMAS-07), pp 947--954, 2007.
• 4: C. Fershtman, The importance of the agenda in bargaining, Games and Economic Behavior, 2: 224--238, 1990.
• 5: M. R. Garey and D. S. Johnson, Computers and Intractability, W. H. Freeman and Company, 1979.
• 6: Francesco Giunta , Nicola Gatti, Bargaining over multiple issues in finite horizon alternating-offers protocol, Annals of Mathematics and Artificial Intelligence, v.47 n.3-4, p.251-271, August 2006 [doi>10.1007/s10472-006-9037-y]
• 7: T. Ito and H. Hattori and M. Klein, Multi-issue negotiation protocol for agents: Exploring nonlinear utility spaces, In Proceedings of the Twentieth International Joint Conference on Artificial Intelligence (IJCAI-07), pp 1347--1352, 2007.
• 8: M. Klein and P. Faratin and H. Sayama and Y. Bar-Yam, Negotiating complex contracts, Group Decision and Negotiation, 12(2): 58--73, 2003.
• 9: Sarit Kraus, Strategic negotiation in multiagent environments, MIT Press, Cambridge, MA, 2001
• 10: Silvano Martello , Paolo Toth, Knapsack problems: algorithms and computer implementations, John Wiley & Sons, Inc., New York, NY, 1990
• 11: R. E. Miller, Optimization: Foundations and Applications, Wiley-IEEE, 2000.
• 12: M. J. Osborne and A. Rubinstein, A Course in Game Theory, The MIT Press, 1994.
• 13: J. S. Rosenschein and G. Zlotkin, Rules of Encounter, MIT Press, 1994.
• 14: 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]
• 15: I. Stahl, Bargaining Theory, Economics Research Institute, Stockholm School of Economics, Stockholm, 1972.
• 16: J. R. Taylor, An introduction to error analysis: The study of uncertainties in physical measurements, University Science Books, 1982.

INDEX TERMS

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

Additional Classification:
  K. Computing Milieux
  K.4 COMPUTERS AND SOCIETY
      K.4.4 Electronic Commerce

General Terms:
Algorithms, Economics, Theory

Keywords:
approximation, game-theory, negotiation