Extensive forms

Sequential games

A sequential game is a game where one

player chooses his action before the
others choose theirs.
We say that a game has perfect
information if all players know all moves
that have taken place.
A game with perfect information is a type of game
where all players have complete knowledge about
the game’s state at every point in time, with no
information hidden from any player.

This means that each player is fully aware of all

past events and actions in the game.
Here are some examples of games with perfect information:
Chess: In chess, both players can see the entire board and all the
pieces at all times. They are aware of all the moves that have been
made previously.
Checkers: Similar to chess, in checkers, the entire board and all the
pieces are visible to both players at all times. All past moves are
known to both players.
Go: Go is another example where the entire board is visible to both
players, and they are aware of all past moves.

These games contrast with games of imperfect information, where

some information is hidden from players. Examples of such games
include poker and bridge, where players cannot see each other’s
cards.
Sequential games
Strategic and extensive form

Strategic form:
Players move simultaneously
There are represented by matrices

Extensive form:
Players move sequentially
There are represented by game trees
Dating game

We may play the dating game as a

sequential game. In this case, one player,
say Roy, makes a choice before the other.
Connie
Football Drama
Football (20,5) (0,0)
Roy
Drama (0,0) (5,20)
Roy wants to go to a football match, F, but Connie wants to
go to the drama, D.
If they both choose F, then Roy gets a payoff of 20, and
Connie gets 5, and if they both choose D, then Roy gets 5 and
Connie gets 20.
But if they choose different events, both receive a payoff of 0.
Each must purchase their ticket without knowing what the
other is doing. [Connie forgot to charge her cell phone.]

Connie
Football Drama
Football (20,5) (0,0)
Roy
Drama (0,0) (5,20)
Roy wants to go to a football match, F, but Connie wants to
go to the drama, D.
If they both choose F, then Roy gets a payoff of 20, and
Connie gets 5, and if they both choose D, then Roy gets 5 and
Connie gets 20.
But if they choose different events, both receive a payoff of 0.
Each must purchase their ticket without knowing what the
other is doing. [Connie forgot to charge her cell phone.]

Connie
Football Drama
Football (20,5) (0,0)
Roy
Drama (0,0) (5,20)
Suppose both Roy and Connie decide to go to the football match.
Is that an equilibrium? Connie
Football Drama
Football (20,5) (0,0)
Roy
Drama (0,0) (5,20)
Given that Connie has chosen F, what happens to Roy if he deviates from F
to D ?
• Answer: He would get 0 instead of 20.
• So, F is Roy's best response to Connie's F.
Given that Roy has chosen F, what happens to Connie if she deviates from
F to D ?
• Answer: She would get 0 instead of 5.
• So, F is Connie's best response to Roy's F.
Result: the strategy profile (F, F) IS an equilibrium!
Likewise, (D, D) is also an equilibrium.
Suppose Roy goes to football and Connie goes to the drama (F, D).
Is (F, D) an equilibrium?
Connie
Football Drama
Football (20,5) (0,0)
Roy
Drama (0,0) (5,20)

Given that Connie has chosen, D, what happens to Roy if he deviates from
F to D?
Answer: he would get 5 instead of 0,
so he would deviate.
F is NOT Roy's best response to Connie's D.
Therefore, (F, D) is not an equilibrium!
We do not have to ask if Connie would also deviate.
Likewise, (D, F) is NOT an equilibrium.
 Previously, we have analyzed static games where all players move
simultaneously.
• Roy wants to attend a football match, F, but Connie wants to
participate in the drama D.
• If they both do F, then Roy gets payoff 20, and Connie gets 5,
and if they both do D, then Roy gets 5, and Connie gets 20.
• But if they do different things, then both get 0.
Both must choose their strategies simultaneously, without
knowing what the other has done.
There are two Nash equilibria: (F, F) and (D, D).

Connie
Football Drama
Football (20,5) (0,0)
Roy
Drama (0,0) (5,20)
We will examine dynamic games in which players move at
different times.
Suppose that the players move at different times, first one and
then the other.
For example, suppose that.
Roy moves first: He buys a ticket for the football match or the
drama.
He shows Connie his ticket so she knows what he has done.
Then Connie moves: she buys her ticket for the football match or
the drama.
Connie
Football Drama
Football (20,5) (0,0)
Roy
Drama (0,0) (5,20)
What would happen in this game?
Connie
Football Drama
Football (20,5) (0,0)
Roy
The answer is clear! Drama (0,0) (5,20)
Roy (the selfish (自私) beast) will choose football F ...
and “force” (强迫) Connie to choose football F.
(F, F) still looks like a Nash equilibrium.
We know they won't choose (D, D), but is (D, D) still an
equilibrium?
To find out, we must model strategies properly.
If Roy moves first, and Connie sees the result before she moves, ...
... then the matrix above does not correctly represent the game.
A strategy is a complete plan of action that specifies what a
player will do in every circumstance that Roy can observe.
Connie
Football Drama
Football (20,5) (0,0)
Roy
Drama (0,0) (5,20)

From what strategies does Roy choose?

• F and D (as before).
What about Connie? What are her strategy choices?
• F and D are NOT strategies for Connie.
• A strategy is a plan that might tell you to do different things in
each situation you know about.
• Connie knows whether Roy has bought F or D.
• So, her strategy must reflect her knowledge of his action
The dynamic Battle of the Sexes can be represented as follows:
Connie
Always F Copy Opposite Always D
Roy F (20,5) (20,5) (0,0) (0,0)
D (0,0) (5,20) (0,0) (5,20)
Connie's possible strategy choices are the following (with my own
nicknames “I” ):
Always F: Opposite:
If he bought F, I would choose F. If he bought F, I will choose D.
If he bought D, I will choose F. If he bought D, I will choose F.
Copy: Always D:
If he bought F, I will choose F. If he bought F, I will choose D.
If he bought D, I will choose D. If he bought D, I will choose D.
These four strategies form Connie's strategy space.

Connie
Always F Copy Opposite Always D
Roy F (20,5) (20,5) (0,0) (0,0)
D (0,0) (5,20) (0,0) (5,20)

If Roy does F, then Connie's strategies Always F and Copy require

the same actions, leading to the same payoffs.
 Connie
Always F Copy Opposite Always D
Roy F {(20,5)} {(20,5)} (0,0) (0,0)
D (0,0) (5,20) (0,0) {(5,20)}
But what are the Nash equilibria of this game?
If we check each cell, we can see that there are exactly three pure-
strategy equilibria:
• (F, Always F)
• (F, Copy)
• (D, Always D)
In each equilibrium, the players have no incentive at the beginning of the
game to deviate from their chosen strategies. However, only (F, Copy) is
formed from the strategy (plans) that would be followed during the
game.
What's wrong with the strategies in the other equilibria?
Answer: They are not time-consistent ...
 Connie
Always F Copy Opposite Always D
Roy F (20,5) (20,5) (0,0) (0,0)
D (0,0) (5,20) (0,0) (5,20)

In the Battle of the Sexes example, Roy purchases his ticket first. However, if Connie
declares that she will attend the drama regardless of Roy's decision, then wouldn't Roy
feel “compelled” (被迫) to purchase a drama ticket? In this case, (D, Always D) is a Nash
equilibrium!

Maybe Roy would ignore Connie’s statement!

• Roy suspects that if he chooses F, Connie will change her mind about Always D.

• He thinks Connie might choose Always D when she plans her strategy at the beginning of
the game.

• But when it's her turn to buy a ticket, Connie may be unwilling to follow the Always D
plan if I have chosen F.

• Always D may be an “idle threat” (無謂的威脅) (that Connie will not carry out), a threat
that Roy doesn't believe.
 A New Kind of Equilibrium

In general, the Nash equilibrium does not guarantee that equilibrium

strategies will be time consistent because the Nash equilibrium
concept doesn’t eliminate idle threats.

However, there’s a special kind of Nash equilibrium that does

guarantee time-consistent equilibrium strategies:
Normal-Form and Extensive-Form Games

Games can be represented in a matrix where each row or column

represents a player's strategy, known as the normal-form game.

However, to find a subgame-perfect Nash equilibrium, we need a

different game structure called the extensive-form game.
A Different Game Model

Yes, (D, Always D) is a Nash equilibrium, but it will not occur if

both players are rational.
This is because Always D is not time-consistent, so a rational
Connie would not follow it during the game, ....
... and Roy knows he won’t.
So, if Roy moves first, she will choose F, even if Connie says She
will follow Always D.
To show this, we need a different model of the game:
The extensive-form game.
Extensive-form games are described with a tree.

The first period is at the top of the tree.

Each tree level designates a period, and the player has a

turn to move.
Roy
Football Drama

Connie Connie
Football Drama Football Drama

(20,5) (0,0) (0,0) (5,20)

Payoffs to: (Roy,Connie)
Each branch of the tree describes an action the player
can choose.

Each node (where branches meet) describes what a

player knows before she moves

Roy
Football Drama

Connie Connie
Football Drama Football Drama

(20,5) (0,0) (0,0) (5,20)

Payoffs to: (Roy,Connie)
A strategy is a complete plan that states what action a
player should take at every one of her nodes.

Each player’s payoffs are given at the bottom of the tree.

Roy
Football Drama

Connie Connie
Football Drama Football Drama

(20,5) (0,0) (0,0) (5,20)

Payoffs to: (Roy,Connie)
Roy moves first.
• He has no information
• He can choose football ...
• or drama
Then Connie moves.
• She looks at Roy's ticket.
• She sees football ...
• or drama.
If she sees football, If she sees drama,
• she can choose football… • She can choose football ...
• or drama. • or drama.
• If she chooses football, Roy gets • If she chooses football, Roy gets 0
20 and she gets 5. and she gets 0.
• If she chooses drama, Roy gets 0 • If she chooses drama, Roy gets 5
and she gets 0. and she gets 20.
In a subgame-perfect equilibrium, (,)
all strategies are time-
consistent, ...
(F) (D)
that is, no one wants to change his
strategy during the game.

We break the game into subgames. Roy has one subgame ( , ) , the
whole thing because he cannot
Connie has two subgames:
move after he finds out what
(F) and (D) Connie did.
Each of Connie's subgames An equilibrium is subgame-
corresponds to the game he faces perfect if and only if it creates a
after discovering what Roy did. Nash equilibrium in every
subgame.
Finding the Subgame-Perfect (,)
Equilibrium
We work backwards from the last
time period to find a subgame- (F) (D)
perfect equilibrium.
This method is called backwards
induction.
What would Connie do in subgame
(F)?
• She would buy F and get 5.
• F is the Nash equilibrium of
subgame (F). We can see Connie's equilibrium
strategy (complete plan) if we look at
What would Connie do in (D)? the two subgames together.
• She would buy D and get 20. Her equilibrium strategy is Copy.
• D is the Nash equilibrium of Why?
subgame (D).
 (,)
Roy can predict that if Connie is
rational, her strategy must be Copy.
So, what does Roy do in his subgame (F) (D)
(,)?

If he buys F, Connie will

buy F, and he will get 20.
But if he buys D, Connie
will buy D, and he will get 5. (F, Copy) is a unique subgame
So Roy's Nash equilibrium strategy is perfect [time-consistent] equilibrium.
F. • (F, Copy) creates a Nash
equilibrium in every subgame.
• In (F, Copy), Roy gets 20; Connie
receives 5.
 (, )

Note that (F, Always F) is NOT a (F) (D)

subgame perfect equilibrium, ...

In Connie’s subgame (F), strategy D

is not a Nash equilibrium strategy.

If Roy had chosen F, Connie would

not have selected D.

Always D needs to be more time-

consistent.
 Roy's Advantage

• In the subgame-perfect equilibrium, Roy moves first. He

has no information.
• When Connie moves, she already knows what Roy has
done.
• Connie has the information advantage, yet Roy gets 20,
and Connie gets only 5. Why?
• Because Roy commits (承诺) before Connie gets to move.
• In business and life, commitment is a significant
advantage.
• However, in other settings, information may be a more
substantial advantage.
 We may play the dating game as a
sequential game. In this case, one player,
say Connie, chooses the other.

Connie
Football Drama

Roy Roy
Football Drama Football Drama

(20,5) (0,0) (0,0) (5,20)

Payoffs to: (Roy,Connie)
Player 1’s Payoff
 Connie
Football Drama
Football (20,5) (0,0)
Roy
Drama (0,0) (5,20)

Connie
Football Drama

Roy Roy
Football Drama Football Drama

(20,5) (0,0) (0,0) (5,20)

Payoffs to: (Roy,Connie)

Player 1’s Payoff Player 2’s Payoff

Backward induction

Connie
Football Drama

Roy Roy
Football Drama Football Drama

(20,5) (0,0) (0,0) (5,20)

Payoffs to: (Roy,Connie)
 Backward induction

Connie
Football Drama

Roy (20,5) (5,20) Roy

Football Drama Football Drama

(20,5) (0,0) (0,0) (5,20)

Solution:
Connie chooses “Drama”, and then Roy chooses “Drama.”
Payoffs: (5,20)
Backward induction

Suppose Roy chooses first.

Roy
Football Drama

Connie Connie
Football Drama Football Drama

(20,5) (0,0) (0,0) (5,20)

Payoffs to: (Roy,Connie)
 Backward induction

Roy
Football Drama

Connie (20,5) (5,20) Connie

Football Drama Football Drama

(20,5) (0,0) (0,0) (5,20)

Solution:
Roy chooses “Football”, and then Connie chooses “Football.”
Payoffs: (20,5)
 Dating game

Connie Roy
Football Drama Football Drama

(20,5) (5,20) (20,5) (5,20)

Football Drama Football Drama Football Drama Football Drama

(20,5) (0,0) (0,0) (5,20) (20,5) (0,0) (0,0) (5,20)

Payoffs: (5,20) Payoffs: (20,5)

In a dating game, the first player to choose

has an advantage.
Modified rock-paper-scissors

Modified rock-paper-scissors

Column player
Rock Scissors
Row Rock (0,0) (1,-1)
player Paper (1,-1) (-1,1)
Modified rock-paper-scissors

Modified rock-paper-scissors

Column player
Rock Scissors
Row Rock (0,0) (1,-1)
player Paper (1,-1) (-1,1)
Modified rock- Rock
Column player
Scissors

paper-scissors Row player

Rock (0,0) (1,-1)
Paper (1,-1) (-1,1)

Column Row
Rock Scissors Rock Paper
(1,-1) (1,-1) (0,0) (-1,1)
Rock Paper Rock Paper Rock Scissors Rock Scissors

(0,0) (1,-1) (1,-1) (-1,1) (0,0) (1,-1) (1,-1) (-1,1)

Payoffs: (1,-1) Payoffs: (0,0)

In modified rock-paper-scissors, the second

player to choose has an advantage.
Prisoner’s John
Confess Deny
dilemma Peter
Confess (-3,-3)
Deny (0,-5)
(-5,0)
(-1,-1)

Peter John
Confess Deny Confess Deny

(-3,-3) (0,-5) (-3,-3) (-5,0)

Confess Deny Confess Deny Confess Deny Confess Deny

(-3,-3) (-5,0) (0,-5) (-1,-1) (-3,-3) (0,-5) (-5,0) (-1,-1)

Payoffs: (-3,-3) Payoffs: (-3,-3)

In a prisoner’s dilemma, it doesn’t matter which

player to choose first.
 Nodes

There are three types of nodes (vertices).

Node associated with Player I:
Each branch from it represents a move of Player I.
Node associated with Player II:
Each branch from it represents a move of Player II.
Terminal node:
The game ends, and a payoff pair is given.
Centipede game
Player I and Player II start with $1 in each pile. They
take turns choosing one of two actions, Leave or Stay,
with Player I choosing first.
If any player chooses to Leave at any stage, the game
ends, and the players get the amount in their piles.
Each time a player says Stay, $1 will be deducted
from his pile, and $3 will be added to another
player’s pile.
The game automatically stops when the total amount
in their piles reaches $8.
 Centipede game

I
Leave Stay
II
(1,1)
 Centipede game

I
Leave Stay
II
(1,1) Leave Stay

(1-1,1+3)=(0,4)
 Centipede game

I
Leave Stay
II
(1,1) Leave Stay
I
(0,4) Leave Stay

(0+3,4-1)=(3,3)
 Centipede game

I
Leave Stay
II
(1,1) Leave Stay
I
(0,4) Leave Stay

(3,3) (3-1,3+3)=(2,6)
Centipede game
Red: Nodes and moves of Player I
Green: Nodes and moves of Player II
Blue: Terminal nodes
Centipede game
Centipede game
Payoffs: (1,1)
((3,3) or (2,6) look much better.)
Imperfect information

Perfect information:
All players know all the moves by all
players that have taken place.
Imperfect information:
Players need to learn some of the
moves of other players.
There may be chance moves.
A game with imperfect information is a type of
game where some information is hidden from
players.
This means that each player, when making any
decision, may not be perfectly informed about
some (or all) of the events that have already
occurred.
Here are some examples of games with imperfect information:
Poker: In poker, each player’s cards are hidden from other players.
While the objectives are known, the exact state of the game (i.e.,
the other players’ hands) is not.
Bridge: Similar to poker, in bridge, each player’s cards are hidden
from other players. The objectives are known, but the exact state of
the game is not.
Ticket to Ride: In this board game, players’ resources and moves
are known to all, but their objectives (which routes they seek to
complete) are hidden.

Games of imperfect information are those in which some

information is hidden from players, in contrast to games of perfect
information where all players have complete knowledge about the
game’s state at every point in time.
Matching pennies

Player I secretly turns a penny to

head or tail. Player II guesses
whether the penny is head or tail.
Player II receives $1 from Player I
if he is correct and pays $1 to
Player I if he is wrong.
 In a version of Matching Pennies with
Matching pennies sequential decisions, Player 1 moves first,
and Player 2 observes 1’s decision before
chooses his decision.

Player 2’s Payoff

Player 1’s Payoff
How do we indicate that Player II
needs to know what Player I has
chosen in the game tree?
Information set

Two nodes (vertices) are in the same

information set if the corresponding
player does not know precisely which
node the player is at.
We join two nodes by a dotted line to
indicate they are in the same
information set.
The dotted line indicates that Player II does
not know whether Player I has chosen H or T.
 Market entry

Suppose Pluto is considering whether to enter a

market, and Venus is a provider of the market.
If Pluto chooses “out”, then the payoffs to
(Pluto, Venus) are
(0,5). If Pluto
chooses “enter”,
Then, they enter a
game with the
We were given a game tree.
The dotted line indicates that Pluto does
not know which move Venus has chosen.
Terminal nodes: V2, V6, V7, V8, V9
Nodes associated with Pluto (Player I): V1, V4, V5
Nodes associated with Venus (Player II): V3
 Information set

Two nodes belong to the same information set if the

associated player does not know exactly which node he is
when the game is played.
Dotted lines connect nodes in the same information set.
Any nodes in the same information set should satisfy the
following two properties.
1. The number of branches from the two nodes is the same.
2. The branches (moves) from one node are in one-to-one
correspondence with the branches from the other node.
Pluto has two information sets: {V1}, {V4, V5}
Venus has one information set: {V3}
 Information set

Information set Player Branch

{V1} Pluto Out (O), Enter (E)
{V3} Venus T, A
{V4, V5} Pluto T, A
A player’s strategy is to choose a branch (move)
from each of his information sets.
The number of strategies a player uses is the product
of the number of moves of the information sets.
 Information set

Pluto
Information sets Moves Number
{V1} O (Out), E (Enter) 2
{V4, V5} T, A 2

Number of strategies = 2 × 2 = 4

Strategies of Pluto: OT, OA, ET, EA

 Information set

Information sets Moves Number

{V1} O (Out), E (Enter) 2
{V4, V5} T, A 2
Pluto has four strategies: OT, OA, ET, and EA.
Example: ET means Pluto chooses “enter” and
then chooses “T” if he entered the market.
Remark: One may think that “OT” and “OA” are redundant because
Pluto does not need to choose between “T” and “A” if he chooses to
be out of the market. However, we consider “OT” and “OA” to be
different strategies in the extensive form of the game.
 Information set

Venus
Information sets Moves Number of moves
{V3} T, A 2

Number of strategies = 2

Strategies of Venus: T (Tough), A (Accommodate)

Information set

Information set Player Branch

{V1} Pluto Out (O), Enter (E)
{V3} Venus T, A
{V4, V5} Pluto T, A
Pluto has four strategies: OT, OA, ET, and EA.
Example: ET means Pluto chooses “enter” and
then chooses “T” if he entered the market.
Remark: One may think that “OT” and “OA” are redundant because
Pluto does not need to choose between “T” and “A” if he chooses to
be out of the market. However, we consider “OT” and “OA” to be
different strategies in the extensive form of the game.
The part in red is called a subgame.
To solve the market entry game, we must
first solve the subgame.
 Venus
T A
T (3,2) (6,1)
Pluto
A (1,4) (4,3)

It can be seen that “T” is Pluto’s dominant strategy.

Thus, Pluto would choose “T” no matter what Venus
decides. Hence, Venus would also select “T”, which
gives her a higher payoff.
 Subgame

We can also represent the subgame

by the bimatrix
Venus
T A
T {(3,2)} {(6,1)
Pluto
A (1,4)} (4,3)

And see that both Pluto and Venus choose

“T” is a pure Nash equilibrium.
Therefore, the solution of the game is
Pluto’s strategy: ET; Venue’s strategy: T; Payoff: (3,2)
Monty Hall game

The Player chooses one card from Ace, Jack and

Two at random. The Host knows which card has
been selected, but the Player does not. The Host
then discards one of the other two cards, a Jack or
a Two and reveals it to the Player. Then, the
Player chooses to stick to the selected card initially
or change to the other card, which has yet to be
discarded. If the final chosen card is Ace , the
Host pays $1 to the Player, and there is no payoff if
the final chosen card is not Ace.
Monty Hall game

玩家從 Ace、Jack 和 Two 中隨機選擇一張牌。

主持人知道選擇了哪張牌，但玩家不知道。主持
人然後丟棄另外兩張牌中的一張，即 Jack 或 2，
並將其展示給玩家。
然後玩家選擇堅持一開始選擇的牌，或者換到另
一張沒有被棄掉的牌。如果最終選擇的牌是 Ace，
則主持人向玩家支付 $1 元，如果最終選擇的牌
不是 Ace，則沒有回報。
Monty Hall game
 Information set Strategies
Player Jack, Two SS, SC, CS, CC
 Monty Hall game

Information sets and Strategies of Player

Information set Strategies
Discarding Jack Stick, Change
Discarding Two Stick, Change
Strategies of Player: SS, SC, CS, CC
(SC means Stick if Jack is discarded (被丟棄) and
Change if Two is discarded.)
Strategies of Host: Jack, Two
(Discarding Jack or discarding Two when an Ace is
chosen initially.)
Monty Hall game
Information sets and Strategies of Player
Information set Strategies
Discarding Jack Stick, Change
Discarding Two Stick, Change
Strategies of Player: SS, SC, CS, CC
(SC means Stick if Jack is discarded and Change if Two is
discarded.)
(SS means Stick if Jack is discarded and Stick if Two is
discarded.)
(CS means Change if Jack is discarded and Stick if Two is
discarded.)
(CC means Change if Jack is discarded and Change if Two is
discarded.)
 Monty Hall game

Suppose Player uses CC and Host uses Jack.

Beginning Discard Final card Payoff
Ace Jack Two (0,0)
Jack Two Ace (1,-1)
Two Jack Ace (1,-1)
The expected payoff is
1 1 1 2 2
× 0,0 + × 1, −1 + × (1, −1) = ,−
3 3 3 3 3
 Suppose Player uses CC and Host uses Jack.
Beginning Discard Final card Payoff
Ace Jack Two (0,0)
Jack Two Ace (1,-1)
Two Jack Ace (1,-1)
CC means Change if Jack is discarded and Change if Two is discarded.
Monty Hall game

It is a zero sum game with game matrix

Jack Two
SS
SC
CS
CC 2/3
 Monty Hall game

Suppose Player uses SC and Host uses Two.

Beginning Discard Final card Payoff
Ace Two Jack (0,0)
Jack Two Ace (1,-1)
Two Jack Two (0,0)
The expected payoff is
1 1 1 1 1
× 0,0 + × 1, −1 + × (0,0) = ,−
3 3 3 3 3
 Suppose Player uses SC and Host uses Two.
Beginning Discard Final card Payoff
Ace Two Jack (0,0)
Jack Two Ace (1,-1)
Two Jack Two (0,0)
SC means Stick if Jack is discarded and Change if Two is discarded.
Monty Hall game

It is a zero sum game with game matrix

Jack Two
SS
SC 1/3
CS
CC 2/3
 Monty Hall game

Suppose Player uses SS and Host uses Jack.

Beginning Discard Final card Payoff
Ace Jack Two (1,-1)
Jack Two Ace (0,0)
Two Jack Ace (0,0)
The expected payoff is
1 1 1 1 1
× 1, −1 + × 0,0 + × (0,0) = ,−
3 3 3 3 3
 Suppose Player uses SS and Host uses Jack.
Beginning Discard Final card Payoff
Ace Jack Two (1,-1)
Jack Two Ace (0,0)
Two Jack Ace (0,0)
SS means Stick if Jack is discarded and Stick if Two is discarded.
Monty Hall game

It is a zero sum game with game matrix

Jack Two
SS 1/3
SC 1/3
CS
CC 2/3
 Monty Hall game

Suppose Player uses SS and Host uses Two.

Beginning Discard Final card Payoff
Ace Two Jack (1,-1)
Jack Two Ace (0,0)
Two Jack Two (0,0)
The expected payoff is
1 1 1 1 1
× 1, −1 + × 0,0 + × (0,0) = ,−
3 3 3 3 3
 Suppose Player uses SS and Host uses Two.
Beginning Discard Final card Payoff
Ace Two Jack (1,-1)
Jack Two Ace (0,0)
Two Jack Two (0,0)
SS means Stick if Jack is discarded and Stick if Two is discarded.
Monty Hall game

It is a zero sum game with game matrix

Jack Two
SS 1/3 1/3
SC 1/3
CS
CC 2/3
 Monty Hall game

Suppose Player uses CS and Host uses Two.

Beginning Discard Final card Payoff
Ace Two Jack (1,-1)
Jack Two Ace (0,0)
Two Jack Two (1,-1)
The expected payoff is
1 1 1 2 2
× 1, −1 + × 0,0 + × (1, −1) = ,−
3 3 3 3 3
 Suppose Player uses CS and Host uses Two.
Beginning Discard Final card Payoff
Ace Two Jack (1,-1)
Jack Two Ace (0,0)
Two Jack Two (1,-1)
CS means Change if Jack is discarded and Stick if Two is discarded.
Monty Hall game

It is a zero sum game with game matrix

Jack Two
SS 1/3 1/3
SC 1/3
CS 2/3
CC 2/3
Monty Hall game

It is a zero sum game with game matrix

Jack Two
SS 1/3 1/3
SC 2/3 1/3
CS 1/3 2/3
CC 2/3 2/3
 Monty Hall game
Host
Jack Two
SS 1/3 1/3
Player SC 2/3 1/3
CS 1/3 2/3
CC 2/3 2/3
Maximin strategy of Player: CC
Minimax strategy of Host: Any
Expected payoff: 2/3
Bluffing game
Both players put $1 into the pot. Player I is dealt a winning card with a
probability of 1/4 and a losing card with a probability of 3/4.
Player I sees this card but keeps it hidden from Player II.
(Player II does not get a card.) Player I then checks or bets.
If he checks, his card is inspected. Player I wins $1 from Player II if he
has a winning card; otherwise, he loses $1 to Player II.
If Player I bets, he puts $2 more into the pot and Player II, not knowing
what card Player I have, must fold or call.
If Player II folds, he loses $1 to Player I, no matter what card Player I
has. If Player II calls, he adds $2 to the pot.
Then Player I wins $3 from Player II if he has a winning card and loses
$3 to Player II otherwise.
Bluffing game
兩位玩家都向底池下注 $1 元。玩家 I 得到一張概率為 1/4 的獲勝
牌和一張概率為 3/4 的失敗牌。
玩家 I 看到了這張牌，但對玩家 II 隱藏起來。
（玩家 II 沒有得到一張牌。）然後玩家 I 過牌(Check)或下注(Bet)。
如果他檢查，他的卡將被檢查。如果玩家 I 有一張贏牌，玩家 I 會
從玩家 II 那裡贏得 $1 元，否則他會從玩家 II 那裡輸掉 $1 元。
如果玩家 I 下注，他會再向底池中投入 $ 2 元，玩家 II 在不知道玩
家 I 有什麼牌的情況下必須棄牌 (Fold) 或跟注 (Call)。
如果玩家 II 棄牌，無論玩家 I 有什麼牌，他都會輸給玩家 I $ 1 元。
如果玩家 II 跟注，他會向底池增加 $ 2 元。
然後，如果玩家 I 有贏牌，則玩家 I 從玩家 II 那裡贏得 $ 3 元，否
則就輸給玩家 II $3 元。
 Bluffing game

Player I Player II

Player I chooses Check or Bet.

 Bluffing game

Check

Player I Card Payoff to Player I Player II

Winning 1
Losing −1
 Bluffing game

Bet

Player I Player II

Player II chooses Fold or Call.

 Bluffing game

Bet Fold

Player I Player II
If Player II Folds, Player II pays $1 to Player I.
 Bluffing game

Bet Call

Player I Card Payoff to Player I Player II

Winning 3
Losing −3
Player I
Information set Strategies
Winning card Bet, Check
Losing card Bet, Check
Player II
Information set Strategies
Bet Call, Fold
 Bluffing game

Player I has 4 strategies

Strategy Meaning
BB Bet for winning and losing card
BC Bet for winning card and Check for losing card
CB Check for winning card and Bet for losing card
CC Check for winning and losing card

Player II has 2 strategies: Call and Fold

When there are chance moves, we need to
calculate the expected value of the players'
payoff for every choice of strategy.
 Bluffing game

Suppose Player I uses BC and Player II uses Fold.

(Note: BC is an honest strategy.)
Card Probability Player I Player II Payoff of I
Winning card 1/4 Bet Fold 1
Losing card 3/4 Check Fold -1
The expected payoff of Player I is
1 3 1
× 1 + × −1 = −
4 4 2
 Card Probability Player I Player II Payoff of I
Winning card 1/4 Bet Fold 1
Losing card 3/4 Check Fold -1
 Bluffing game

Suppose Player I uses BB and Player II uses Call.

(Note: BB is a bluffing strategy.)
Card Probability Player I Player II Payoff of I
Winning card 1/4 Bet Call 3
Losing card 3/4 Bet Call -3
The expected payoff of Player I is
1 3 3
× 3 + × −3 = −
4 4 2
 Card Probability Player I Player II Payoff of I
Winning card 1/4 Bet Call 3
Losing card 3/4 Bet Call -3
 Bluffing game

Call Fold
1 3 3 1 3
BB × 3 + × −3 = − ×1+ ×1=1
4 4 2 4 4
1 3 1 3 1
BC × 3 + × −1 = 0 × 1 + × −1 = −
4 4 4 4 2
1 3 1 3
CB × 1 + × −3 = −2 ×1+ ×1=1
4 4 4 4
1 3 1 1 3 1
CC × 1 + × −1 = − × 1 + × −1 = −
4 4 2 4 4 2
 Bluffing game

We can represent the bluffing game by the matrix

Call Fold
3
BB − 1
2
1
BC 0 −
2
CB −2 1
1 1
CC − −
2 2
 Bluffing game

Call Fold
BB −1.5 1
BC 0 −0.5
CB −2 1
CC −0.5 −0.5
CB and CC are dominant strategies and can be
removed. This is unsurprising because Player I
has no reason to check if he has a winning card.
Bluffing game

The game reduces to the 2 × 2 matrix

Call Fold
BB (Bluffing) −1.5 1
BC (Honest) 0 −0.5

−1.5 1
𝐴𝐴 =
0 −0.5
Bluffing game

−1.5 1 −2.5 1/6

×
0 −0.5 0.5 5/6
−1.5 1.5
×
1/2 1/2
−1.5 1
𝐩𝐩𝐴𝐴 = 1/6 5/6 = −0.25 −0.25
0 −0.5
𝑇𝑇 −1.5 1 1/2 −0.25
𝐴𝐴𝐪𝐪 = =
0 −0.5 1/2 −0.25
 Bluffing game

Solution to the bluffing game:

Maximin strategy of Player I: 𝐩𝐩 = (1/6,5/6,0,0)
Minimax strategy of Player II: 𝐪𝐪 = (1/2,1/2)
Value: -0.25
That means Player I should use the Bluffing
strategy (BB) with a probability of 1/6 and use the
Honest strategy (BC) with a probability of 5/6, and
Player II should Call with a probability of 1/2 and
Fold with a probability of 1/2 when Player I has bet.
 Pocket game

A Terran has one $10 note, one $20 note in the left pocket,
one $10 note, and three $20 notes in the right pocket. The
Terran chooses one pocket at his will and randomly picks a
note from the pocket.
$10 note $20 note
Left 1 1
Right 1 3
A Martian, who knows the note’s value, must guess which
pocket the Terran has chosen. If the Martian is correct, the
Terran pays an amount equal to the value of the note to the
Martian. The payoff is only fair if the Martian is correct.
 Pocket game

人族有一張 $10 元紙幣，一張 $20 元紙幣在左口袋，一張

$10 元紙幣，三張 $20 元紙幣在右口袋。人族隨意選擇一
個口袋，然後從口袋中隨機挑選一張紙條。

$10 note (紙幣) $20 note (紙幣)

Left (左) 1 1
Right (右) 1 3

一個火星人，知道撿到的鈔票的價值，必須猜測人族選擇
了哪個口袋。如果火星人是正確的，人族支付與火星人票
據價值相等的金額。如果火星人錯了，就沒有回報。
 Pocket game

Left

Right

Terran Martian
 Pocket game

Left

or

Right

Terran Martian
 Pocket game

Right
Left

Right

Terran Martian
 Pocket game

Result Payoff
Correct Pays the note
Wrong No payoff

Terran Martian
Pocket game
Player Information sets Strategies
Terran Initial Left, Right
Martian $10, $20 LL, LR, RL, RR
 Pocket game

Terran’s strategies: Left, Right

Martian’s strategies:
Meaning
LL Always guess Left.
LR Guess Left if it is $10 and guess Right if it is $20
RL Guess Right if it is $10 and guess Left if it is $20
RR Always guess Right.
Pocket game

Suppose Terran uses Left and Martian uses LR. The

payoff of Terran is
$10 $20
Probability 0.5 0.5
Martian’s guess Left Right
Result Correct Wrong
Payoff to Terran −10 0
The expected payoff of Terran is
−10 × 0.5 + 0 × 0.5 = −5
Player Information sets Strategies
Terran Initial Left, Right
Martian $10, $20 LL, LR, RL, RR
Pocket game

Suppose Terran uses Right and Martian uses RR. The

payoff of Terran is
$10 $20
Probability 0.25 0.75
Martian’s guess Right Right
Result Correct Correct
Payoff to Terran −10 −20
The expected payoff of Terran is
−10 × 0.25 + −20 × 0.75 = −17.5
Pocket game

Suppose Terran uses Right and Martian uses RL. The

payoff of Terran is
$10 $20
Probability 0.25 0.75
Martian’s guess Right Left
Result Correct Wrong
Payoff to Terran −10 0
The expected payoff of Terran is
−10 × 0.25 + 0 × 0.75 = −2.5
 Pocket game

It is a zero sum game and the payoff matrix is

LL LR RL RR
Left −15 −5 −10 0
Right 0 −15 −2.5 −17.5

−15 −5 −10 0
𝐴𝐴 =
0 −15 −2.5 −17.5
 −15 −5 −10 0
𝐴𝐴 =
0 −15 −2.5 −17.5
Pocket game

−15 −5 −10 0.6

×
0 −15 15 0.4
−15 10
×
0.4 0.6
−15 −5
𝐩𝐩𝐴𝐴 = 0.6 0.4 = −9 −9
0 −15
𝑇𝑇 −15 −5 0.4 −9
𝐴𝐴𝐪𝐪 = =
0 −15 0.6 −9
 Pocket game

The solution to pocket game:

Maximin strategy of Terran: 𝐩𝐩 = (0.6,0.4)
Minimax strategy of Martian: 𝐪𝐪 = (0.4,0.6,0,0)
Value: 𝑣𝑣 = −9
That means an intelligent Martian should use
LL with a probability of 0.4 and
LR with a probability of 0.6.
(Same as always Left if it is $10, and Left, Right
with probabilities 0.4, 0.6 respectively if it is $20.)