Excerpt

Game theory is a cornerstone of the social sciences today. In its original formulation by John von Neumann and Oskar Morgenstern (1944), a variety of concepts and procedures for solving games was proposed, depending on the nature of the game being played. For example, minimax solutions were advanced for two-person, zero-sum games, that is, games in which what is won by one player is lost by the other. What John Nash’s foundational 1951 paper did, along with the shorter one from 1950, was to provide an alternative solution concept that was more generally applicable, to zero- and non-zero–sum games alike, to games with many players, and so on. This is the idea of an equilibrium point of a game, in which the strategies of players are configured such that no one can be made better off by unilaterally deviating to a different strategy. Nash proved that such equilibria always exist for any game with a finite number of strategies. The Nash equilibrium, as it is today known, has become a focal point for solving essentially all games, and is fundamental to the practice of game theory.

Specifically, consider two players engaged in a game with a finite set of strategies and fixed and known possible payoffs that depend on the strategies employed by the players. A single play of the game amounts to each player selecting a strategy and receiving the corresponding payoff. Each individual strategy is considered “pure” while a mixed strategy involves a set of probabilities for playing each of the pure strategies. For example, consider the children’s game of rock–paper–scissors, played by two players: the rock strategy loses to paper but defeats scissors, while the paper strategy loses to scissors. It is a zero-sum game in which the mixed strategy of playing each of the three pure strategies one-third of the time is intuitively obvious, even to kids. A two-strategy version is “matching pennies”—play “heads” half the time, “tails” the other half.

Bibliography

Brouwer, L. E. J. 1911. “Beweis der invarianz des n-dimensionalen gebiets.” Mathematische Annalen 71 (3): 305–313. https://doi.org/10.1007/BF01456846.

Camerer, C. F. 1997. “Progress in Behavioral Game Theory.” Journal of Economic Perspectives 11 (4): 167–188. https://doi.org/10.1257/jep.11.4.167.

Daskalakis, C., P. W. Goldberg, and C. H. Papadimitriou. 2009. “The Complexity of Computing a Nash Equilibria.” SIAM Journal on Computing 39 (1): 195–259. https://doi.org/10.1137/070699652.

Erev, I., and A. E. Roth. 1998. “Predicting How People Play Games: Reinforcement Learning in Experimental Games with Unique, Mixed Strategy Equilibria.” American Economic Review 88 (4): 848–881.

Harrington, Jr., J. E. 1987. “Non-Cooperative Games.” In The New Palgrave: A Dictionary of Economics, edited by J. Eatwell, M. Milgate, and P. Newman. New York, NY: W. W. Norton.

Harsanyi, J. C. 1973. “Oddness of the Number of Equilibrium Points: A New Proof.” International Journal of Game Theory 2:235–250. https://doi.org/10.1007/BF01737572.

Holt, C. A., and A. E. Roth. 2004. “The Nash Equilibrium: A Perspective.” Proceedings of the National Academy of Sciences 101 (12): 3999–4002. https://doi.org/10.1073/pnas.0308738101.

Kakutani, S. 1941. “A Generalization of Brouwer’s Fixed Point Theorem.” Duke Mathematical Journal 8 (3): 457–459. https://doi.org/10.1215/S0012-7094-41-00838-4.

Lewontin, R. C. 1961. “Evolution and the Theory of Games.” Journal of Theoretical Biology 1 (3): 382–403. https://doi.org/10.1016/0022-5193(61)90038-8.

Maynard Smith, J., and G. R. Price. 1973. “The Logic of Animal Conflict.” Nature 246:15–18. https://doi.org/10.1038/246015a0.

Moore, C., and S. Mertens. 2011. The Nature of Computation. Oxford, UK: Oxford University Press.

Nash, J. 1950. “Equilibrium Points in n-Person Games.” Proceedings of the National Academy of Sciences 36 (1): 48–49. https://doi.org/10.1073/pnas.36.1.48.

—. 1951. “Non-Cooperative Games.” Annals of Mathematics 54 (2): 286–295. https://doi.org/10.2307/1969529.

Papadimitriou, C. H. 1994. “On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence.” Journal of Computer and Systems Sciences 48 (3): 498–532. https://doi.org/10.1016/S0022-0000(05)80063-7.

—. 2015. “The Complexity of Computing Equilibria.” In Handbook of Game Theory with Economic Applications, edited by H. P. Young and S. Zamir, 4:779–810. Oxford, UK: Elsevier. https://doi.org/10.1016/B978-0-444-53766-9.00014-8.

Scarf, H. 1973. The Computation of Economic Equilibria. New Haven, CT: Yale University Press.

Schelling, T. C. 1960. The Strategy of Conflict. Cambridge, MA: Harvard University Press.

Shubik, M. 1955. “The Uses of Game Theory in Management Science.” Management Science 2 (1): 40–54. https://doi.org/10.1287/mnsc.2.1.40.

—. 1984. Game Theory in the Social Sciences: A Game-Theoretic Approach to Political Economy. Cambridge, MA: MIT Press.

Smith, V. L. 1962. “An Experimental Study of Competitive Market Behavior.” Journal of Political Economy 70 (2): 111–137. https://doi.org/10.1086/258609.

Sperner, E. 1928. Neuer Beweis für die Invarianz der Dimensionszahl und des Gebietes. 6:265–272. https://doi.org/10.1007/BF02940617.

von Neumann, J. 1937. Über ein Ökonomisches Gleichungssystem und eine Verallgemeinerung des Brouwerschen Fixpunktsatzes. Edited by K. Menger. 8:73–83.

—. 1945. A Model of General Economic Equilibrium. 13:1–9. 33. https://doi.org/10.2307/2296111.

von Neumann, J., and O. Morgenstern. 1944. Theory of Games and Economic Behavior. Princeton, NJ: Princeton University Press.

Walker, M., and J. Wooders. 2001. “Minimax Play at Wimbledon.” American Economic Review 91 (5): 1521–1538. https://doi.org/10.1257/aer.91.5.1521.

Wilson, R. 1971. “Computing Equilibria in N-Person Games.” SIAM Journal of Applied Mathematics 21 (1): 80–87. https://doi.org/10.1137/0121011.

BACK TO Foundational Papers in Complexity Science