Playing games in many possible worlds

ABSTRACT

In traditional game theory, players are typically endowed with exogenously given knowledge of the structure of the game--either full omniscient knowledge or partial but fixed information. In real life, however, people are often unaware of the utility of taking a particular action until they perform research into its consequences. In this paper, we model this phenomenon. We imagine a player engaged in a question and- answer session, asking questions both about his or her own preferences and about the state of reality; thus we call this setting "Socratic" game theory. In a Socratic game, players begin with an a priori probability distribution over many possible worlds, with a different utility function for each world. Players can make queries, at some cost, to learn partial information about which of the possible worlds is the actual world, before choosing an action. We consider two query models: (1) an unobservable-query model, in which players learn only the response to their own queries, and (2) an observable-query model, in which players also learn which queries their opponents made.The results in this paper consider cases in which the underlying worlds of a two-player Socratic game are either constant-sum games or strategically zero-sum games, a class that generalizes constant-sum games to include all games in which the sum of payoffs depends linearly on the interaction between the players. When the underlying worlds are constant sum, we give polynomial-time algorithms to find Nash equilibria in both the observable- and unobservable-query models. When the worlds are strategically zero sum, we give efficient algorithms to find Nash equilibria in unobservablequery Socratic games and correlated equilibria in observablequery Socratic games.

REFERENCES

• 1: Aaron Archer , David P. Williamson, Faster approximation algorithms for the minimum latency problem, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 2: R. J. Aumann. Subjectivity and correlation in randomized strategies. J. Mathematical Economics, 1:67--96, 1974.
• 3: Robert J. Aumann. Correlated equilibrium as an expression of Bayesian rationality. Econometrica, 55(1):1--18, January 1987.
• 4: Dick Bergemann and Juuso Välimäki. Information acquisition and efficient mechanism design. Econometrica, 70(3):1007--1033, May 2002.
• 5: Dick Bergemann and Juuso Välimäki. Information in mechanism design. Technical Report 1532, Cowles Foundation for Research in Economics, 2005.
• 6: Daniel S. Bernstein , Robert Givan , Neil Immerman , Shlomo Zilberstein, The Complexity of Decentralized Control of Markov Decision Processes, Mathematics of Operations Research, v.27 n.4, p.819-840, November 2002 [doi>10.1287/moor.27.4.819.297]
• 7: Avrim Blum , Prasad Chalasani , Don Coppersmith , Bill Pulleyblank , Prabhakar Raghavan , Madhu Sudan, The minimum latency problem, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.163-171, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195125]
• 8: Andrei Broder , Michael Mitzenmacher, Optimal plans for aggregation, Proceedings of the twenty-first annual symposium on Principles of distributed computing, July 21-24, 2002, Monterey, California [doi>10.1145/571825.571852]
• 9: Moses Charikar , Ronald Fagin , Venkatesan Guruswami , Jon Kleinberg , Prabhakar Raghavan , Amit Sahai, Query strategies for priced information, Journal of Computer and System Sciences, v.64 n.4, p.785-819, June 2002 [doi>10.1006/jcss.2002.1828]
• 10: Xi Chen and Xiaotie Deng. 3-NASH is PPAD-complete. In Electronic Colloquium on Computational Complexity, 2005.
• 11: Xi Chen and Xiaotie Deng. Settling the complexity of 2-player Nash-equilibrium. In Electronic Colloquium on Computational Complexity, 2005.
• 12: Olivier Compte and Philippe Jehiel. Auctions and information acquisition: Sealed-bid or dynamic formats? Technical report, Centre d'Enseignement et de Recherche en Analyse Socio-économique, 2002.
• 13: Vincent Conitzer and Tuomas Sandholm. Complexity results about Nash equilibria. In Proceedings of the International Joint Conference on Artificial Intelligence, pages 765--771, 2003.
• 14: Gerard Cornuejols, Marshall L. Fisher, and George L. Nemhauser. Location of bank accounts to optimize float: An analytic study of exact and approximate algorithms. Management Science, 23(8), April 1977.
• 15: Jacques Crémer and Fahad Khalil. Gathering information before signing a contract. American Economic Review, 82:566--578, 1992.
• 16: Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou. The complexity of computing a Nash equilbrium. In Electronic Colloquium on Computational Complexity, 2005.
• 17: Konstantinos Daskalakis and Christos H. Papadimitriou. Three-player games are hard. In Electronic Colloquium on Computational Complexity, 2005.
• 18: K. M. J. De Bontridder, B. V. Halldórsson, M. M. Halldórsson, C. A. J. Hurkens, J. K. Lenstra, R. Ravi, and L. Stougie. Approximation algorithms for the test cover problem. Mathematical Programming, 98(1-3):477--491, September 2003.
• 19: Ap Dijksterhuis, Maarten W. Bos, Loran F. Nordgren, and Rick B. van Baaren. On making the right choice: The deliberation-without-attention effect. Science, 311:1005--1007, 17 February 2006.
• 20: Rosemary Emery-Montemerlo , Geoff Gordon , Jeff Schneider , Sebastian Thrun, Approximate Solutions for Partially Observable Stochastic Games with Common Payoffs, Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems, p.136-143, July 19-23, 2004, New York, New York [doi>10.1109/AAMAS.2004.67]
• 21: Alex Fabrikant , Christos Papadimitriou , Kunal Talwar, The complexity of pure Nash equilibria, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007445]
• 22: Kyna Fong. Multi-stage Information Acquisition in Auction Design. Senior thesis, Harvard College, 2003.
• 23: Lance Fortnow , Duke Whang, Optimality and domination in repeated games with bounded players, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.741-749, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195448]
• 24: Y. Freund , M. Kearns , Y. Mansour , D. Ron , R. Rubinfeld , R. E. Schapire, Efficient algorithms for learning to play repeated games against computationally bounded adversaries, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.332, October 23-25, 1995
• 25: Drew Fudenberg and Jean Tirole. Game Theory. MIT, 1991.
• 26: Michel X. Goemans and Jon Kleinberg. An improved approximation ratio for the minimum latency problem. Mathematical Programming, 82:111--124, 1998.
• 27: Paul W. Goldberg and Christos H. Papadimitriou. Reducibility among equilibrium problems. In Electronic Colloquium on Computational Complexity, 2005.
• 28: M. Grotschel, L. Lovasz, and A. Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1:70--89, 1981.
• 29: A. Gupta , A. Kumar, Sorting and Selection with Structured Costs, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.416, October 14-17, 2001
• 30: Eric A. Hansen, Daniel S. Bernstein, and Shlomo Zilberstein. Dynamic programming for partially observable stochastic games. In National Conference on Artificial Intelligence (AAAI), 2004.
• 31: John C. Harsanyi. Games with incomplete information played by "Bayesian" players. Management Science, 14(3,5,7), 1967--1968.
• 32: S. Hart , D. Schmeidler, Existence of correlated equilibria, Mathematics of Operations Research, v.14 n.1, p.18-25, Feb. 1989 [doi>10.1287/moor.14.1.18]
• 33: Eric Horvitz , Geoffrey Rutledge, Time-dependent utility and action under uncertainty, Proceedings of the seventh conference (1991) on Uncertainty in artificial intelligence, p.151-158, June 1994, Los Angeles, California, United States
• 34: G. E. Hughes and M. J. Cresswell. A New Introduction to Modal Logic. Routledge, 1996.
• 35: Sheena S. Iyengar and Mark R. Lepper. When choice is demotivating: Can one desire too much of a good thing? J. Personality and Social Psychology, 79(6):995--1006, 2000.
• 36: Ehud Kalai. Bounded rationality and strategic complexity in repeated games. Game Theory and Applications, pages 131--157, 1990.
• 37: Sampath Kannan , Sanjeev Khanna, Selection with monotone comparison costs, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 38: L.G. Khachiyan. A polynomial algorithm in linear programming. Dokklady Akademiia Nauk SSSR, 244, 1979.
• 39: Daphne Koller and Nimrod Megiddo. The complexity of two-person zero-sum games in extensive form. Games and Economic Behavior, 4:528--552, 1992.
• 40: Daphne Koller, Nimrod Megiddo, and Bernhard von Stengel. Efficient computation of equilibria for extensive two-person games. Games and Economic Behavior, 14:247--259, 1996.
• 41: Kate Larson , Tuomas Sandholm, Mechanism design for computationally limited agents, 2004
• 42: Kate Larson , Tuomas Sandholm, Bargaining with limited computation: deliberation equilibrium, Artificial Intelligence, v.132 n.2, p.183-217, November 2001 [doi>10.1016/S0004-3702(01)00132-1]
• 43: Kate Larson , Tuomas Sandholm, Costly valuation computation in auctions, Proceedings of the 8th conference on Theoretical aspects of rationality and knowledge, July 08-10, 2001, Siena, Italy
• 44: Kate Larson , Tuomas Sandholm, Strategic deliberation and truthful revelation: an impossibility result, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988825]
• 45: C. E. Lemke and J. T. Howson, Jr. Equilibrium points of bimatrix games. J. Society for Industrial and Applied Mathematics, 12, 1964.
• 46: 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]
• 47: Michael L. Littman, Michael Kearns, and Satinder Singh. An efficient exact algorithm for singly connected graphical games. In Proceedings of Neural Information Processing Systems, 2001.
• 48: Steven A. Matthews and Nicola Persico. Information acquisition and the excess refund puzzle. Technical Report 05-015, Department of Economics, University of Pennsylvania, March 2005.
• 49: Richard D. McKelvey and Andrew McLennan. Computation of equilibria in finite games. In H. Amman, D. A. Kendrick, and J. Rust, editors, Handbook of Compututational Economics, volume 1, pages 87--142. Elsevier, 1996.
• 50: B.M.E. Moret and H. D. Shapiro. On minimizing a set of tests. SIAM J. Scientific Statistical Computing, 6:983--1003, 1985.
• 51: H. Moulin and J.-P. Vial. Strategically zero-sum games: The class of games whose completely mixed equilibria cannot be improved upon. International J. Game Theory, 7(3/4), 1978.
• 52: John F. Nash, Jr. Equilibrium points in n-person games. Proceedings of the National Academy of Sciences, 36:48--49, 1950.
• 53: P. S. Bradley , O. L. Mangasarian , W. N. Street , Debra E. Meyerson , Pieter Klaassen , Panayiotis Theodossiou , Abraham Neyman, Finitely Repeated Games with Finite Automata, Mathematics of Operations Research, v.23 n.3, p.513-552, March 1998 [doi>10.1287/moor.23.3.513]
• 54: Christos H. Papadimitriou, On the complexity of the parity argument and other inefficient proofs of existence, Journal of Computer and System Sciences, v.48 n.3, p.498-532, June 1994 [doi>10.1016/S0022-0000(05)80063-7]
• 55: 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]
• 56: Christos H. Papadimitriou, Computing correlated equilibria in multi-player games, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060598]
• 57: Christos H. Papadimitriou , Tim Roughgarden, Computing equilibria in multi-player games, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 58: Christos H. Papadimitriou , Mihalis Yannakakis, On complexity as bounded rationality (extended abstract), Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.726-733, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195445]
• 59: David C. Parkes, Auction design with costly preference elicitation, Annals of Mathematics and Artificial Intelligence, v.44 n.3, p.269-302, July 2005 [doi>10.1007/s10472-005-4692-y]
• 60: Nicola Persico. Information acquisition in auctions. Econometrica, 68(1):135--148, 2000.
• 61: Jean-Pierre Ponssard and Sylvain Sorin. The LP formulation of finite zero-sum games with incomplete information. International J. Game Theory, 9(2):99--105, 1980.
• 62: Eric Rasmussen. Strategic implications of uncertainty over one's own private value in auctions. Technical report, Indiana University, 2005.
• 63: Leonardo Rezende. Mid-auction information acquisition. Technical report, University of Illinois, 2005.
• 64: Ariel Rubinstein. Modeling Bounded Rationality. MIT, 1988.
• 65: Barry Schwartz. The Paradox of Choice: Why More is Less. Ecco, 2004.
• 66: Herbert Simon. Models of Bounded Rationality. MIT, 1982.
• 67: I. Simonson and A. Tversky. Choice in context: Tradeoff contrast and extremeness aversion. J. Marketing Research, 29:281--295, 1992.
• 68: Brian Skyrms, Dynamic Models of Deliberation and the Theory of Games, Proceedings of the 3rd Conference on Theoretical Aspects of Reasoning about Knowledge, p.185-200, March 01, 1990
• 69: Richard S. Sutton , Andrew G. Barto, Introduction to Reinforcement Learning, MIT Press, Cambridge, MA, 1998
• 70: John von Neumann and Oskar Morgenstern. Theory of Games and Economic Behavior. Princeton, 1957.
• 71: Bernhard von Stengel. Computing equilibria for two-person games. In R. J. Aumann and S. Hart, editors, Handbook of Game Theory with Econonic Applications, volume 3, pages 1723--1759. Elsevier, 2002.
• 72: S. Zilberstein and S. Russell. Approximate reasoning using anytime algorithms. In S. Natarajan, editor, Imprecise and Approximate Computation. Kluwer, 1995.

INDEX TERMS

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

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

General Terms:
Algorithms, Economics, Theory

Keywords:
Nash equilibria, algorithms, correlated equilibria, game theory, information acquisition, socratic games