Lecture 3: Static games with complete information III
1 Recap of last lecture
• Cournot vs. Bertrand
• Hotelling model
• Tragedy of the commons
2 Mixed strategy Nash equilibrium
2.1 Motivation
• Consider the following example
Exercise 1. Penalty Kick in a soccer game
Goalie
Left Right
Kicker
Left 0,1 1,0
Right 1,0 0,1
Agent 1 is the kicker and Agent 2 is the goalie. Each has to commit to going either to
the left side of the goal or the right side before learning what the other is doing. If they
choose the same side, the advantage is to the goalie.
• There is no pure-strategy Nash equilibria
• In reality, we know that both players should randomize between left and right.
• Mixed-strategy Nash equilibrium captures this idea: In some games, it can be optimal
for a player to randomize between his strategies.
• However, to formalize this idea, we need to know how to calculate one’s utility when
there is uncertainty.
1
2.2 Expected Utility Theory
• When the event is uncertain, we say that an agent is facing a “lottery”, which species
a list of events with associated probabilities. E.g.,
L1 =
sunny prob. 0.8
rainy prob. 0.19
blizzard+ tornado prob. 0.01
L2 =
sunny prob. 0.5
rainy prob. 0.5
blizzard+ tornado prob. 0
• In intermediate-level economics, we have learned that, facing a lottery, the expected
utility of the agent is
EU(L) =
∑
i
u(eventi) · P (eventi)
• E.g., if for our agent, u(sunny) = 10, u(rainy) = 0, u(blizzard + tornado) = 1000,
then
EU(L1) = 10 · 0.8 + 0 · 0.19 + 1000 · 0.01 = 18
EU(L2) = 10 · 0.5 + 0 · 0.5 + 1000 · 0 = 5
• But why do we choose to work with this specific formula? When we say “the agents
likes L1 more than L2 because the calculated EU(L1)>EU(L2)”, what exactly have we
assumed about this agent’s preferences?
• (This part is optional for the course, but hopefully it will persuade you that Economic
theorists are careful scientists, not just people who like making assumptions. And
hopefully it will make you feel more comfortable being a young economist.)
2.2.1 Axioms
• Let � denote one’s preference over lotteries. E.g. L1 � L2 means that L1 is weakly
preferred to L2. One can argue that it’s reasonable for � to have the following prop-
erties:
1. [Completeness] For any pair of L1 and L2, either L1 � L2 or L2 � L1
2. [Transitivity] If L1 � L2 and L2 � L3, then L1 � L3.
3. [Continuity] Suppose L1 � L2. Obtain new lotteries L
′
1 and L
′
2 by slightly chang-
ing the probabilities in L1 and L2. We can always make those changes small
enough so that L1 � L
′
2 and L
′
1 � L2.
4. [Independence] Suppose L1 � L2 and p ∈ (0, 1). Then, for any L3, pL1 + (1 −
p)L3 � pL2 + (1− p)L3
2
• von Neumann-Morgenstern utility theorem: if one’s preference satisfies 1-4, then we
can use the an expected utility function to represent his preferences over lotteries. (i.e.
the EU formula is a correct metaphor)
2.3 Find mixed-strategy Nash equilibrium
Definition 1. In the normal-form gameG = {S1, …, Sn;ui, …, un}, suppose the set of all pure
strategies for i is Si = {si1, si2, …, siK}. Then a mixed strategy for player i is a probability
distribution σi = (pi1, …, piK), where pik ∈ [0, 1] for k = 1, 2, …, K and pi1+pi2+ …+piK = 1.
Example. (revisit) Penalty Kick in a soccer game
Goalie
Left Right
Kicker
Left 0,1 1,0
Right 1,0 0,1
• A mixed strategy for the Kicker is σ1 = (p, 1 − p) for some p ∈ [0, 1], where p is the
probability of playing Left, 1− p is the probability of playing Right.
• Technically, pure strategies can be written in the form of the mixed strategies as well:
“Left” →(1,0); “Right” →(0,1). However, by convention, the term “mixed-strategy
equilibrium” refers to the case in which at least one player chooses more than one
action with positive probability.
• There is no pure NE and one mixed NE:
((
1
2
, 1
2
)
,
(
1
2
, 1
2
))
.
Definition 2. In the two-player normal-form game G = {S1, S2;u1, u2}, the mixed strategies
(σ∗1, σ
∗
2) are a Nash equilibrium if each player’s mixed strategy is a best response to the other
player’s mixed strategy.
• Assume that, in the mixed NE, Kicker chooses left with prob p, Goalie chooses left
with prob q.
Goalie
Left Right
q 1-q
Kicker
Left p 0,1 1,0
Right 1-p 1,0 0,1
• Two ways to find the mixed-strategy Nash equilibrium
3
1. “If one is willing to play two strategies with positive probabilities, then he must
be indifferent between these two strategies”
EUkicker(left) = EUkicker(right)
0 · q + 1 · (1− q) = 1 · q + 0 · (1− q)
q∗ = 0.5
EUgoalie(left) = EUgoalie(right)
1 · p+ 0 · (1− p) = 0 · p+ 1 · (1− p)
p∗ = 0.5
Therefore, the mixed NE is
((
1
2
, 1
2
)
,
(
1
2
, 1
2
))
. *Note that the indifference condition
for player 1 specifies the equilibrium strategy for player 2, and vice versa.
2. “Find the intersection of players’ best response graphs”
– Kicker’s best response is
p = 1 (Left) when q < 1
2
Any p ∈ [0, 1] (any pure or mixed strategy) when q = 1
2
p = 0 (Right) when q > 1
2
– Goalie’s best response is
q = 0 (Right) when p < 1
2
Any q ∈ [0, 1] (any pure or mixed strategy) when p = 1
2
q = 1 (Left) when p > 1
2
–
– Only one point of intersection in the middle => Only one mixed NE. No pure
NE.
4
Example. (revisit) The battle of the sexes
Bob
Opera Fight
q 1-q
Ann
Opera p 2,1 0,0
Fight 1-p 0,0 1,2
Pure NE: (Opera, Opera) and (Fight, Fight)
Mixed strategy NE:
Ann : 2q = 1− q ⇒ q∗ =
1
3
Bob : p = 2(1− p) ⇒ p∗ =
2
3
Mixed NE:
((
2
3
, 1
3
)
,
(
1
3
, 2
3
))
.
Alternative graphical answer:
• Ann’s best response is
p = 0 (Fight) when q < 1
3
Any p ∈ [0, 1] (any pure or mixed strategy) when q = 1
3
p = 1 (Opera) when q > 1
3
• Bob’s best response is
q = 0 (Fight) when p < 2
3
Any q ∈ [0, 1] (any pure or mixed strategy) when p = 2
3
q = 1 (Opera) when p > 2
3
5
•
• Two intersection points at the corners => Two pure NE: (Opera, Opera) and (Fight,
Fight)
• One point of intersection in the middle => One mixed-strategy NE
((
2
3
, 1
3
)
,
(
1
3
, 2
3
))
.
3 Revisit: Dominated strategies
3.1 A pure strategy can be strictly dominated by a mixed strategy,
even if it is not strictly dominated by any pure strategy
Player 2
L R
Player 1
T 3, – 0, –
M 0, – 3, –
B 1, – 1, –
• Although B is not dominated by either T or M, it is strictly dominated by the mixed
strategy (0.5, 0.5, 0).
• Recall: Suppose player 2 plays L with probability q and R with probability 1-q. For
player 1, a strategy A is strictly dominated by a (possibly mixed) strategy B if, for any
q ∈ [0, 1], A is strictly worse than B.
• Here, for any q ∈ [0, 1], playing the mixed strategy “1/2 T, 1/2 M” always gives payoff
1.5, while playing B always gives payoff 1.
6
3.2 A pure strategy can be a best response to a mixed strategy,
even if it is not a best response to any pure strategy
Player 2
L R
Player 1
T 3, – 0, –
M 0, – 3, –
B 2, – 2, –
• Although B is never a best response when player 2 plays a pure strategy, it is not a
strictly dominated strategy.
• In fact, B is the best response when player 2 plays the mixed strategy “1/2 L, 1/2 R”.
3.3 Weak dominance vs. Strict dominance
Pirate 2
Island Home
Pirate 1
Island 1, 1 0, 0
Home 0, 0 0, 0
• Story: there are two pirates, each holding half of a key to open the passage to a hidden
island. Each pirate chooses whether to travel to the hidden island tonight or stay at
home.
• “Home” is weakly dominated by “Hidden Island”: playing H gives strictly lower payoff
than playing I if the opponent plays I, and the same payoff if the opponent plays H.
• To find NE, should we first delete Home for both players?
• No! Because (Home, Home) is a NE!
• Lesson: we keep weakly dominated strategies in the iterated elimination of strictly
dominated strategies.
3.4 Steps to find all Nash equilibria
1. Simplifying the game by deleting all strictly dominated strategies. If this leads to a
unique strategy profile, then that is the unique Nash equilibrium of the game.
2. Find all pure-strategy NE of the simplified game.
3. Assign probabilities to each player’s strategies in the simplified game and solve the
mixed-strategy NE (if there is any).
Example 1. Consider the following 3×3 game
7
Player 2
L C R
Player 1
U 5,7 2,8 0,3
M 0,4 1,6 2,5
D 9,2 2,2 4,1
• Step 1: Delete M (dominated by D), and R (dominated by C). Then, we simply find
all NE of the simplified game:
Player 2
L C
q 1-q
Player 1
U p 5,7 2,8
D 1-p 9,2 2,2
• Step 2: pure-strategy NE: (U, C), (D, L), (D, C)
• Step 3: mixed NE:
Player 1 indifferent: 5q + 2(1− q) = 9q + 2(1− q) => q = 0
– Player 2 chooses q = 0 when 8p+ 2(1− p) ≥ 7p+ 2(1− p), which is true for any
p ∈ [0, 1]
– Any ((p, 1− p) , (0, 1)) with p ∈ [0, 1] is a Nash equilibrium.
Player 2 indifferent: 7p+ 2(1− p) = 8p+ 2(1− p) => p = 0
– Player 1 chooses p = 0 when 9q + 2(1− q) ≥ 5q + 2(1− q), which is true for any
q ∈ [0, 1]
– Any ((0, 1) , (q, 1− q)) with q ∈ [0, 1] is also a Nash equilibrium.
Infinitely many mixed NE!
Exercise: draw the best response graphs and verify that they intersect at infinitely many
points.
8
• Remark: suppose the game is
Player 2
L C R
Player 1
U 5,7 2,8 0,3
M 0,4 4,6 2,5
D 9,2 2,2 4,10
• Then we cannot simplify the game. Find pure NE and then assign probability p1 to
U, p2 to M, (1− p1 − p2) to D, etc. to find mixed NE.
4 Existence of Nash equilibrium
Theorem 1. (Nash 1950) In the n-player normal-form game G = {S1, …, Sn;u1, …, un}, if
(a) n is finite, and
(b) Si is finite for every i,
then there exists at least one Nash equilibrium, possibly involving mixed strategies.
Proof. A Nash equilibrium is a fixed point of players’ best-response correspondence. Apply
Kakutani’s fixed point theorem to show the existence of fixed point(s).
• Sketch of proof for 2×2 game:
Suppose we draw two players’ best responses in a graph:
The best response graphs will shift according to the payoff matrix of the specific game,
but they will always cross at least once because:
9
– each graph is continuous
– each graph starts from one end and ends at the opposite end.
Therefore, there will always be at least one Nash equilibrium.
This generalizes to any arbitrary finite game.
5 Practice problems
1. Nash’s Theorem (1950) states that, in any normal form game, there always exists at
least one (possibly mixed) Nash equilibrium if
(i) the number of players is finite, and
(ii) the number of feasible strategies for each player is finite.
In each of the following examples, state which assumption is violated, and why Nash
equilibrium does not exist.
a. Two players, each chooses xi ∈ [0, 1] and receives payoff
ui =
{
0 if both players choose 1
xi otherwise
b. There are infinitely many players. Each player chooses xi ∈ {0, 1} and receives
payoff {
xi if
∑
i xi is finite
−xi if
∑
i xi is infinite
2. Consider the following game
Player 2
L R
Player 1
U -12, 1 8, 8
D 15, 1 8, -1
a. Is there any strictly dominated strategy? Is there any weakly dominated strategy?
b. Find all Nash equilibria.
3. Consider the following game
Player 2
L R
Player 1
T 1, 3 1, 0
M 4, 2 0, 4
B 0, 5 3, 1
10
a. Is there any strictly dominated strategy?
b. Find all Nash equilibria.
11