Competition and Strategy

Topic 2: Sequential Games

David Byrne

Department of Economics

University of Melbourne

Recommended reading in DS: 2nd edition, chapter 3 (p. 45–72,

77–78), or 3rd edition, chapter 3 (p. 47–72, 79–80).

1 / 41

Sequential Games

◮

Sequential move games are played by two or more players for two or more periods

◮

Ultimatum game is a sequential game

◮

Chess is a sequential game

◮

Paper-Rock-Scissors is not a sequential game

2 / 41

Representing Sequential Games: Game Trees

◮

Sequential move games are normally presented as game trees.

◮

Game trees are often referred to as extensive form games.

◮

Think of these as a possible paths of players’ actions and outcomes ◮

Game trees reveal the players, their actions, the timing of their actions and the payoffs.

◮

Game trees vs. decision trees: Game trees are joint decision trees for all the players in a game.

3 / 41

Sir Richard Branson

4 / 41

Game Trees

Example

Consider the phone company choice game represented by the following game tree with two players, Husband (H) and Wife (W):

H

Telstra

4, 4

Telstra

W

Virgin

3, 5

Virgin

W

Telstra

4, 3

Virgin

6, 6

So if the actions are H:{Telstra} and W:{Virgin}, H gets 3 and W gets 5. That is, wife prefers Virgin if husband prefers Telstra.

5 / 41

Game Trees

Game characteristics

◮

This is a non-zero sum game.

If actions are H:{Telstra} and W:{Virgin}, then H gets 3 and

W gets 5

If actions are H:{Virgin} and W:{Virgin}, then H gets 6 and

W gets 6

So we see pay-offs from actions do not result in one player’s gain = other player’s loss. Here, both do better if H:{Virgin} and W:{Virgin} then if H:{Telstra} and W:{Virgin}!

◮

This is a complete information game.

W sees all possible previous moves by all other players (H)

H can anticipate any reaction of W to H’s choice

6 / 41

Game Trees

Characterization of a Game Tree

◮

Players: Two players – Husband (H) and Wife (W)

◮

Nodes: Three decision nodes and four terminal nodes

◮

Timing: Sequential, player H moves first, then player W

◮

Outcomes and Payoffs: At each terminal node, payoffs for all players are listed for that sequence of moves. They are normally listed in the order of who moves first.

◮

Actions are moves taken at decision nodes, where each branch represents a possible action.

◮

Strategies: action plans that describe a player’s actions at all of his/her decision nodes

7 / 41

2 Things that Drive Your Lecturer Nuts

STRATEGIES ARE ACTION PLANS!

H

Telstra

4, 4

Telstra

W

Virgin

3, 5

Virgin

W

Telstra

4, 3

Virgin

6, 6

◮

Example strategy: H Virgin) and W is (Virgin, Telstra)

◮

They are NOT payoffs (i.e, (4,3) from the example strategy)

◮

They are NOT the sequence of decisions implied by action plans (i.e., (Virgin, Telstra) from the example strategy)

8 / 41

Game Trees

Backward Induction

◮

A subgame is a game comprising a portion of a larger game, starting at a non-initial node of the larger game.

◮

Backward induction asks to start at the final subgames, and to work backwards towards the initial node.

(That’s why backward induction is also known as rollback.)

◮

Rational player selects in every subgame the move that maximises their own payoff.

9 / 41

Game Trees

Example

The phone company choice game has three subgames:

◮

The two subgames for each of the possible (W) choices

◮

The one subgame for the one (H) choice (i.e., the entire game!) H

Telstra

4, 4

Telstra

W

Virgin

3, 5

Virgin

W

Telstra

4, 3

Virgin

6, 6

10 / 41

Game Trees

Backward Induction

◮

To start solving the phone company game, consider the two final subgames:

When player H has chosen Telstra, player W gets payoff 4 if she chooses Telstra and 5 if she chooses Virgin.

When Player H has chosen Virgin, player W gets payoff 3 if she chooses Telstra and 6 if she chooses Virgin.

H

Telstra

4, 4

◮

Telstra

W

Virgin

3, 5

Virgin

W

Telstra

4, 3

Virgin

6, 6

Hence, the best strategy of player W is (Virgin, Virgin)

11 / 41…