Computing the optimal strategy to commit to

ABSTRACT

In multiagent systems, strategic settings are often analyzed under the assumption that the players choose their strategies simultaneously. However, this model is not always realistic. In many settings, one player is able to commit to a strategy before the other player makes a decision. Such models are synonymously referred to as leadership, commitment, or Stackelberg models, and optimal play in such models is often significantly different from optimal play in the model where strategies are selected simultaneously.The recent surge in interest in computing game-theoretic solutions has so far ignored leadership models (with the exception of the interest in mechanism design, where the designer is implicitly in a leadership position). In this paper, we study how to compute optimal strategies to commit to under both commitment to pure strategies and commitment to mixed strategies, in both normal-form and Bayesian games. We give both positive results (efficient algorithms) and negative results (NP-hardness results).

REFERENCES

• 1: Navin A. R. Bhat , Kevin Leyton-Brown, Computing Nash equilibria of action-graph games, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.35-42, July 07-11, 2004, Banff, Canada
• 2: V. Conitzer and T. Sandholm. Complexity results about Nash equilibria. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI), pages 765--771, Acapulco, Mexico, 2003.
• 3: Vincent Conitzer , Tuomas Sandholm, Complexity of (iterated) dominance, Proceedings of the 6th ACM conference on Electronic commerce, p.88-97, June 05-08, 2005, Vancouver, BC, Canada [doi>10.1145/1064009.1064019]
• 4: V. Conitzer and T. Sandholm. A generalized strategy eliminability criterion and computational methods for applying it. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pages 483--488, Pittsburgh, PA, USA, 2005.
• 5: A. A. Cournot. Recherches sur les principes mathématiques de la théorie des richesses (Researches 1Bayesian games are one potentially concise representation of normal-form games. into the Mathematical Principles of the Theory of Wealth). Hachette, Paris, 1838.
• 6: G. Dantzig. A proof of the equivalence of the programming problem and the game problem. In T. Koopmans, editor, Activity Analysis of Production and Allocation, pages 330--335. John Wiley & Sons, 1951.
• 7: Itzhak Gilboa , Ehud Kalai , Eitan Zemel, The complexity of eliminating dominated strategies, Mathematics of Operations Research, v.18 n.3, p.553-565, Aug. 1993 [doi>10.1287/moor.18.3.553]
• 8: I. Gilboa and E. Zemel. Nash and correlated equilibria: Some complexity considerations. Games and Economic Behavior, 1:80--93, 1989.
• 9: R. Karp. Reducibility among combinatorial problems. In R. E. Miller and J. W. Thatcher, editors, Complexity of Computer Computations, pages 85--103. Plenum Press, NY, 1972.
• 10: Michael J. Kearns , Michael L. Littman , Satinder P. Singh, Graphical Models for Game Theory, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.253-260, August 02-05, 2001
• 11: D. E. Knuth, C. H. Papadimitriou, and J. N. Tsitsiklis. A note on strategy elimination in bimatrix games. Operations Research Letters, 7(3):103--107, 1988.
• 12: D. Koller and N. Megiddo. The complexity of two-person zero-sum games in extensive form. Games and Economic Behavior, 4(4):528--552, Oct. 1992.
• 13: D. Koller, N. Megiddo, and B. von Stengel. Efficient computation of equilibria for extensive two-person games. Games and Economic Behavior, 14(2):247--259, 1996.
• 14: K. Leyton-Brown and M. Tennenholtz. Local-effect games. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI), Acapulco, Mexico, 2003.
• 15: Richard J. Lipton , Evangelos Markakis , Aranyak Mehta, Playing large games using simple strategies, Proceedings of the 4th ACM conference on Electronic commerce, p.36-41, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779933]
• 16: Michael L. Littman , Peter Stone, A polynomial-time nash equilibrium algorithm for repeated games, Proceedings of the 4th ACM conference on Electronic commerce, p.48-54, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779935]
• 17: R. D. Luce and H. Raiffa. Games and Decisions. John Wiley and Sons, New York, 1957. Dover republication 1989.
• 18: J. Nash. Equilibrium points in n-person games. Proc. of the National Academy of Sciences, 36:48--49, 1950.
• 19: Eugene Nudelman , Jennifer Wortman , Yoav Shoham , Kevin Leyton-Brown, Run the GAMUT: A Comprehensive Approach to Evaluating Game-Theoretic Algorithms, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.880-887, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.238]
• 20: M. J. Osborne and A. Rubinstein. A Course in Game Theory. MITPress, 1994.
• 21: Christos Papadimitriou, Algorithms, games, and the internet, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.749-753, July 2001, Hersonissos, Greece [doi>10.1145/380752.380883]
• 22: R. Porter, E. Nudelman, and Y. Shoham. Simple search methods for finding a Nash equilibrium. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pages 664--669, San Jose, CA, USA, 2004.
• 23: T. Sandholm, A. Gilpin, and V. Conitzer. Mixed-integer programming methods for finding Nash equilibria. In Proceedings of the National Conference on Artificial Intelligence (AAAI), pages 495--501, Pittsburgh, PA, USA, 2005.
• 24: J. von Neumann. Zur Theorie der Gesellschaftsspiele. Mathematische Annalen, 100:295--320, 1927.
• 25: H. von Stackelberg. Marktform und Gleichgewicht. Springer, Vienna, 1934.
• 26: B. von Stengel and S. Zamir. Leadership with commitment to mixed strategies. CDAM Research Report LSE-CDAM-2004-01, London School of Economics, Feb. 2004.

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES
      Subjects: Economics

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

General Terms:
Algorithms, Economics, Theory

Keywords:
bayesian games, commitment, game theory, leadership, nash equilibrium, normalform games, stackelberg