Game Theory by David K. Levine

article submitted to the Nature Publishing Group, Encyclopedia of Cognitive Science

Keywords: non-cooperative, game theory, strategy, Nash equilibrium, social situations

Article Definition: Game theory is the mathematical study of human interactions described by rules of play and alternative choices.

Overview

Situations economists and mathematicians call games psychologists call social situations. While game theory has applications to "games" such as poker and chess, it is the social situations that are the core of modern research in game theory. Game theory has two main branches: Non-cooperative game theory models a social situation by specifying the options, incentives and information of the "players" and attempts to determine how they will play. Cooperative game theory focuses on the formation of coalitions and studies social situations axiomatically. This article will focus on non-cooperative game theory.

Game theory starts from a description of the game. There are two distinct but related ways of describing a game mathematically. The extensive form is the most detailed way of describing a game. It describes play by means of a game tree that explicitly indicates when players move, which moves are available, and what they know about the moves of other players and nature when they move. Most important it specifies the payoffs that players receive at the end of the game.

Strategies

Fundamental to game theory is the notion of a strategy. A strategy is a set of instructions that a player could give to a friend or program on a computer so that the friend or computer could play the game on her behalf. Generally, strategies are contingent responses: in the game of chess, for example, a strategy should specify how to play for every possible arrangement of pieces on the board.

An alternative to the extensive form is the normal or strategic form. This is less detailed than the extensive form, specifying only the list of strategies available to each player. Since the strategies specify how each player is to play in each circumstance, we can work out from the strategy profile specifying each player's strategy what payoff is received by each player. This map from strategy profiles to payoffs is called the normal or strategic form. It is perhaps the most familiar form of a game, and is frequently given in the form of a game matrix:

This matrix is the celebrated Prisoner's Dilemma game. In this game the two players are partners in a crime who have been captured by the police. Each suspect is placed in a separate cell, and offered the opportunity to confess to the crime. The rows of the matrix correspond to strategies of the first player. The columns are strategies of the second player. The numbers in the matrix are the payoffs: the first number is the payoff to the first player, the second the payoff to the second player. Notice that the total payoff to both players is highest if neither confesses so each receives 5. However, game theory predicts that this will not be the outcome of the game (hence the dilemma). Each player reasons as follows: if the other player does not confess, it is best for me to confess (9 instead of 5). If the other player does confess, it is also best for me to confess (1 instead of 0). So no matter what I think the other player will do, it is best to confess. The theory predicts, therefore, that each player following her own self-interest will result in confessions by both players.

Equilibrium

The previous example illustrates the central concept in game theory, that of an equilibrium. This is an example of a dominant strategy equilibrium: the incentive of each player to confess does not depend on how the other player plays. Dominant strategy is the most persuasive notion of equilibrium known to game theorists. In the experimental laboratory, however, players who play the prisoner's dilemma sometimes cooperate. The view of game theorists is that this does not contradict the theory, so much as reflect the fact that players in the laboratory have concerns besides monetary payoffs. An important current topic of research in game theory is the study of the relationship between monetary payoffs and the utility payoffs that reflect players' real incentive for making decisions.

By way of contrast to the prisoner's dilemma, consider the game matrix below:

This is known as the Battle of the Sexes game. The story goes that a husband and wife must agree on how to spend the evening. The husband (player 1) prefers to go to the ballgame (2 instead of 1), and the wife (player 2) to the opera (also 2 instead of 1). However, they prefer agreement to disagreement, so if they disagree both get 0. This game does not admit a dominant strategy equilibrium. If the husband thinks the wife's strategy is to choose the opera, his best response is to choose opera rather than ballgame (1 instead of 0). Conversely, if he thinks the wife's strategy is to choose the ballgame, his best response is ballgame (2 instead of 0). While in the prisoner's dilemma, the best response does not depend on what the other player is thought to be doing, in the battle of the sexes, the best response depends entirely on what the other player is thought to be doing. This is sometime called a coordination game to reflect the fact that each player wants to coordinate with the other player.

For games without dominant strategies the equilibrium notion most widely used by game theorists is that of Nash equilibrium. In a Nash equilibrium, each player plays a best response, and correctly anticipates that her opponent will do the same. The battle of the sexes game has two Nash equilibria: both go to the opera, or both go to the ball game: if each expects the other to go to the opera (ballgame) the best response is to go to the opera (ballgame). By way of contrast, one going to the opera and one to the ballgame is not a Nash equilibrium: since each correctly anticipates that the other is doing the opposite, neither one is a playing a best response.

Games with more than one equilibrium pose a dilemma for game theory: how do we or the players know which equilibrium to choose? This question has been a focal point for research in game theory since its inception. Modern theorists incline to the view that equilibrium is arrived at through learning: people have many opportunities to play various games, and through experience learn which is the "right" equilibrium.

Mixed Strategies

While the battle of the sexes has too many equilibria, what about the game below?

You may recognize this game as the Matching Pennies game. There is, however, a more colorful story from Conan Doyle's Sherlock Holmes story The Last Problem. Moriarity (player 2) is pursuing Holmes (player 1) by train in order to kill Holmes and save himself. The train stops at Canterbury on the way to Paris. If both stop at Canterbury, Moriarity catches Holmes and wins the game (-1 for Holmes, 1 for Moriarity). Similarly if both stop at Paris. Conversely, if they stop at different places, Holmes escapes (1 for Holmes and -1 for Moriarity). This is an example of a zero sum game: one player's loss is another player's gain. In the story, Holmes stops at Canterbury, while Moriarity continues on to Paris. But it is easy to see that this is not a Nash equilibrium: Moriarity should have anticipated that Holmes would get off at Canterbury, and so his best response was to get off also at Canterbury. As Holmes says "There are limits, you see, to our friend's intelligence. It would have been a coup-de-maître had he deduced what I would deduce and acted accordingly." However, this game does not have any Nash equilibrium: whichever player loses should anticipate losing, and so choose different strategy.

What do game theorists make of a game without a Nash equilibrium? The answer is that there are more ways to play the game than are represented in the matrix. Instead of simply choosing Canterbury or Paris, a player can flip a coin to decide what to do. This is an example of a random or mixed strategy, which simply means a particular way of choosing randomly among the different strategies. It is a mathematical fact, although not an easy one to prove, that every game with a finite number of players and finite number of strategies has at least one mixed strategy Nash equilibrium. The mixed strategy equilibrium of the matching pennies game is well known: each player should randomize 50-50 between the two alternatives. If Moriarity randomizes 50-50 between Canterbury and Paris, then Holmes has a 50% chance of winning and 50% chance of losing regardless of whether he choose to stop at Canterbury or Paris. Since he is indifferent between the two choices, he does not mind flipping a coin to decide between the two, and so there is no better choice than for him to randomize 50-50 himself. Similarly when Holmes is randomizing 50-50, there is no better choice for Moriarity to do the same. Each player, correctly anticipating that his opponent will randomize 50-50 can do no better than to do the same. So perhaps Holmes (or Conan Doyle) is not such a clever game theorist after all.

Mixed strategy equilibrium points out an aspect of Nash equilibrium that is often confusing for beginners. Nash equilibrium does not require a positive reason for playing the equilibrium strategy. In matching pennies, Holmes and Moriarity are indifferent: they have no positive reason to randomize 50-50 rather than doing something else. However, it is only an equilibrium if they both happen to randomize 50-50. The central thing to keep in mind is that Nash equilibrium does not attempt to explain why players play the way they do. It merely proposes a way of playing so that no player would have an incentive to play differently. Like the issue of multiple equilibria, theories that provide a positive reason for players to be at equilibrium have been one of the staples of game theory research, and the notion of players learning over time has played a central role in this research. 

Glossary:

Extensive form game – description of a game by specifying the order of moves and information available to players, as well as the payoffs

Strategy – a specification of how to play the game in every contingency

Mixed strategy – a random choice of strategy

Normal form game – description of a game by specifying the strategies and payoffs

Best response – any strategy that yields the highest possible payoff in response to the strategy of other players

Dominant strategy equilibrium – strategy profile in which each player plays best-response that does not depend on the strategies of other players

Nash equilibrium – strategy profile in which each player plays a best-response to the strategies of other players

Reading List:

K. Binmore, Fun and Games: A Text on Game Theory, D.C. Heath, 1992.

H. Bierman and L. Fernandez, Game Theory with Economic Applications Addison-Wesley, 1993.

A. K. Dixit and B. Nalebuff, Thinking Strategically, Norton, 1991.

A. K. Dixit and Susan Skeath, Games of Strategy, WW Norton and Co, 1999.

D. Fudenberg and D. K. Levine, The Theory of Learning in Games, MIT Press, 1998.

D. Fudenberg and J. Tirole, Game Theory, MIT Press, 1991.

D. Kreps, A Course in Microeconomic Theory, Princeton University Press, 1990.

R. Luce and H. Raiffa, Games and Decisions, John Wiley and Sons, 1857.

R. Myerson, Game Theory: Analysis of Conflict, Harvard University Press

M. J. Osborne and A. Rubinstein, A Course in Game Theory, MIT Press, 1994.