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
