Mixed Strategy Equilibrium: �Theorems 3 and 4

Roman Sheremeta, Ph.D.

Professor, Weatherhead School of Management

Case Western Reserve University

1

Outline�

• Review
• Theorems 3 and 4
• Experiment #5
• Example: “Rock, paper and scissors”

​

​

​

2

Review�

• A pair of mixed strategies ((r*,1-r*), (q*,1-q*)) is a Mixed Strategy Equilibrium if (r*,1-r*) is a best response to (q*,1-q*), and (q*,1-q*) is a best response to (r*,1-r*)

​

• That is,
• Eu₁((r*,1-r*),(q*,1-q*)) ≥ Eu₁((r,1-r),(q*,1-q*)), for all 0≤r≤1
• Eu₂((r*,1-r*),(q*,1-q*)) ≥ Eu₂((r*,1-r*),(q,1-q)), for all 0≤q≤1

3

r

1-r

1-q

q

Review�

• THEOREM 1: A pair of mixed strategies ((r*,1-r*), (q*,1-q*)) is a Mixed Strategy Nash equilibrium if and only if� Eu₁((r*,1-r*), (q*,1-q*)) ≥ Eu₁(s₁₁, (q*,1-q*))� Eu₁((r*,1-r*), (q*,1-q*)) ≥ Eu₁(s₁₂, (q*,1-q*)) � Eu₂((r*,1-r*), (q*,1-q*)) ≥ Eu₂((r*,1-r*), s₂₁)� Eu₂((r*,1-r*), (q*,1-q*)) ≥ Eu₂((r*,1-r*), s₂₂)

​

• That is, no player can do better by playing a pure strategy

4

r

1-r

1-q

q

Review�

• THEOREM 2: Let ((r*,1-r*),(q*,1-q*)) be a pair of mixed strategies, where 0<r*<1, 0<q*<1. Then ((r*,1-r*), (q*,1-q*)) is a Mixed Strategy Equilibrium if and only if � Eu₁(s₁₁, (q*,1-q*)) = Eu₁(s₁₂, (q*,1-q*))� Eu₂((r*,1-r*), s₂₁) = Eu₂((r*,1-r*), s₂₂)

​

• That is, each player is indifferent between her two pure strategies

5

r

1-r

1-q

q

2-Player Game�

• Set of players:

{Player 1, Player 2}

​

• Sets of strategies:

S₁={s₁₁,s₁₂,...,s_1J}

S₂={s₂₁,s₂₂,...,s_2K}

​

• Payoff functions:

u₁(s_1j,s_2k) for j = 1, 2, ..., J and k = 1, 2, ..., K

u₂(s_1j,s_2k) for j = 1, 2, ..., J and k = 1, 2, ..., K

6

2-Player Game�

• Mixed Strategies:

Player 1’s mixed strategy: p₁=(p₁₁, p₁₂, ..., p_1J )

Player 2’s mixed strategy: p₂=(p₂₁, p₂₂, ..., p_2K )

7

2-Player Game:�Mixed Strategy Equilibrium

• A pair of mixed strategies (p₁*,p₂*), where

p₁*=(p₁₁*,p₁₂*, ...,p_1J*)

p₂*=(p₂₁*,p₂₂*, ...,p_2K*)

• is a Mixed Strategy Nash equilibrium if player 1’s mixed strategy p₁* is a best response to player 2’s mixed strategy p₂*, and p₂* is a best response to p₁*

​

• That is,

Eu₁(p₁*,p₂*) ≥ Eu₁(p₁,p₂*), for all player 1’s mixed strategy p₁

Eu₂(p₁*,p₂*) ≥ Eu₂(p₁*,p₂), for all player 2’s mixed strategy p₂

8

Theorem 3�

• THEOREM 3: A pair of mixed strategies (p₁*,p₂*), where

p₁*=(p₁₁*, p₁₂*, ..., p_1J* )

p₂*=(p₂₁*, p₂₂*, ..., p_2K* )

• is a Mixed Strategy Nash equilibrium if and only if they satisfy the following conditions:

Eu₁(p₁*,p₂*) ≥ Eu₁(s_1j,p₂*), for j = 1, 2, ..., J

Eu₂(p₁*,p₂*) ≥ Eu₂(p₁*,s_2k), for k= 1, 2, ..., K

• That is, no player can do better by playing a pure strategy

9

Theorem 4�

• THEOREM 4: A pair of mixed strategies (p₁*,p₂*), where

p₁*=(p₁₁*, p₁₂*, ..., p_1J* )

p₂*=(p₂₁*, p₂₂*, ..., p_2K* )

• is a Mixed Strategy Nash equilibrium if and only if they satisfy the following conditions:
• Player 1: for any m and n

if p_1m*>0 and p_1n*>0 then Eu₁(s_1m,p₂*) = Eu₁(s_1n,p₂*)

if p_1m*>0 and p_1n*=0 then Eu₁(s_1m,p₂*) ≥ Eu₁(s_1n,p₂*)

• Player 2: for any m and n

if p_2i*>0 and p_2k*>0 then Eu₂(p₁*,s_2i) = Eu₂(p₁*,s_2k)

if p_2i*>0 and p_2k*=0 then Eu₂(p₁*,s_2i) ≥ Eu₂(p₁*,s_2k)

10

Theorem 4:�Implications

• THEOREM 4 implies that we have a Mixed Strategy Nash equilibrium in the following situation:
• Given player 2’s mixed strategy, player 1 is indifferent among the pure strategies to which she assigns positive probability
• The expected payoff of any pure strategy she assigns positive probability is not less than the expected payoff of any pure strategy she assigns zero probability
• The same is true for player 2

11

Theorem 4:�Illustration

• Use THEOREM 4 to check whether p₁=(3/4, 0, 1/4) and p₂=(0, 1/3, 2/3) is a Mixed Strategy equilibrium
• Player 1:

Eu₁(T,p₂) = 0×0 + 3×(1/3) + 1×(2/3) = 5/3

Eu₁(M,p₂) = 4×0 + 0×(1/3) + 2×(2/3) = 4/3

Eu₁(B,p₂) = 3×0 + 5×(1/3) + 0×(2/3) = 5/3

• Hence, Eu₁(T,p₂) = Eu₁(B,p₂) > Eu₁(M,p₂), which satisfies the conditions of THEOREM 4

12

Theorem 4:�Illustration

• Player 2:

Eu₂(p₁,L) = 2×(3/4) + 4×(1/4) = 5/2

Eu₂(p₁,C) = 3×(3/4) + 3×(1/4) = 5/2

Eu₂(p₁,R) = 1×(3/4) + 7×(1/4) = 5/2

• Hence, Eu₂(p₁,C) = Eu₂(p₁,R) ≥ Eu₂(p₁,L), which satisfies the conditions of THEOREM 4
• Therefore, p₁=(3/4, 0, 1/4) and p₂=(0, 1/3, 2/3) is a Mixed Strategy equilibrium by THEOREM 4

​

13

Rock, Paper and Scissors�

• Each of two players simultaneously announces either Rock, or Paper, or Scissors
• Paper beats Rock, Rock beats Scissors, and Scissors beats Paper
• The player who names the winning object receives $1 from her opponent
• If both players name the same choice then no payment is made

14

Experiment #5: Rock, Paper and Scissors�

• I need two volunteers

15

Experiment #5: Rock, Paper and Scissors�

• What is the optimal strategy in “Rock, Paper and Scissors” game?
• http://www.youtube.com/watch?v=kH50-giCeDM

​

16

Rock, Paper and Scissors�

• Here is a conversation between Bart and Lisa:
• Lisa: Look, there's only one way to settle this. Rock-paper-scissors.
• Lisa's brain: Poor predictable Bart. Always takes `rock'.
• Bart's brain: Good ol' `rock'. Nuthin' beats that!
• Bart: Rock!
• Lisa: Paper.
• Bart: D'oh!”

​

• Obviously, Bart will never win this game because he does not understand the concept of Mixed Strategy

17

Rock, Paper and Scissors�

• Can you guess a Mixed Strategy Nash equilibrium?
• Check whether there is a mixed strategy Nash equilibrium (p₁*,p₂*) in which p₁₁>0, p₁₂>0, p₁₃>0, p₂₁>0, p₂₂>0, p₂₃>0.
• If each player assigns positive probability to every of her pure strategy, then by THEOREM 4, each player is indifferent among her three pure strategies

18

Rock, Paper and Scissors�

• Player 1 is indifferent among her three pure strategies

​

• This implies that: Eu₁(Rock, p₂) = Eu₁(Paper, p₂) = Eu₁(Scissors, p₂)

​

• Together with p₂₁+p₂₂+p₂₃=1, we have three equations and three unknowns

19

Rock, Paper and Scissors�

• The three equations are: Eu₁(Rock, p₂) = Eu₁(Paper, p₂) Eu₁(Rock, p₂) = Eu₁(Scissors, p₂) p₂₁ + p₂₂ + p₂₃ = 1
• Substituting the appropriate expressions: 0×p₂₁ + (-1)×p₂₂ + 1×p₂₃ = 1×p₂₁ + 0×p₂₂ + (-1)×p₂₃ 0×p₂₁ + (-1)×p₂₂ + 1×p₂₃ = (-1)×p₂₁ + 1×p₂₂ + 0×p₂₃ p₂₁ + p₂₂ + p₂₃ = 1
• The solution is p₂₁=p₂₂=p₂₃=1/3

20

Rock, Paper and Scissors�

• Player 2 is indifferent among her three pure strategies

​

• This implies that: Eu₂(p₁, Rock) = Eu₂(p₁, Paper) = Eu₂(p₁, Scissors)

​

• Together with p₁₁+p₁₂+p₁₃=1, we have three equations and three unknowns

21

Rock, Paper and Scissors�

• The three equations are: Eu₂(p₁, Rock) = Eu₂(p₁, Paper) Eu₂(p₁, Rock) = Eu₂(p₁, Scissors) p₁₁ + p₁₂ + p₁₃ = 1
• Substituting the appropriate expressions: 0×p₁₁ + (-1)×p₁₂ + 1×p₁₃ = 1×p₁₁ + 0×p₁₂ + (-1)×p₁₃ 0×p₁₁ + (-1)×p₁₂ + 1×p₁₃ = (-1)×p₁₁ + 1×p₁₂ + 0×p₁₃ p₁₁ + p₁₂ + p₁₃ = 1
• The solution is p₁₁=p₁₂=p₁₃=1/3

22

Rock, Paper and Scissors�

• It is easy to see that when p₁*=(1/3, 1/3, 1/3) and p₂*=(1/3, 1/3, 1/3) then:

Eu₁(Rock, p₂) = Eu₁(Paper, p₂) = Eu₁(Scissors, p₂) = 0

Eu₂(p₁, Rock) = Eu₂(p₁, Paper) = Eu₂(p₁, Scissors) = 0

• Therefore (p₁*,p₂*) is a Mixed Strategy Nash equilibrium by THEOREM 4

​

• Are we done?
• No! We still need to check several possible solutions…

23

Rock, Paper and Scissors�

• p₁₁=0, p₁₂>0, p₁₃>0, p₂₁>0, p₂₂>0, p₂₃>0.
• p₁₁>0, p₁₂=0, p₁₃>0, p₂₁>0, p₂₂>0, p₂₃>0.
• p₁₁>0, p₁₂>0, p₁₃=0, p₂₁>0, p₂₂>0, p₂₃>0.
• p₁₁=0, p₁₂=0, p₁₃>0, p₂₁>0, p₂₂>0, p₂₃>0.
• p₁₁=0, p₁₂>0, p₁₃=0, p₂₁>0, p₂₂>0, p₂₃>0.
• p₁₁>0, p₁₂=0, p₁₃=0, p₂₁>0, p₂₂>0, p₂₃>0.
• p₁₁>0, p₁₂>0, p₁₃>0, p₂₁=0, p₂₂>0, p₂₃>0.
• p₁₁>0, p₁₂>0, p₁₃>0, p₂₁>0, p₂₂=0, p₂₃>0.
• p₁₁>0, p₁₂>0, p₁₃>0, p₂₁>0, p₂₂>0, p₂₃=0.
• p₁₁>0, p₁₂>0, p₁₃>0, p₂₁=0, p₂₂=0, p₂₃>0.
• p₁₁>0, p₁₂>0, p₁₃>0, p₂₁=0, p₂₂>0, p₂₃=0.
• … a total of 64 cases (technically 49), however, none of these is an equilibrium!

​

24

Rock, Paper and Scissors�

• Behavior in “Rock, Paper and Scissors” game:
• https://www.youtube.com/watch?v=rudzYPHuewc&feature=emb_logo

​

​

25

Exercise�

• Find all pure-strategy Nash equilibria?

(B,L)

(T,R)

​

• Find all Mixed Strategy Nash equilibria?
• By THEOREM 4, we need to consider 15 cases!
• Some cases are very easy…

26

Exercise: Case 1�

• (1) Check whether there is a mixed strategy in which p₁₁>0, p₁₂>0, p₂₁>0, p₂₂>0, p₂₃>0
• (2) We should have for player 2: � 2×p₁₁ + 2×p₁₂ = 3×p₁₁ + 1×p₁₂ = 3×p₁₁ + 2×p₁₂ p₁₁ + p₁₂ = 1
• (3) We should have for player 1: 2×p₂₁ + 0×p₂₂ + 1×p₂₃ = 3×p₂₁ + 1×p₂₂ + 0×p₂₃ p₂₁ + p₂₂ + p₂₃ = 1
• If a solution satisfies (1), (2), and (3) then we have a Mixed Strategy equilibrium. But it is easy to check that (2) cannot be satisfied.

27

Exercise: Case 2�

• (1) Check whether there is a mixed strategy in which p₁₁>0, p₁₂>0, p₂₁>0, p₂₂>0, p₂₃=0
• (2) We should have for player 2: � 2×p₁₁ + 2×p₁₂ = 3×p₁₁ + 1×p₁₂ ≥ 3×p₁₁ + 2×p₁₂ p₁₁ + p₁₂ = 1
• (3) We should have for player 1: 2×p₂₁ + 0×p₂₂ + 1×p₂₃ = 3×p₂₁ + 1×p₂₂ + 0×p₂₃ p₂₁ + p₂₂ + p₂₃ = 1
• If a solution satisfies (1), (2), and (3) then we have a Mixed Strategy equilibrium. But it is easy to check that (2) cannot be satisfied.

28

Exercise: Case 3�

• (1) Check whether there is a mixed strategy in which p₁₁>0, p₁₂>0, p₂₁>0, p₂₂=0, p₂₃>0
• (2) We should have for player 2: � 2×p₁₁ + 2×p₁₂ = 3×p₁₁ + 2×p₁₂ ≥ 3×p₁₁ + 1×p₁₂ p₁₁ + p₁₂ = 1
• (3) We should have for player 1: 2×p₂₁ + 0×p₂₂ + 1×p₂₃ = 3×p₂₁ + 1×p₂₂ + 0×p₂₃ p₂₁ + p₂₂ + p₂₃ = 1
• If a solution satisfies (1), (2), and (3) then we have a Mixed Strategy equilibrium. But it is easy to check that (2) cannot be satisfied.

29

Exercise: Case 4�

• (1) Check whether there is a mixed strategy in which p₁₁>0, p₁₂>0, p₂₁=0, p₂₂>0, p₂₃>0
• (2) We should have for player 2: � 2×p₁₁ + 2×p₁₂ ≤ 3×p₁₁ + 1×p₁₂ = 3×p₁₁ + 2×p₁₂ p₁₁ + p₁₂ = 1
• (3) We should have for player 1: 2×p₂₁ + 0×p₂₂ + 1×p₂₃ = 3×p₂₁ + 1×p₂₂ + 0×p₂₃ p₂₁ + p₂₂ + p₂₃ = 1
• If a solution satisfies (1), (2), and (3) then we have a Mixed Strategy equilibrium. But it is easy to check that (2) cannot be satisfied.

30

Rock, Paper and Scissors�

• All Cases from 5 to 15 are relatively easy because one player is playing a pure strategy equilibrium…
• Case 5: p₁₁>0, p₁₂>0, p₂₁>0, p₂₂=0, p₂₃=0
• Case 6: p₁₁>0, p₁₂>0, p₂₁=0, p₂₂>0, p₂₃=0
• Case 7: p₁₁>0, p₁₂>0, p₂₁=0, p₂₂=0, p₂₃>0
• Case 8: p₁₁>0, p₁₂=0, p₂₁>0, p₂₂>0, p₂₃>0
• Case 9: p₁₁>0, p₁₂=0, p₂₁>0, p₂₂>0, p₂₃=0
• Case 10: p₁₁>0, p₁₂=0, p₂₁>0, p₂₂=0, p₂₃>0
• Case 11: p₁₁>0, p₁₂=0, p₂₁=0, p₂₂>0, p₂₃>0
• Mixed Strategy equilibrium:((1,0),(0,p₂₂,1-p₂₂)) for 0<p₂₂≤0.5
• Case 12: p₁₁=0, p₁₂>0, p₂₁>0, p₂₂>0, p₂₃>0
• Case 13: p₁₁=0, p₁₂>0, p₂₁>0, p₂₂>0, p₂₃=0
• Case 14: p₁₁=0, p₁₂>0, p₂₁>0, p₂₂=0, p₂₃>0
• Mixed Strategy equilibrium:((0,1),(p₂₁,0,1-p₂₁)) for 0.5≤p₂₁<1
• Case 15: p₁₁=0, p₁₂>0, p₂₁=0, p₂₂>0, p₂₃>0

31

Exercise�

• This game has two pure-strategy Nash equilibria:

(B,L)

(T,R)

​

• It also has infinite amount of Mixed Strategy Nash equilibria:

((1,0),(0,p₂₂,1-p₂₂)) for any 0<p₂₂≤0.5

((0,1),(p₂₁,0,1-p₂₁)) for and 0.5≤p₂₁<1

32

P vs NP�

• Computational Complexity Theory deals with the resources required during computation to solve a given problem
• The class P (quickly solvable) consists of decision problems that can be solved efficiently
• The class NP (quickly verifiable) consists of decision problems whose solutions can be verified efficiently

​

• Daskalakis et al. (2009) proved that the Nash equilibrium belongs to the class NP
• “This suggests that the Nash equilibrium may not be an accurate predictor of rational behavior in all strategic environments, since it may be too difficult for people to compute the Nash equilibrium”

33

All-pay Auction (Contest)�

• Next Time!

34

Thank you!

Roman Sheremeta, Ph.D.

Professor, Weatherhead School of Management

Case Western Reserve University

35

References�

• Watson, J. (2013). Strategy: An Introduction to Game Theory (3rd Edition). Publisher: W. W. Norton & Company. (Chapters 4 & 11)
• Daskalakis, C., Goldberg, P.W., & Papadimitriou, C.H. (2009). The complexity of computing a Nash equilibrium. SIAM Journal on Computing, 39, 195-259.

​

​

36