Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

In many multiagent settings, each agent's goal is to come out ahead of the other agents on some metric, such as the currency obtained by the agent. In such settings, it is not appropriate for an agent to try to maximize its expected score on the metric; rather, the agent should maximize its expected probability of winning. In principle, given this objective, the game can be solved using game-theoretic techniques. However, most games of interest are far too large and complex to solve exactly. To get some intuition as to what an optimal strategy in such games should look like, we introduce a simplified game that captures some of their key aspects, and solve it (and several variants) exactly.

Specifically, the basic game that we study is the following: each agent i chooses a lottery over nonnegative numbers whose expectation is equal to its budget b_i. The agent with the highest realized outcome wins (and agents only care about winning). We show that there is a unique symmetric equilibrium when budgets are equal. We proceed to study and solve extensions, including settings where agents must obtain a minimum outcome to win; where agents choose their budgets (at a cost); and where budgets are private information.

REFERENCES

• 1: A. Anderson and L. M. B. Cabral. Go for broke or play it safe? Dynamic competition with choice of variance. RAND Journal of Economics, 2007. Forthcoming.
• 2: F. J. Anscombe and R. J. Aumann. A definition of subjective probability. Annals of Math. Statistics, 34:199--205, 1963.
• 3: M. R. Baye, D. Kovenock, and C. G. de Vries. The all-pay auction with complete information. Economic Theory, 8(2):291--305, 1996.
• 4: S. Bhattacharya and D. Mookherjee. Portfolio choice in research and development. RAND Journal of Economics, 17(4):594--605, 1986.
• 5: D. Billings, N. Burch, A. Davidson, R. Holte, J. Schaeffer, T. Schauenberg, and D. Szafron. Approximating game-theoretic optimal strategies for full-scale poker. IJCAI, 2003.
• 6: L. M. B. Cabral. Increasing dominance with no efficiency effect. Journal of Economic Theory, 102:471--479, 2002.
• 7: J. Collins, R. Arunachalam, N. Sadeh, J. Eriksson, N. Finne, and S. Janson. The supply chain management game for the 2007 trading agent competition. Technical Report CMU-ISRI-07-100, Carnegie Mellon University, 2006.
• 8: V. Denicolò. Patent races and optimal patent breadth and length. J. of Industrial Economics, 44(3):249--265, 1996.
• 9: V. Denicolò. Two-stage patent races and patent policy. RAND Journal of Economics, 31(3):450--487, 2000.
• 10: U. Dulleck, P. Frijters, and K. Podczeck. All-pay auctions with budget constraints and fair insurance. Working paper 0613, Department of Economics, Johannes Kepler University of Linz, Austria, 2006.
• 11: A. Gilpin and T. Sandholm. A competitive Texas Hold'em poker player via automated abstraction and real-time equilibrium computation. AAAI, 2006.
• 12: Andrew Gilpin , Tuomas Sandholm, Better automated abstraction techniques for imperfect information games, with application to Texas Hold'em poker, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329358]
• 13: Michael Kearns , Luis Ortiz, The Penn-Lehman Automated Trading Project, IEEE Intelligent Systems, v.18 n.6, p.22-31, November 2003 [doi>10.1109/MIS.2003.1249166]
• 14: C. Kiekintveld, Y. Vorobeychik, and M. P. Wellman. An analysis of the 2004 supply chain management trading agent competition. In Workshop on Trading Agent Design and Analysis (TADA), 2005.
• 15: J.-J. Laffont and J. Robert. Optimal auction with financially constrained buyers. Economic Letters, 52:181--186, 1996.
• 16: A. Mas-Colell, M. Whinston, and J. R. Green. Microeconomic Theory. Oxford University Press, 1995.
• 17: C. McMillen and M. Veloso. Thresholded rewards: Acting optimally in timed, zero-sum games. AAAI, 2007.
• 18: Jiefu Shi , Michael L. Littman, Abstraction Methods for Game Theoretic Poker, Revised Papers from the Second International Conference on Computers and Games, p.333-345, October 26-28, 2000
• 19: University of Alberta. American Association for Artificial Intelligence computer poker competition, 2006. http://www.cs.ualberta.ca/~pokert/.
• 20: Yevgeniy Vorobeychik , Christopher Kiekintveld , Michael P. Wellman, Empirical mechanism design: methods, with application to a supply-chain scenario, Proceedings of the 7th ACM conference on Electronic commerce, p.306-315, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134741]
• 21: M. P. Wellman, J. Estelle, S. Singh, Y. Vorobeychik, C. Kiekintveld, and V. Soni. Strategic interactions in a supply chain game. Computational Intelligence, 21:1--26, 2005.
• 22: M. P. Wellman, P. R. Jordan, C. Kiekintveld, J. Miller, and D. M. Reeves. Empirical game-theoretic analysis of the TAC market games. In Workshop on Game Theoretic and Decision Theoretic Agents (GTDT), 2006.

INDEX TERMS

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

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES

General Terms:
Economics, Theory

Keywords:
Nash equilibrium, contests, fair bets, game theory, strategic betting