# 7. Mixed Strategies

(1,1)

(1,2)

(2,1)

(2,2)

(1,1)

Two-Finger Morra Game
Two players simultaneously raise both hands with one or two fingers extended on each hand. Left hand is for “number shown,” right hand for “number guessed.” The guess is about how many fingers the other player is going to show―with his left hand, of course.
0 0 0 0 0 0 0 0 -3 3 4 0 -4 0 0 -4 0 3 4 -3

(1,2)

(2,1)

(2,2)

(1,1) 0 (1,1) 0 2 (1,2) -2 -3 (2,1) 3 (2,2) 0 2

(1,2) -2 -3 0

(2,1) 3

(2,2)

Mixed Strategies in Normal and Sequential Form Games

1

The South Pacific Example (World War II) Japan

E
2 E US -2 0 0

W
0

1 -1

W
0

You have to choose one of the two routes, E or W, every day. How would you play?

Mixed Strategies in Normal and Sequential Form Games

2

The South Pacific Example with Different Payoffs
The original game

Japan

E
2 E US -2 0 5

W
0
US W E -2

Japan E W 2 0 0 0 -1 1 0

1 -1

W
0

Regardless of the solution to the original game what would you do, as the US player, if your payoffs were altered as above? (Say, they can bring considerably more supplies using E rather than W.) Would you go E more often than before, less often or with the same frequency?

Mixed Strategies in Normal and Sequential Form Games

3

How to calculate payoffs to a probabilistic mix of Row’s E and W against, for instance, Column’s E?

Japan
E 2 E W 0 0 0 W 0 -1 1

US

-2

p E

uUS (

,E)=?
1-p W
Mixed Strategies in Normal and Sequential Form Games 4

Japan

E
2

W
0 0 0 1 -1

p E

p (E, E)

E

uUS (

,E)=
1-p W

uUS (
1-p (W, E)

)=

US W

-2 0

here we need expected utility theory

= p uUS (E, E) + (1-p) uUS (W, E) = p?(-2) + (1-p)?0 = -2p

Thus with mixed strategies we have to switch from ordinal utility assumption (preference theory) to cardinal utility assumption (expected utility theory)
p E

1-p W

I will write pE ? (1-p)W

? stands for a “lottery”

Mixed Strategies in Normal and Sequential Form Games

5

Japan E W 2 E 0 0 0 W 0 -1 1 -2

A Few Examples

US

uUS (0.7E ? 0.3W, E) = 0.7 uUS (E, E) + 0.3 uUS (W, E) = 0.7?(-2) + 0.3?0 = -1.4

Row’s strategy (recall the general notation rules in game theory) Column’s strategy

uJ (0.6E ? 0.4W, W) = 0.6 uJ (E, W) + 0.4 uJ (W, W) = 0.6?0 + 0.4?1 = 0.4 uUS (W, 0.7E ? 0.3W) = 0.7 uUS (W, E) + 0.3 uUS (W, W) = 0.7?0 + 0.3?(-1) = -0.3 uJ (0.2E ? 0.8W, 0.3E ? 0.7W) = 0.2 uJ (E, 0.3E ? 0.7W ) + 0.8 uJ (W, 0.3E ? 0.7W) = 0.2?0.3 uJ (E, E) + 0.2?0.7 uJ (E, W) + 0.8?0.3 uJ (W, E) + 0.8?0.7 uJ (W, W) = 0.06?2 + 0.14?0 + 0.24?0 + 0.56?1 = 0.68
Mixed Strategies in Normal and Sequential Form Games

6

q

1-q

E
2 p E 1-p W 0 pE?(1-p)W 2p -2 0 0

W
0

qE?(1-q)W
p?2 + (1-p)?0

-2q 1

-1 1-p

q-1

p?0 + (1-p)?1

Just like we were looking for Nash equilibria in pure strategies we now need to do the same with mixed strategies. The difference here is that since we have infinitely many mixed strategies we can no longer draw a payoff table with rows representing choices of the Row player. Note that when 2p > 1-p, or equivalently when p > 1/3, the best response of Column is his pure strategy E since mixing in W will only lower his payoff.

By the same token, when 2p < 1-p, that is p < 1/3, the best response of Column is his pure strategy W.
Finally, when p = 1/3 then all possible strategies of Column give him the same payoff—all are best response strategies.
Mixed Strategies in Normal and Sequential Form Games 7

Game with pure strategies only
Japan E W 2 US 0 0 0 W 0 -1 1

A way to think about the same game with mixed strategies
Japan 1 1 US 1/3 0 1/3 0

E -2

qE?(1-q)W

best response of Column to Row’s choice of strategy “p” W ? q=0

E ? q=1

E ? p=1

1/3E?2/3W ? q=1/3

best response of Row to Column’s choice of strategy “q”

pE?(1-p)W
1/3E?2/3W ? p=1/3

Nash equilibrium: each is the best response to the other
2 1 2 ? ?1 ? E ? W, E ? W ? 3 3 3 ? ?3

W ? p=0
Mixed Strategies in Normal and Sequential Form Games 8

The South Pacific Example with Different Payoffs
The original game

Japan E W
E

Japan

W
2 0 0 0 1 -1

2
E US W -2 0 5

0
US

E W

-2 0

1

1

-1

What would be Row’s equilibrium strategy if his payoffs were altered as above? (Say, they can bring considerably more supplies using E rather than W.) Would you go E more often than before, less often or with the same frequency? THE SAME: since his strategy depends only on the other player’s payoffs and they are the same in both games.
Mixed Strategies in Normal and Sequential Form Games 9

THEOREM

1 2 n Denote p1s1 ? p 2s1 ? ...... ? p n s1 ? s 2 m q1s1 ? q 2s 2 ? ...... ? q ms 2 ? s* 2

s1 2
p1

……

sm 2

……

s1 1

If two proper mixes (s, s* )

……

are in Nash equilibrium then
m u 2 (s1 , s) = ... = u 2 (s 2 , s) and 2 1 n u1 (s1 , s* ) = ... = u1 (s1 , s* ).

pn
Proper mix ? does not reduce to a pure strategy

n s1

……

Idea behind the proof: If, for example, a was greater than a*, then Column would have no reason to play s2m at all and since he plays it in equilibrium it must be that a = a*.

1 n p1s1 ? .... ? p n s1

a

……

a*

……

Mixed Strategies in Normal and Sequential Form Games

10

Battle of the Sexes Example

G
1 G 2 0 0

T
0

2 1

T
0

Identify all Nash equilibria in this game.

Mixed Strategies in Normal and Sequential Form Games

11

G

T

qG?(1-q)T

1
G 2 0 T 0 pG?(1-p)T p 1 0

0
2q 2 1-q 2-2p

The value of p for which the payoffs to Column are the same: p = 2-2p or p = 2/3 The value of q for which the payoffs to Row are the same: 2q = 1-q or q = 1/3

Mixed Strategies in Normal and Sequential Form Games

12

Game with pure strategies only

A way to think about the same game with mixed strategies
1 1/3 0

G 1

T 0 0 2 1 0 1 2/3

G 2
0 T 0

qG?(1-q)T

best response of Column to Row’s choice of strategy “p” W ? q=0

G ? q=1

G ? p=1

1/3G?2/3T ? q=1/3

best response of Row to Column’s choice of strategy “q”

2/3G?1/3T ? p=2/3

pG?(1-p)T

Nash equilibria: (G, G), (T, T) and ( ? T, ? T )

T?

p=0
Mixed Strategies in Normal and Sequential Form Games 13

Competition: Chicken / Hawk-Dove Game

H
0 H 0 3 3

D
1

2 2

D
1

Draw the best response diagram and identify all Nash equilibria on it.

Mixed Strategies in Normal and Sequential Form Games

14

Game with pure strategies only The value of p for which the payoffs to Column are the same: 3(1-p) = p + 2(1-p) or p = 1/2
1 3 3 D 1 2 2

H 0

D

H 0

The value of q for which the payoffs to Row are the same: 3(1-q) = q + 2(1-q) or q = 1/2

qH?(1-q)D

best response of Column to Row’s choice of strategy “p” D ? q=0

H ? q=1

1/2H?1/2D q=1/2

H ? p=1

best response of Row to Column’s choice of strategy “q”

pH?(1-p)D

1/2H?1/2D ? p=1/2

Nash equilibria: (H, D), (D, H) and ( ? D, ? D)

D?

p=0
Mixed Strategies in Normal and Sequential Form Games 15

A footnote: mixed strategies and iterated dominance
X 4 A 6 3 B 3 2 C 2 6 3 3 2 0 Y 5

Step 1:B is dominated by ? A ? ?C Step 2: X is dominated by Y Step 3: A is dominated by C (C,Y) is the solution through iterated dominance Next comes the second important idea of Nash.

Mixed Strategies in Normal and Sequential Form Games

16

THEOREM (Nash) Every game with finite number of strategies has at least one equilibrium.
Idea behind the proof
First a few concepts: A set is closed if it contains all its boundary points. For example, interval (0,1) is not a closed set since it does not contain its boundary points; interval [0,1] is a closed set. A set is convex if for any two points it contains it also contains all points from the interval connecting the two points.

non-convex sets

convex sets

A set is compact if it is both closed and bounded. A function from Re (real numbers) to Re is continuous if you can draw its graph without having to lift the pen off the paper. This of course is not a definition but an intuition behind it.
Mixed Strategies in Normal and Sequential Form Games 17

THEOREM (Brouwer) Take any nonempty, compact, convex set X in Ren. If a function f: X→X is continuous then there is a point x0 such that f(x0) = x0.
Example: Take X = [0,1] and consider any continuous function from [0,1] into [0, 1], that is f: [0,1]→[0,1]. We have three possible cases: (1) f(0) = 0, (2) f(1) = 1, and (3) f(0) ≠ 0 & f(1) ≠ 1. In (1) the fixed point is 0, in (2) the fixed point is 1, so the only nontrivial case to consider is case (3). .
f(x) 1 f(x) = x line

f(x0) = x0

0

x0 1

x

Mixed Strategies in Normal and Sequential Form Games

18

Japan

E -2
US

E 2 0 0 -1

W 0 1

THEOREM (Kakutani) Take any nonempty, compact , convex set X. Take any correspondence f: X→X that has a closed graph and such that for any x, f(x) is convex and nonempty then there is a point x0 such that x0 ?f(x0). How does it apply to games? Take any of the games we have solved for Nash equilibria in mixed strategies as an example, say the South Pacific game.
q=0 Consider Column’s best response function: BRC(p) = q, BRC: [0,1]→ [0,1] Consider Row’s best response function: BRR(q) = p, BRR: [0,1]→ [0,1]

W0

BR of Column to Row’s “p” BR of Row to Column’s “q” q=1 p=1 q=1/3

p=1/3 p=0

Now take the following transformation: f: (p, q) → (BRR(q), BRC(p))

1 1

q

0

1 1

BRC(p)

0

(?, ?)
p BRR(q)

(?,?)
0 0

Yellow circle is a fixed point of this correspondence. This point is (?,?), of course.

(?, ?)
Mixed Strategies in Normal and Sequential Form Games 19

In 2 x 2 game finding Nash equilibria is trivial. The problem begins with larger games. The source of the problem is that in larger games we don’t know which mixes go into Nash equilibrium. Let’s go back to the Two-Finger Morra game.

Mixed Strategies in Normal and Sequential Form Games

20

C1 0 R1 0 2 2

C2 -2

C3 3

C4 0

-3 0 0

0 -3

R2
-2 -3 0 0 0 0 3 4

R3
3 0 0 3 0 -4 -4 0

R4
0 -3 4 0

Mixed Strategies in Normal and Sequential Form Games

21

C1 0 p1 R1 0 2 p2 R2 -2 -3 p3 R3 0 2

C2 -2

C3 3

C4 0

-3 0 0

0 -3

0 0 0

3 4

3
0 p4 R4 0 p1R1? p2R2? p3R3 ? p4R4 2p2-3p3

0
3

0
-4

-4 0

-3 -2p1+3p4

4 3p1-4p4

0 -3p2+4p3

The idea: Find values of p1, p2, p3 and p4 that make all payoffs to the Column less or equal to zero, that is 2p2-3p3 ?0, -2p1+3p4 ?0, 3p1-4p4 ?0 and -3p2+4p3 ?0
Mixed Strategies in Normal and Sequential Form Games 22

Note that we can group the four inequalities into two sets with the same variables: (1) -2p1+3p4 ?0, 3p1-4p4 ?0 and (2) 2p2-3p3 ?0, -3p2+4p3 ?0. where p1, p2, p3 p4?0 since they are all probabilities. Let’s solve (1): -2p1+3p4 ?0 ? 3p4 ?2p1 ? p4 ?2/3p1 3p1-4p4 ?0 ? 3p1?4p4 ? 3/4p1?p4 which means that 3/4p1? p4 ?2/3p1 or 0.75p1? p4 ?0.67p1 But this cannot be satisfied by any values of p1 and p4 that are larger than 0. The only values of p1 and p4 that satisfy these inequalities are p1 = p4=0.

Mixed Strategies in Normal and Sequential Form Games

23

Let’s solve now (2): 2p2-3p3 ?0 and -3p2+4p3 ?0. But first note that since p1 = p4=0 and all four probabilities have to add up to 1, it must be that p2+ p3=1. So, in the two inequalities we can substitute for p3 , for instance, p3=1- p2. That way we get: 2p2-3(1-p2 )?0 which is 5p2-3 ?0, and -3p2+4(1-p2 )?0.which is 4-7p2?0 Solving the two inequalities we have: p2?3/5 or p2?0.6 and p2?4/7 or (approximately) p2?0.57. Putting the two inequalities together: 0.57?p2?0.6. (This implies that 0.4?p3?0.43.)

Mixed Strategies in Normal and Sequential Form Games

24

The set of all Nash equilibria in the Two-Finger Morra Game

q2 of the Column player

set of Nash equilibria 0.6

0.57

0 0.57 0.6

p2 of the Row player

Any pair of strategies ( p2R2?(1-p2)R3, q2C2?(1-q2)C3 ) where 0.56 ? p2,q2 ?0.6 is a Nash equilibrium. The set of all Nash equilibria is identified above as the set of all points (p2,q2) where 0.56 ? p2,q2 ?0.6

Mixed Strategies in Normal and Sequential Form Games

25

Back to sequential games. How would you play the following game?

0, 2
2 X

How about representing this game in a normal form?

X

Y 2 0 2 0 1 1

A
1

Y

2, 0

A
2, 0 B 2 Y 1, 1 X B 2 0

Mixed Strategies in Normal and Sequential Form Games

26

Looks familiar?

Subtract 2 from the payoffs of Row.
X 0 2 Y 0 0 0 B 0 -1 1

X 2

Y

A
0 0 B 2 1 2 1

A
-2

It is the South Pacific example. It is easier to solve games for mixed strategy Nash equilibria when a game is represented in normal form. We can always take a sequential game and represent it in normal form. What is, however, the relationship between Nash equilibria in a normal form game and the rollback equilibrium in the corresponding sequential game?
Mixed Strategies in Normal and Sequential Form Games

27

1, 2

2

X XW 2 XZ 2 1 2 YW 3 2 3 1 2 2 YZ 3

A 1

Y

2, 3
1, 3

A B

1

3
1 2

2

B

W

2
Z 2, 2
The rollback equilibrium in this game is (A, YW) There are three Nash equilibria: (A, YW), (A, YZ) and (B, XW) but only one of them is the rollback equilibrium.

Selten: the concept of subgame perfect equilibrium (the rollback equilibrium as we have called it before.)
Mixed Strategies in Normal and Sequential Form Games 28

Si 。在允许混合策略(mixed strategies) 以后,钱币配对及猜拳赛局才有解。 ? ...1.7 小结 策略思考的几点原则: 1. 互动时要先在对手的角度思考,再反思自己...

Nash’s Existence Theorem If we allow mixed strategies, then every game ... x) 3, 7 7, 3 今天购买(1 ? y) 9, 4 4, 9 解 由表 2.3 可以...
Networks, Crowds, and Markets_Notes
Be known as The Game of Chicken, Swerve and Don't Swerve, 6.7 Mixed ...Mixed Strategies: With randomization, a game consists of a set of players,...

talking about pros and cons of mixed marriages and the listening strategies....(第二版)教师用书》 ,2011,外语教学与研究出版社 Unit 7 Relax or Die 课程...

3.3 Mixed Gender Analysis on the Other Five Conversational Strategies错误!未...时代教育(7):105. 王显志. 2010. 英汉语性别歧视现象的对比研究[D]. 北京:...

7页 5财富值如要投诉违规内容,请到百度文库投诉...The word “mixed”in the first paragraph means ...listening strategies that lead to superior ...
DesignDescription

2012年11月北京地区成人本科学位英语统一考试真题及其...
The word “mixed”in the first paragraph means ...So what are these listening strategies? Skilled ...7. What does Vandergrift’s research show? A....
2012年11月学位英语答案及解析(最新)
listening strategies that lead to superior ..."The results have really been mixed", admits ...7. 【答案】 A。 细节题。 根据第二段第一句话...