This document is written as an intuitive and non-technical introduction for anyone interested in the way economists analyse strategic behaviour.
Readers with no background in economics or game theory are encouraged to start with the basic concepts and language used by game theorists. Subsequent sections explain the principles underpinning key solution concepts for static games (dominance and Nash equilibrium) and dynamic games (backward induction and subgame perfection).
These solution concepts are drawn on to inform a series of worked examples. The examples have been chosen to illustrate how insights from game theory can help illuminate behaviour in a wide range of familiar situations.
The basic goal of game theory is to be able to understand and predict the outcome of strategic interactions. For our purposes, a game consists of:
The players might be individuals, teams, firms, or even governments. Each player will typically have several possible strategies, each describing a different set of actions to take during the game. The game's payoffs depend on the combination of strategies chosen by the players. Crucially, a player's payoff depends not only his choice of strategy, but also on the strategies chosen by the other players in the game.
We will be looking at non-cooperative games, where each player cares only about their own payoff (with a higher payoff always being better). At a minimum, we would like to be able to identify which outcomes (if any) will never occur. If possible, we would like to be able to predict with a reasonable degree of confidence how a non-cooperative game will be played.
We will make two basic assumptions about the players:
By rational, we mean that a player is motivated only to maximise their own payoff. By common knowledge, we mean that everyone knows that everyone is rational. Moreover, everyone knows that everyone knows that everyone is rational, and everyone knows that everyone knows that everyone knows, and so on. Although strong, these assumptions provide the basic structure necessary to begin analysing how non-cooperative games will be played.
The classic way to describe a game is to draw its normal form.
A typical normal form game, with two players each choosing from two possible actions, looks like this:
| Player 2 | |||
| L | R | ||
| Player 1 | U | 3,1 | 2,2 |
| D | 4,5 | 6,0 | |
Here the rows represent the choices available to Player 1, and the columns the choices available to Player 2. The possible payoffs are listed as pairs of numbers. By convention, the payoff to Player 1 is listed first in each pair. Each player chooses once from two possible actions, so each has two possible strategies. As there are four possible combinations of strategies, there are four sets of payoffs.
In this game, each player chooses an action without knowing the choice of his opponent. For example, if Player 1 chooses D and Player 2 chooses L, then Player 1 will receive a payoff of 4 and Player 2 will receive a payoff of 5. In shorthand, (D,L) corresponds to a payoff of (4,5).
For games with several stages of play, it is often more convenient to draw the game in extensive form.
A typical extensive form game, where Player 1 chooses first, looks like this:
Here the game is read from top to bottom. Each node is labelled according to the player who has the move, with their possible actions labelled on the lines connecting the nodes. When a line ends without reaching another node, the game ends and the players receive the specified payoffs.
In this game, Player 2 chooses an action after observing Player 1's choice of L or R. For example, if Player 1 chooses R then Player 2 has a choice between C or D. If Player 2 chooses C, then Player 1 will receive a payoff of 2 and Player 2 will receive a payoff of 4. In shorthand, (R,C) corresponds to a payoff of (2,4).
To capture sitations where players choose actions without knowing their precise location in the game tree, we use information sets.
A typical game in which Player 2 chooses an action without knowing the choice made by his opponent looks like this:
Here a dashed line indicates a player's information set. When that player has the move, he does not know which of the nodes in his information set has been reached. Each node in the infomation set has the same set of possible actions (or else a player could work out their location from the choice of actions open to them).
In this game, Player 2 must choose between L and R without knowing whether Player 1 has chosen U or D.
Careful inspection will reveal that this example is an extensive form version of the normal form game we met earlier. The list of players, their possible strategies and the corresponding list of payoffs are the same. Of course, we could have drawn the extensive form differently (starting with Player 2 at the initial node) without changing the fundamental nature of the game. In general:
We begin with static games, where each player independently chooses a single action at the outset (the game has one stage). There is no scope for one player to observe his opponents' choices before deciding how to play.
For an individual player choosing how to play, one strategy dominates another if it delivers higher payoffs regardless of the strategies chosen by his opponents. It is immediately apparent that:
If a player knows his opponent is rational, and one if his opponent's strategies is dominated by another, he can safely assume his opponent will never choose it. The dominated strategy can effectively be deleted from the game. This may leave one of the player's own strategies dominated, so in turn it can also be deleted. Because we have assumed rationality is common knowledge, this iterated deletion may proceed indefinitely, until there are no further dominated strategies. In some circumstances, this will leave just one way to play the game.
| Player 2 | |||
| L | R | ||
| Player 1 | U | 3,1 | 7,2 |
| D | 5,0 | 6,5 | |
In this game, L is dominated by R, as it delivers a higher payoff regardless of Player 1's choice of U or D. When the L column is deleted, D is dominated by U. This leaves (U,R) as the only combination to survive iterated deletion of dominated strategies.
In addition to deleting strictly dominated strategies, we might also consider deleting strategies that are weakly dominated. One strategy weakly dominates another if it always delivers equal or higher payoffs, regardless of the strategies chosen by other players. Iterated deletion of weakly dominated strategies can help narrow the set of possible solutions to the game. However, when working with weak dominance, the order of deletion matters. As a result, many people consider iterated deletion of weakly dominated strategies an unattractive solution concept.
To sum up, iterated deletion of (weakly) dominated stragies can be helpful in some circumstances, but is not guaranteed to find a unique solution. More importantly, many games do not contain any dominated strategies - so iterated deletion offers no clues about their likely outcome.
The Nash equilibrium concept is named after John Nash, the Nobel prize-winning mathematician and economist (played by Russell Crowe in Ron Howard's A Beautiful Mind).
The core idea is to look for a set of strategies (one for each player), such that every player's strategy is a best response to the strategies of their opponents. Put another way, when a set of strategies constitute a Nash equilibrium, no player has an incentive to unilaterally deviate by playing differently. If, before the game, players could agree to play a set of Nash equilibrium strategies, each would find it in his interest to keep his part of the agreement. This property has led some to describe Nash equilibria as self-enforcing.
| Player 2 | |||
| L | R | ||
| Player 1 | U | 5,6 | 3,2 |
| D | 0,2 | 4,3 | |
In this game it is easy to see that there are no dominated strategies. There are, however, two Nash equilibria. If Player 1 chooses U then Player 2's best reponse is to choose L. And if Player 2 chooses L then Player 1's best response is to choose U. So (U,L) is a Nash equilibrium, and nets payoffs of (5,6). By the same reasoning (D,R) also constitutes a Nash equilibrium.
As this example illustrates, a game can have more than one Nash equilibrium. And some games may appear to have no Nash equilibria. So far, however, we have only dealt with pure strategies - in the game above, for example, Player 1 can choose either U or D. Nash's key insight was to examine what happens when players are allowed to choose mixed strategies. A mixed strategy is one in which several pure strategies are each chosen with a fixed probability. A mixed strategy for Player 1 in the above game might be to play U with probability 1/3, and D with probability 2/3. Nash proved the following result:
Here a finite game means one with a finite number of players, each with a finite number of strategies. This basic existence result is incredibly powerful, as it presents the possibility to find at least one possible solution to any finite game.
In dynamic games, play proceeds in a seqence of stages. We say a player has the move when it is his or her turn to choose an action. In a dynamic game, there is often scope for one player to observe another before deciding how to play. This allows dynamic games to describe more sophisticated situations than is possible using static analysis.
In a special class of dyamic games called repeated games, the same static game is played several times in a row.
In a game with several stages, it may be possible to elimate strategies by working backward from the final stage. This procedure is called backward induction.
In this game, Player 2 chooses an action after observing Player 1's choice of L or R. If Player 2 finds himself at the left node he will choose B (as 3 is better than 2). If he finds himself at the right node, he will choose C (as 4 is better than 1). As we can be sure Player 2 will not choose A or D, we can safely delete them from the game tree. This clearly leaves Player 1 prefering to choose L. The backward induction solution to this game is (L,C) which nets a payoff of (2,4).
Backward induction fails in two main circumstances. First, if at any stage a player has two or more actions that deliver the same highest payoff (the payoffs are tied), backward induction cannot predict which he will choose. Second, if we reach an information set containing more than one node, there may not be a clear best action for the player concerned. This second circumstance is one in which the player has imperfect information about what happened in the game before he was given the move.
Nevertheless, backward induction can often provide strong predictions about how a game will be played. Moreover, when certain conditions are met, it can be used to isolate a single pattern of play between rational players:
In some dynamic games there are Nash equilibria that rely on empty threats.
This game has two pure strategy Nash equilibria - (In,A) and (Out,B). It is straightforward to verify (In,A) as a Nash equilibrium, but (Out,B) raises a subtle complication. If Player 2 is choosing B then the best response for Player 1 is to choose Out. And if Player 1 is choosing Out, then Player 2 will not get the move - so B is indeed a legitimate best response. However, if given the move, Player 2 will clearly prefer to choose A. His threat to play B if given the move is not credible.
To deal with this sort of situation, we must first define a new concept specific to dynamic games. A subgame is any subset of the game tree starting from a singleton node (this means a subgame cannot start from an information set containing more than one node). We then look for Nash equilibrium strategies in the main game that also constitute a Nash equilibrium in every proper subgame.
In the example above, this rules out (Out,B), as B does not constitute a Nash equilibrium in the subgame starting at Player 2's node. This leaves (In,A) as the subgame perfect Nash equilibrium of this game.
Following a robbery, the two suspected culprits have been captured by the police. However, the police do not have enough evidence to fully prosecute the pair without a confession. The suspects are held in separate cells, and each offered the following deal. If both stay silent, they will convicted of a minor infraction and given a light punishment (say 1 month behind bars). If one confesses and the other stays silent, the suspect confessing to the police will be set free whilst the other will receive a very severe punishment (6 months). If both confess, their honesty will secure them both a moderate punishment (3 months).
We can write this game out in normal form, where each suspect has the choice to cooperate with the other by staying silent, or defecting by confessing to the police:
| Suspect 2 | |||
| Cooperate | Defect | ||
| Suspect 1 | Cooperate | -1,-1 | -6,0 |
| Defect | 0,-6 | -3,-3 | |
On inspection, it is clear that Defect is a dominant strategy for both suspects. For both suspects, regardless of how the other behaves, defecting by confessing to the police always nets a less severe punishment.
The core of the dilemma, however, is that if both were to stay silent they would unambiguously be better off (receiving 1 month each instead of 3). But there is no way to commit to this course of action. Even if the suspects confer before being separated and both promise to cooperate by staying silent, both have a strong incentive to defect once the game begins.
Although the equilibrium of the static game is inefficient, it may be possible to sustain cooperation if the prisoners' dilemma game is repeated several times.
If the game is repeated a finite number of times, we can find a solution using backward induction. In the final round, both players have an unambiguous incentive to defect - as there is nothing to be gained by cooperating. Now, in the penultimate round, the outcome of the final stage is known. So again there is nothing to gain by cooperating. This argument can be repeated until the first round - resulting in a prediction that players will defect in every round.
If the game is repeated an infinite (or uncertain) number of times, however, it is possible to sustain cooperation. One way to do so is for both players to operate grim trigger strategies. Both start the game by cooperating, and continue to do so unless the other player defects. If one player defects, the other punishes him by defecting in every round from then on. It is clear that if both players adopt such strategies, they will cooperate in every round.
There are many other strategies that can sustain cooperation in the infinite prisoners' dilemma. One of the most famous is the tit-for-tat strategy. With this strategy, each player starts the game by cooperating, and continues to do so unless the other defects. Defection is punished by withholding cooperation for the next round, before returning to cooperation. Experimental studies have shown tit-for-tat to be a remarkably good way to play a repeated prisoners' dilemma, beating far more complicated contingent strategies.
Two players are each given a coin and asked to place it either heads up or tails up. If both place their coin the same way up, they both win £1. If the two coins are placed different ways up, neither player wins anything.
| Player 2 | |||
| H | T | ||
| Player 1 | H | 1,1 | 0,0 |
| T | 0,0 | 1,1 | |
This game has two pure strategy Nash equilibria, (H,H) and (T,T). If player 1 chooses H then Player 2's best response is also to choose H. And if Player 2 chooses H, then H is a best response for Player 1. The same argument can be applied to show (T,T) is also a Nash equilibrium.
The problem for the players is how to coordinate on one of the two equilibria. In the absence of any further information, there is no way for one player to be sure how the other will choose to play. As a result, although (H,H) and (T,T) are Nash equilibria, there may be no a priori reason to predict either will be the actual outcome.
The matching pennies game is sometimes recast in a game known as the battle of the sexes. A man and woman are trying to choose whether to spend the evening at the football or the ballet. Both prefer to be together than apart, but the man would prefer the football whilst the woman would prefer the ballet.
| Woman | |||
| F | B | ||
| Man | F | 3,2 | 1,1 |
| B | 0,0 | 2,3 | |
The matching pennies analysis applies equally to this game. It is straightforward to see that (F,F) and (B,B) are both Nash equilbria. But without any further information, it is not clear whether the players will actually manage to coordinate their actions.
Two players attempt to outdo each other in front of their friends by playing a game of chicken. They drive toward each other at high speed, and the first to swerve aside (act chicken) is humiliated, while the other gains immense kudos as a result of their bravery. If both players swerve neither benefits, but if neither player swerves both suffer terrible consequences.
| Player 2 | |||
| Brave | Chicken | ||
| Player 1 | Brave | -99,-99 | 10,0 |
| Chicken | 0,10 | 0,0 | |
This game is very similar to the matching pennies example. There are two Nash equilibria, and in each one of the players swerves whilst the other doesn't. But it is not clear how players can coordinate on one equilibrium rather than the other. Indeed, if players are sufficiently concerned that the game might end in a crash, both are likely to act chicken. This outcome, though one we might expect from reasonable players, does not constitute a Nash equilibrium.
Two players are shown a list of ten cities:
Player 1 is allocated Paris, and Player 2 is allocated New York. The players must each write down the names of four other cities. If together their two lists name each city once and once only, each receives £100. If any city is left out or named in both lists, both players win nothing.
Any two lists that successfully partition the cities constitute a Nash equilbrium solution, as neither player can improve on his outcome by changing his list. But there are many different pairs of lists that achieve this, and the Nash criteria alone cannot help us predict which will be chosen. However, the initial allocation of Paris and New York provides a focal point for the players. Provided they both have a rudimentary grasp of geography, it may be reasonable to expect the following partition:
Indeed, experimental evidence from similar games (see Kreps 1990) suggests players do tend to coalesce around strong focal points.
Sherlock Holmes is on the train from London to the Kent coast, being pursued by Moriarty who aims to catch him and kill him. Holmes would like to get to Dover, from where he can safely reach the continent. But he can also choose to get off at Canterbury, and make his way to the continent via a different route. Holmes must choose where to get off the train, always prefering to be in a different place to Moriarty. Moriarty, who is on the next train, must also decide where to get off, always prefering to be in the same place as Holmes.
| Moriarty | |||
| D | C | ||
| Holmes | D | 0,1 | 1,0 |
| C | 1,0 | 0,1 | |
This game has no Nash equilibrium in pure strategies. In each of the four possible outcomes, at least one of the players would prefer to have made a different choice.
There is, however, a Nash equilbrium in mixed stragies. In this equilbrium, both players randomly choose C or D with probability 1/2. In this case, neither player can achieve a better expected payoff by playing in a different way.
A similar game is played out in The Princess Bride. A villain is attempting to kill the hero by posioning one of two cups. Knowing this, the hero must choose which cup to drink from.
| Villain | |||
| Cup 1 | Cup 2 | ||
| Hero | Cup 1 | -1,1 | 1,-1 |
| Cup 2 | 1,-1 | -1,1 | |
Reasoning that cup 1 (his own) is poisoned, the hero reaches for cup 2 (the villain's). But if the villain knows this will happen, he will have poisoned cup 2 - and so realising this, the hero reaches instead for cup 1. But he then realises that the villain will know this also, and so will have poisoned cup 1. But then the hero will realise this and choose cup 2, so the villain will have poisoned this cup, and so on. This neatly captures the practical problems associated with assumptions of rationality and common knowledge.
This is a classic game for two players. Each chooses either rock, paper or scissors before both reveal their choices simultaneously. Rock beats scissors, scissors beats paper, and paper beats rock. If both players make the same choice, the game is drawn.
| Player 2 | ||||
| R | P | S | ||
| Player 1 | R | 0,0 | -1,1 | 1,-1 |
| P | 1,-1 | 0,0 | -1,1 | |
| S | -1,1 | 1,-1 | 0,0 | |
There is no pure strategy Nash equilibrium in this game. For any pair of actions, ex post at least one of the players will prefer to have chosen differently. There is, however, an equilbrium in mixed strategies (where both players each choose R, P or S with probabilty 1/3).
Two pirates discover 100 gold coins. The first pirate proposes a division of the treasure between the two of them. The second can either accept the division, or reject it. If the division is rejected, both must walk away with nothing.
There are 101 different ways to divide the treasure. This is a very large game tree, so only part of it is drawn here:
Although there are many possible divisions, the solution to this game is relatively simple. It is clear that with rational players, the first pirate will do best by proposing a division that leaves the second with just one coin. The second pirate will accept this, as accepting one coin strictly dominates rejecting it and receiving nothing (which is the only alternative). Thus the first pirate gets to keep 99 of the 100 coins.
In reality, most people in similar situations tend to propose a roughly equal split. This tendency is particularly strong when the game is repeated with alternating roles, as players attempt to build a good reputation with their opponent.
In a similar game, two players have a delicious cake to share between them. Player 1 cuts the cake into two pieces. Player 2 takes whichever piece he prefers. Player 1 then takes whatever is left.
Again, the full extensive form is too large to draw, so only part of it is illustrated:
Again there is a readily apparent solution to this game. Player 1 cuts the cake exactly in half, and Player 2 chooses a piece at random. This is a strictly dominant strategy for Player 1, because any other division will leave him with less cake (as Player 2 always takes the larger piece).
Chess is a familiar example of a highly complex strategic game. Without going fully into the rules of chess, we can specify some of the game's characteristics. Players take turns to move, so it is a dynamic game. Moreover, at every point both players know the full history of play thus far, so it is a game of perfect information. And as the game must eventually be won, lost or drawn (the game is drawn if a particular position recurs three times, or fifty moves pass without a piece being taken or a pawn moved), it is also a zero-sum finite game.
Because chess is a finite game of complete and perfect information, we can in principle find a unique solution by backward induction. To do this, we would first draw out the game tree. We would then work backward from the final nodes, at each point determining the best way to play. And we would eventually reach the beginning of the game, and be left with an optimal way to play for both players.
The problem of course is that the game tree for chess is unimaginably large. So large, in fact, that attacking chess using backward induction techniques is entirely impractical. Nevertheless, sophisticated chess software is already able to look much further down the game tree than the average human player, and thus able to win most games with ease.
Stanley Kubrick's Dr Strangelove is a black comedy about nuclear deterrents and nuclear exchange at the height of the Cold War.
The basic premise behind nuclear deterrents is the doctrine of so-called mutually assured destruction (MAD). Put simply, no country will start a nuclear exchange because doing so will lead to catastrophic retaliation.
In practice, reliance on MAD is jeapordised by the presence of human decision makers in the chain of command. Even if a country were the subject of a nuclear attack, its leaders might still recoil from a retaliation that would cost hundreds of millions of lives. This may leave pre-emptive nuclear strikes as an attractive option for some protagonists, if they do not believe their enemies will follow through on threats of retaliation.
A stylised game tree for this sort of situation is as follows:
In this game, although the strategy pairing (Peace, Retaliate if attacked) constitutes a Nash equilibrium, it relies on a threat of retaliation that lacks credibility. For if Russia is attacked, it prefers to do nothing rather than initiate a global nuclear holocaust. If the Americans believe there is a good chance the Russians won't retaliate, there may be an advantage to launching a preemptive strike (for a potential payoff of 6 rather than 3). Indeed, (Strike, Do nothing) is the only subgame perfect Nash equilbrium of this game.
In the fictional world inhabited by Dr Strangelove, the Russians are well aware of this problem. To combat it they link their nuclear weapons to an entirely automated system, programmed to retaliate immediately if attacked - a perfectly credible threat. In our example, this corresponds to deleting the Do nothing option at Russia's node. This leaves Peace as America's preferred strategy.
In the film, however, the situation rapidly unravels. Although the automated response system is in place, the Russians have not communicated its existence to the Americans. In the belief that Russian threats of retaliation are empty, a preemptive strike is launched. By the time the Americans find out that this will be met with certain retaliation, it is already too late to abort the strike. In desperation they escalate the exchange by launching further weapons, but this only hastens the inevitable catastrophic conclusion.
If you're interested in reading more about game theory and its applications, Game Theory and Economic Modelling by David Kreps offers a good and accessible introduction to the topic. More advanced readers will find an excellent treatment in A Primer in Game Theory by Robert Gibbons. You can also find basic game theory concepts covered in most standard undergraduate microeconomics texts.
If you think you've mastered the basics and want to try a more challenging problem have a go at this puzzle from Perplex City.