Advances in Game Theory

views updated

Advances in Game Theory

Overview

Game theory provides ways to understand and predict behavior in situations where participants are driven by goals. Developed by John von Neumann (1903-1959) and Oskar Morgenstern (1902-1977), game theory reveals patterns of advantage for participants and has been applied broadly in areas such as jury selection, investment decisions, military strategy, and medical analysis. Some game theory models, like the prisoners' dilemma and zero-sum games, have become part of common discourse.

Background

Von Neumann was actively involved in a wide range of mathematical activities. In the 1920s he became aware of a series of papers by Emile Borel (1871-1956) that gave mathematical form to mixed strategies (combining rational selection and chance). Von Neumann also discovered a limited minimax (from minimum/maximum) solution for certain games. In 1928, von Neumann provided a proof for the minimax theorem, establishing one of the pillars of game theory.

The minimax theorem applies to zero-sum games (one in which the total payoff of the game is fixed). For two players, everything that one person gains is lost by the other. Minimax states that using a mixed strategy, the average gain or loss over time for a given game can be calculated. It also concludes that, for a large class of two-person zero-sum games, there is no point in playing. The long-term outcome is determined entirely by the rules, rather than any clever play.

The proof of minimax was a neat piece of mathematics, incorporating both topology and functional calculus, but it was up to von Neumann to expand the work and apply it to the real world.

The idea that games like poker, chess, or betting on a coin toss could provide deep insights into complex economic and social behavior is not obvious, and von Neumann's intuitive grasp of this may be his greatest contribution. The impact comes from three factors: First, games provide a ready reference point since game playing is an almost universal human endeavor. Second, games provide a model that incorporates strategy. Third, games can be varied and tested with real human players.

One example of an insight that can come from game theory is the concept of dominance. You and an opponent may seem to have a dozen choices each in a game. However, if all the outcomes are put into a matrix, you will probably find some choices that have a worse outcome in every single case. You will eliminate these choices from consideration and, looking at your opponent's point of view, eliminate his or her consistently unfavorable choices. Choices that are consistently worse are said to be dominated by other choices. They can be excluded as possibilities, immediately simplifying your analysis.

Von Neumann slowly built upon game theory, turning to applications in economics in 1939 after meeting economist Oskar Morgenstern. The two coauthored Theory of Games and Economic Behavior in 1944. The book was pivotal in establishing the field, laying the foundations for all subsequent work in game theory. It not only brought zero-sum ideas to a practical application (e.g., economics), it also looked at cooperative games and brought the notion of utility (quantification of preference) to game theory.

Impact

Economists immediately recognized the significance of game theory, but initially found it difficult to apply. Its first important, practical adoption was in military strategy. During the Cold War, game theory was used both for analysis of specific operations (e.g. dogfights) and overall strategy, such as the doctrine of mutual assured destruction that came to dominate nuclear politics for decades. The latter inspired some opposition to game theory as a dehumanizing tool. Looking at battles only in terms of victories or defeats without regard to human suffering was criticized as a dangerous simplification.

Some of the most important contributions toward realizing the potential of game theory in economics (and, by extension, other practical endeavors) came from John Forbes Nash (1928- ), who, through his thesis in 1950 and an influential article the next year, encouraged its adoption. In particular, Nash developed bargaining theory and was the first to distinguish cooperative games, where binding agreements are feasible, from noncooperative games, where such agreements are not feasible. His solution for noncooperative games provided a way that all players' expectations could be fulfilled and their strategies optimized. This solution is now known as the Nash equilibrium.

One of the most fruitful games used for predicting the outcomes of strategic interactions has been A. W. Tucker's prisoners' dilemma. In this scenario, two men have been captured for burglary and are being questioned separately. If both keep quiet, they will get one year in jail each on weapons charges. If both confess and implicate the other, they will get 10 years each. If one agrees to testify against the other, who is keeping quiet, the cooperative one goes free and the other one goes to jail for 20 years. The "rational" solution is to confess and avoid the 20-year sentence, with a chance of immediate freedom. But it's hard to ignore the fact that if both stay quiet, they only get a year each, the best outcome possible for the team. The situation is paradoxical, but it reflects real-world circumstances, such as OPEC nations trying to limit oil production, budgeting for defense during an arms race, and compliance with anti-pollution laws. In each case, cheating can lead to big payoffs for individuals, but everyone is worse off if cheating is widespread.

Game theory continues to move closer to real-world situations. Further developments include the study of static games (where players play simultaneously), dynamic games (where players play over time), and games of incomplete information. In 1967, there was a serious challenge to von Neumann and Morgenstern's work in cooperative games. Since publication, most experts had assumed that, universally, each cooperative game had at least one solution. Neither von Neumann nor Morgenstern had been able to find a counterexample. However, William Lucas was able to prove that for one specific, complicated 10-person game, no solution existed. While this exception points to a fundamental incompleteness in the understanding of cooperative games, it does not invalidate the work of von Neumann and Morgenstern work, which continues to be useful both for theoretical studies and practical applications.

Game theory has become a dominant tool in economics. It has been used to regulate industry, providing, for instance, a basis for antitrust legislation and action. It has also been used to decide where best to site a new factory and to calculate the best price for new products. Game theory provides business strategists with guidance on how best to organize conglomerates and how to work cooperatively within their industries. Outside economics, game theory has been used to explain evolutionary biology and to formulate strategies to curb epidemics, encourage immunization, and test new medicines. In government and politics, game theory has been helpful in creating policies and strategies for voting, forming coalitions, and moderating the deleterious effects of majority rule. Attorneys have applied game theory to decide when to use their right to dismiss prospective jurors, and laws related to the fair distribution of inheritances have been formulated using game theory analyses. Game theory was seriously applied to philosophy as early as 1955.

Experimental economics, a growing field important to understanding commerce on the Internet, got its first foothold thanks to game theory. Von Neumann and Morgenstern's expected utility theory inspired serious testing as early as 1951. These experiments led to new theories in economics and extended the range and techniques of empirical testing in economics.

In 1994, the Nobel Prize for economics went to John Nash, John Harsanyi (1920- ), and Reinhard Selten (1930- ) for their contributions to game theory. Nash was honored for his investigations into noncooperative games and the results of seeing into an opponent's strategy. Harsanyi made original contributions to understanding dynamic strategic interactions; Selten demonstrated how games with incomplete information, where players don't know each other's objectives, could be analyzed; and both have provided mathematical proofs for game theories.

PETER J. ANDREWS