5. Sequential move two-person games

Recall the Battle of the Sexes example of a non-zero sum game. A husband and wife wished to go to the cinema, and disagreed on the film to see, but both get no pleasure from being apart. The payoff matrix was given by

R A
R \((1,2)\) \((0,0)\)
A \((0,0)\) \((2,1)\)

Example 5.1

Now suppose that player 1 chooses first, and that player 2 then makes their choice knowing this decision.

Example completed by hand in the lecture

We have found 3 Nash equilibria in the normal form, but are they all really rational?

The equilibrium \((R,r'r)\) says that player 2 will pick Romance regardless of player 1’s choice — but if player 1 picked Action this would be foolish. The equilibrium \((A,a'a)\) is similar.

The problem here is that the strategy chosen relies on the fact that the foolish option does not occur (as the equilibrium state does not include that scenario).

We will introduce a more refined notion of rational strategies (and of Nash equilibria) to deal with this problem.

Recall the extensive form representation of a game, and assume that at each node there are only finitely many possible actions.

Sequential rationality is an extension of the concept of rationality: we do not assume that players select best reponses at the beginning of the game but instead that they demonstrate rationality whenever that are called on to make a decision.

Definition 5.2

An optimal strategy for a sequentially rational player should maximize his or her expected payoff, conditional on every information set at which this player has a move.

That is, player \(i\)’s strategy should specify an optimal action from each of the player \(i\)’s information sets, even those that player \(i\) does not believe will be reached in the game.

Perhaps the simplest way to represent sequential rationality is through a procedure that identifies an optimal action for each information set by working backwards in the game tree.

Consider for instance a game with perfect information (which has only singleton information sets).

One can start by looking at the decision nodes that are immediate predecessors of only terminal nodes. At such a decision node, the game ends after the relevant player makes the choice and to determine the optimal action there is no need to think of the behaviour of the other players.

Essentially the player of the move has a choice among some terminal nodes, and we assume she will select the payoff-maximizing action (all other actions are dominated).

The procedure then moves to evaluate decision nodes whose immediate successor are either terminal nodes or the nodes we have already evaluated.

From each node in this second class, the payoff consequences are clear because the player of the move can anticipate how other players will behave later. The process continues all the way back to the initial node.

Definition 5.3

The process of analyzing a game from the end to the beginning is called backward induction. At each decision node, one strikes from consideration all dominated actions, given the terminal nodes that can be reached through the play of action identified at successor nodes.

Example 5.1 (revisited)

In Example 5.1 we see that using backward induction player 2 will reject the option \(a'\) and the option \(r\).

Then player 1 sees only the two possibilities (\(Rr'\)) and (\(Aa\)) and chooses the latter to maximise their payoff, and so the only sequentially rational strategies are \(A\) for player 1 and \(r'a\) for player 2.

By considering the process of backward induction for games with perfect information, it is is easy to prove

Theorem 5.4: (Zermolo’s Theorem)

Any finite game of perfect information has a backward induction solution that is sequentially rational. Further, if no two terminal nodes prescribe the same payoffs to any player then this solution is unique.

Our backwards induction procedure ensures that each player will necessarily play a best response to the actions of the players who follow them, and so we obtain

Corollary 5.5

Any finite game of perfect information has at least one sequentially rational pure Nash equilibrium. Further, if no two terminal nodes prescribe the same payoffs to any player then this is the unique sequentially rational pure Nash equilibrium.

We still have to worry about situations where we have incomplete information. For this it will be useful to have the notion of a subgame.

Definition 5.6

A subgame of an extensive game is a subtree of the game tree that satisfies

  • The subtree begins a a decision node.
  • The information set containing this inital decision node contains no other decision nodes.
  • The sub-tree contains all of the decision nodes that follow the initial node, and no others.

The second condition is crucial, and means that the player who first plays in the sub game knows all the decisions made up to this point.

We will show how subgames can be used to give a suitable refinement of Nash equilibria that are sequentially rational.

We can now give the desired refinement of Nash equilibrium that incorporates sequential rationality.

Definition 5.7

A subgame perfect Nash equilibrium is a Nash equilibrium in which the behaviour specified in each subgame is a Nash equilibrium for that subgame.

Note that this applies even to subgames that are not reached during a play of the game using Nash equilibrium strategies.

Example 5.1 (again)

We found three pure Nash equilibria: \((R.r'r)\), \((A,r'a)\), and \((A,a'a)\). Only \((A,r'a)\) is a subgame perfect Nash equilibrium.

This definition extends our previous methods for sequentially rational solutions to game trees with imperfect information.

Example 5.8

Consider the game tree shown.

Example completed by hand in the lecture

Theorem 5.9

Every finite extensive game has a subgame perfect Nash equilibrium.