Game theory is an application of mathematical logic to decision-making in games and, by extension, to economics, politics, military conflicts, and biology. The goal of game theory is to find the optimal strategy for one player to use when his opponent also plays optimally. A strategy may incorporate randomness, in which case it is referred to as a mixed strategy.

 

History of game theory

Early ideas of game theory can be found in writings throughout history as diverse as the Bible and works by René Descartes, Sun Tzu (author of the 2,400-year-old The Art of War), and Charles Darwin. The basis of modern game theory is an outgrowth of several books that deal with related subjects such as economics and probability. These include Augustin Cournot's Researches into the Mathematical Principles of the Theory of Wealth (1838), which gives an intuitive explanation of what would eventually be formalized by John Nash as Nash equilibrium; Francis Edgeworth's Mathematical Psychics, which explored the notion of competitive equilibria in a two-type (or two-person) economy; and Emile Borel's Algebre et calcul des probabilites (1927), which gave the first insight into mixed strategies.¹

 

Game theory finally came of age through the efforts of two European immigrants to the United States working at the Institute of Advanced Studies in Princeton. Around 1940, the idea of the utility function was taken up by John von Neumann, who had been forced to flee his native Hungary when the Nazis invaded, and the economist Oskar Morgenstern (1902-1976), who had left Austria because he loathed the National Socialists. In Princeton the two immigrants worked together on what they initially thought would be a short paper on the theory of games, but that kept growing until it finally appeared in 1944 as an opus of 600 pages with the title Theory of Games and Economic Behavior.²

 

Utility function

The lesson of the St. Petersburg paradox is that people do not play games as if they are maximizing the expected monetary value they receive. However, certain rationality assumptions about the way people behave, known as the von Neumann and Morganstern axioms, imply that people do act as though they are maximizing something. This "something" is often referred to as a utility function.

 

Types of games

In singular games (e.g., solitaire) the player's strategy is determined solely by the rules. In dual games (e.g., chess, football) one side's strategy must take into account the possible strategies of the other. Dual games are usually zero-sum: one side's gain exactly equals the other's loss. In practical situations, however, they may be non-zero-sum, as where two conflicting nations negotiate a truce that benefits both. Two major strategies are available to players of dual games: the minimax, in which a player evaluates his probable maximum loss and attempts to minimize it; and the maximin, in which a player evaluates his probably minimum gain and attempts to maximize it. Von Neumann showed in his minimax theorem (first stated in 1928) that, since, statistically, minimax and maximin strategies negate each other, most dual games are not worth playing in that their outcome is determined solely by the rules.

 

In plural or n-person games (e.g., poker), an individual's gain does not necessarily imply another's loss; and more complex considerations must affect each player's choice of action. More over, the outcome may be affected by the formation of coalitions, possibly reducing the n-person game to a dual one.

 

Zero-sum game

a zero-sum game is a game in which a win for one player results in an equal but opposite loss for the other players. The theory of zero-sum games is very different from that of non-zero-sum games because an optimal solution can always be found.

 

In a two-person zero-sum game, the payoff to one player is the negative of that to the other. Many common card and board games, such as poker and chess are zero sum: one player wins, another loses. According to von Neumann's theory of games, every zero sum game has a value. Each player can guarantee himself or herself this value against any play of an opponent, and can prevent the other player from doing any better than this. The outcomes of a two-player zero-sum game can be shown in the form of a matrix in which one player corresponds to the rows and the other the columns. The entries in the matrix are the payoffs to the row player.

 

Glossary of game theory
categorical game	A game in which a tie is impossible
finite game	A game in which each player has a finite number of moves and a finite number of choices at each move
futile game	A game that allows a tie when played properly by both players
impartial game	A game in which the possible moves are the same for each player in any position
mixed strategy	A collection of moves together with a corresponding set of weights which are followed probabilistically in the playing of a game
partisan game	A game for which each player has a different set of moves in any position
payoff matrix	An m × n matrix that gives the possible outcome of a two-person zeros-sum game when player A has m possible moves and player B has n moves
strategy	A set of moves that a player plans to follow while playing a game
zero-sum game	A game in which players make payments only to each other. One player's loss is the other player's gain, so the total amount of "money" available is constant

 

References

1. Borel, Emile. "Algebre et calcul des probabilites," Comptes Rendus Academie des Sciences, Vol. 184, 1927.
2. Neumann, J. von and Morgenstern, O. Theory of Games and Economic Behavior. New York: Wiley, 1964.