Assignment on Mixed Strategy
Handout 6
ECO 444
Konrad Grabiszewski
Mixed Strategy
Take a game in the normal form, G = (N; S1, …,SN ; u1, …,uN ). We say that G is a finite game
if every set of strategies Si is a finite set. In this handout, we only consider finite games.
Take si ∈ Si. We say that si is a pure strategy of player i and Si is the set of pure strategies
of player i. A mixed strategy of player i is a probability distribution over Si. Let ∆(Si) denote
the set of mixed strategies of player i. A generic mixed strategy of player i is denoted by αi and
αi(si) is a probability assigned to pure strategy si by the mixed strategy αi. Note that a pure
strategy si is the same as a mixed strategy αi with αi(si) = 1 and αi(s ′ i) = 0 for s
′ i 6= si.
Consider the following example.
Bob
L R
Ann T 2,0 0,1
B 0,1 4,0
Let αA = (p, 1 − p) be Ann’s mixed strategy where p is the weight assigned to strategy T. Let
αB = (q, 1 − q) be Bob’s mixed strategy where q is the weight assigned to strategy L.1
A mixed extension of G is Γ = (N; ∆(S1), …, ∆(SN ); EU1, …,EUN ) where EUi is the expected
utility function of player i. A profile of mixed strategies is denoted by α = (α1, …,αN ) ∈ ∆(S1)×
…×∆(SN ). If we assume the independence of the randomizations, then a profile of mixed strategies
α = (α1, …,αN ) assigns probability λ(s) to the profile of pure strategies s = (s1, …,sN ),
λ(s) = Πj∈Nαj(sj) = α1(s1) · … ·αN (sN ). (1)
1For example, strategy αA = ( 1 3 , 2 3
) is Ann’s mixed strategy that assigns probability 1
3 to pure strategy T and
probability 2 3
to pure strategy B. As another example, consider αB = (0, 1) which is Bob’s mixed strategy that assigns probability 1 to pure strategy R. In other words, this specific mixed strategy is a pure strategy R.
1
The expected utility EUi is defined as
EUi(α) = Σs∈Sui(s) ·λ(s). (2)
A profile of mixed strategies α∗ is a mixed strategy Nash equilibrium (MSNE) in game Γ if
the following holds for each player i:
EUi(α ∗ i ,α
∗ −i) ≥ EUi(αi,α
∗ −i) ∀αi ∈ ∆(Si) (3)
That is, α∗ is an MSNE if and only if each player’s mixed strategy α∗i is a best response to α ∗ −i
where player i’s best-response correspondence is defined in the following way.
BRi(α−i) = {αi ∈ ∆(Si) such that EUi(αi,α−i) ≥ EUi(α′i,α−i) ∀α ′ i ∈ ∆(Si)} (4)
Nash Theorem
Every finite game has at least one MSNE.
In the 2 × 2 matrix on page 1 there is no Nash equilibrium in pure strategies. However, because
of the Nash theorem, there exists at least one MSNE. Let (α∗A,α ∗ B) denote an MSNE where
α∗A = (p ∗, 1 −p∗) and α∗B = (q
∗, 1 − q∗) is Ann’s and Bob’s equilibrium strategy, respectively.
In order to find (α∗A,α ∗ B), we need to (i) identify Ann’s and Bob’s best-response correspondences,
and (ii) find where they cross. Let BRA(αB) be Ann’s best-response correspondence: for each
mixed strategy of Bob αB, BRA(αB) is the collection of Ann’s mixed strategies that maximize her
expected utility. Similarly, we have BRB(αA).
We identify Ann’s best-response correspondence in the following way. Let EUA(sA,αB) be Ann’s
expected utility from playing a pure strategy sA when Bob’s mixed strategy is αB.
EUA(T,αB) = 2 · q + 0 · (1 − q) = 2q (5)
EUA(B,αB) = 0 · q + 4 · (1 − q) = 4 − 4q (6)
2
Hence, the following is true.
EUA(T,αB) > EUA(B,αB) ⇔ q > 2
3 (7)
EUA(T,αB) = EUA(B,αB) ⇔ q = 2
3 (8)
EUA(T,αB) < EUA(B,αB) ⇔ q < 2
3 (9)
The first row tells us that if q > 2 3 , then choosing strategy T with probability one generates strictly
higher expected utility for Ann than playing strategy B with probability one. In other words, in
this case playing T is Ann’s best response; more formally, (1, 0) is Ann’s unique best response.
The second row tells us that if q = 2 3 , then it does not really matter what Ann chooses: playing
T with probability one, or playing B with probability one, or mixing between T and B will yield
the same expected gain. The third row tells us that if q < 2 3 , the choosing B with probability one
is the best response. We formally describe Ann’s best-response correspondence.
BRA(αB) =
{(1, 0)} if αB is such that q > 23
{(p, 1 −p) : p ∈ [0, 1]} if αB is such that q = 23
{(0, 1)} if αB is such that q < 23
(10)
We identify Bob’s best-response correspondence using the same approach. Let EUB(αA,sB) be
Bob’s expected utility from playing a pure strategy sB when Ann’s mixed strategy is αA.
EUB(αA,L) = 0 ·p + 1 · (1 −p) = 1 −p (11)
EUB(αA,R) = 1 · q + 0 · (1 −p) = p (12)
Hence, the following is true.
EUB(αA,L) > EUB(αA,R) ⇔ p < 1
2 (13)
EUB(αA,L) = EUB(αA,L) ⇔ p = 1
2 (14)
EUB(αA,L) < EUB(αA,L) ⇔ p > 1
2 (15)
3
We formally describe Bob’s best-response correspondence.
BRB(αA) =
{(1, 0)} if αA is such that p < 12
{(q, 1 − q) : q ∈ [0, 1]} if αA is such that p = 12
{(0, 1)} if αA is such that p > 12
(16)
Ann’s best-response correspondence as described in (10) and Bob’s best-response correspondence
as described in (16) look rather complicated. However, in the case of 2 × 2 matrices, we can
simplify the notation and, in fact, graphically visualize best-response correspondences. Instead
of writing αA = (p, 1 − p) we can simply say that p is Ann’s mixed strategy. (Why?) Similarly,
instead of αB = (q, 1 − q) we can use q as Bob’s mixed strategy.
Hence, for each q ∈ [0, 1] (Bob’s mixed strategy, Ann’s best-response correspondence BRA(q) gives
a set of singleton. Similarly for Bob.
We re-write BRA(q) and BRB(p).
BRA(q) =
{1} if q > 2
3
[0, 1] if q = 2 3
{0} if q < 2 3
(17)
BRB(p) =
{1} if p < 1
2
[0, 1] if p = 1 2
{0} if p > 1 2
(18)
4
We graphically represent Ann’s and Bob’s best-response correspondences based on (17) and (18),
respectively.
p
q
1
1 ⅔
Figure 1: Ann’s best-response correspondence BRA as the solid line.
q
p
1
1 ½
Figure 2: Bob’s best-response correspondence BRB as the dashed line.
5
In order to find MSNE, we need to depict BRA and BRB in the same graph.
p
q
1
1 ⅔
½
Figure 3: BRA and BRB in the same graph.
A point at which the best-response correspondences intersect is an MSNE. In our case, p∗ = 1 2
and q∗ = 2 3 . Formally,
(( 1 2 , 1 2
) , ( 2 3 , 1 3
)) is the MSNE in our example.
6