ECO290E: Game Theory
Review of Lecture 4
Spatial competition model has a unique NE in which both shops choose the middle point.
⇒ Minimal differentiation!
Political platforms (left/right or liberal/ conservative)
TV shows (time slots)
Under the Bertrand model:
Price will be set at the level of marginal cost even when there are only two competitors.
⇒ Huge jump from 1 (monopoly) to 2 (duopoly)!
Under the Cournot model:
Total output (price) is between monopoly level and that under perfect competition.
Zero-Sum Game
Matching Pennies:
Player 2 Player 1
Heads Tails
Heads 1 -1
-1 1
Tails -1 1
No Nash Equilibrium?
The distinguishing feature of zero-sum game is that
each player would like to outguess the other since
there is No “win-win” situation.
Examples are:
Porker: bluff or not
Battle (War): attack/defend by land or by sea
Tennis: left or right to serve/receive
When each player would always like outguess the
other(s), there is no Nash equilibrium.
Is there no solution or stable outcome?
Mixed Strategy
A mixed strategy for a player is a probability
distribution over some (or all) of her strategies.
The strategy we have studied so far, i.e., taking some
action for sure, is called a pure-strategy .
When the outcome of the game is uncertain, we
assume that each player maximizes expected value of
her payoff.
⇒
Expected utility theory (von Neumann and
Morgenstern, 1944)
Matching Pennies Again
Introducing mixed strategies:
Player 2 Player 1
Heads (p) Tails (1-p)
Heads (q)
1 -1
-1 1
Tails (1-q)
-1 1
1 -1
How to Find Equilibrium?
If a player takes both “Heads” and “Tails” with positive probability, she must be indifferent between these two pure strategies, i.e., the expected payoff derived by
choosing Heads must be equal to that by choosing Tails.
Otherwise, it is strictly better for her to choose either H or T for sure; no incentive to mix the strategies.
-p + (1-p) = p - (1-p), hence p = 0.5.
q - (1-q) = -q + (1-q), hence q = 0.5.
How to Verify Equilibrium?
Note that if p = 0.5, Player 1 does not have a strict
incentive to change her strategy from q = 0.5.
Similarly, Player 2 does not have a strict incentive to
change his strategy from p = 0.5, if q = 0.5.
⇒
Therefore, p = q = 0.5 constitutes a mixed-strategy
equilibrium.
Q: Is this equilibrium reasonable/stable?
A: Yes (each player ends up randomizing two strategies
equally if the rival is smart enough).
Best Response Curves
Given the opponent mixed strategy, draw the best response (mixed strategy) against it.
p
1
BR2
BR1
0.5
NE
Existence of NE
Theorem (Nash, 1950)
If a game has finite number of players and actions,
then there exists at least one Nash equilibrium,
possibly involving mixed strategies.
Q: Are there any games which do not even have a
mixed-strategy equilibrium?
A: Yes. For example, integer game.
(Two person) Zero-sum game in which players independently choose a number simultaneously. The player who picked a larger number wins.
Modified Matching Pennies
Suppose the payoffs in the up-left cell changes as the
following:
Player 2 Player 1
Heads (p’) Tails (1-p’)
Heads (q’)
2 -2
-1 1
Tails -1 1
Indifference Property
Under mixed-strategy NE, Player 1 must be indifferent between choosing H and T:
⇒ -2p’ + (1-p’) = p’ - (1-p’), hence p’ = 0.4.
Similarly, Player 2 must be indifferent between choosing H and T:
⇒ 2q’ - (1-q’) = -q’ + (1-q’), hence q’ = 0.4.
You can easily verify that (p’, q’) = (0.4, 0.4) indeed becomes a mixed-strategy NE.
Note that player 2 chooses H with less than a half chance, even if H looks “better” strategy than T.
Multiple Nash Equilibria
2 1
D (x) E (y) F (1-x-y)
A (a)
6 7
8 5
0 0
B (b)
8 5
6 7
0 0
C 0 0 4
Three Different Equilibria
Pure-strategy NE
(C, F) is a unique pure-strategy NE.
Mixed-strategy NE (1)
P1 mixes A (q) and B (1-q); p2 mixes D (p) and E (1-p).
7p + 5(1-p) = 5p + 7(1-p) ⇒ p = 1/2.
6q + 8(1-q) = 8q + 6(1-q) ⇒ q = 1/2.
Mixed-strategy NE (2)
Both players use all three strategies.
A (a), B (b), C (1-a-b); D (x), E (y), F (1-x-y)
7x + 5y = 5x + 7y = 4(1-x-y) ⇒ x = y = 1/5.
Example: Soccer (Penalty Kick)
Kicker GK
Left (x) Middle (y) Right (1-x-y)
Left (p)
40 60
100 0
80 20
Middle (q)
80 20
0 100
80 20
Right 80 100 20
Further Exercises
Construct a game which has both pure-strategy and mixed-strategy Nash equilibria.
Consider a modified matching penny game in which the payoff on (H, H) is changed from (-1, 1) to (-k, k) for k > 0. Then, derive a mixed-strategy Nash equilibrium.
Prove that a strategy which is erased by the iterated
elimination of strictly dominated strategies can never be selected (with positive probability) in a mixed-strategy Nash equilibrium.