Mixed Strategy Nash Equilibrium

Sanjay Singh

1
Department of Information and Communication Technology
Manipal Institute of Technology, MAHE
Manipal-576104, INDIA
sanjay.singh@manipal.edu
2
Centre for Artificial and Machine Intelligence (CAMI)
MAHE, Manipal-576104, INDIA

April 10, 2021

Sanjay Singh MSNE 1

A strategy profile with an outcome which is simultaneously the smallest number in

its row and the largest number in its column are the best response to each other, and
that both players are guaranteed to do no worse than this value.

Definition (Saddle Point)

An outcome in a matrix game (with payoff to row player) is called a saddle point if
the entry at that outcome is both less than or equal to any entry in its row, and greater
than or equal to any entry in its column.

Definition (Saddle Point Principle)

If a matrix game has a saddle point, both players should play a strategy which
contains it.

Definition (Game Value)

For any matrix game, if there is a number v such that Rose (row player) has a strategy
which guarantees that she will get at least v, and Colin (column player) has a strategy
which guarantees that Rose will get no more than v, then v is called the value of the
game.

Sanjay Singh MSNE 2

 Colin
A B C D
A 4 2 5 2
Rose B 2 1 -1 -20
C 3 2 4 2
D -16 0 16 1

All four of the circled outcomes are saddle point

These are the only saddle points
The strategy profile (B, A) is not a saddle point
If the maxmin of rows and minmax of columns are the same,
then they appear at saddle point strategies
When the maxmin and minmax are different, the game has no
saddle point

Sanjay Singh MSNE 3

Only sensible plan is to use

Colin some random device to decide
A B
Rose which strategy to play
A 2 -3
B 0 3 For example, Rose may flip a
coin to decide between A and B
There is no saddle point in this Such a plan, which involves
game playing a mixture of strategies
Neither player would want to according to certain fixed
play a single strategy with probabilities, is called mixed
certainty strategy

Other player could take The contrasting plan of playing

advantage of such a choice one strategy with certainty is
called a pure strategy

Sanjay Singh MSNE 4

 To analyze the effect of one or both players using mixed strategy,
we use the concept of expected value
The expected value of getting payoffs a1 , . . . , ak with respective
probabilities p1 , . . . , pk is given by

p1 a1 + p2 a2 + . . . + pk ak

Expected Value Principle

If you know that your opponent is playing a given mixed strategy, and
will continue to play it regardless of what you do, you should play
your strategy which has the largest expected value.

Sanjay Singh MSNE 5

Colin
A B
Rose
A 2 -3
B 0 3

Consider the scanario wherein Colin decides to use mixed

strategy with different probabilities
Might there be some choice of probabilities which Rose could
not take advantage of?
To find, suppose Colin plays a mixed strategy with probabilities
x for A and (1 − x) for B
The Rose’s expected value for A and B is given by:
Rose A: x(2) + (1 − x)(−3) = −3 + 5x
Rose B: x(0) + (1 − x)(3) = 3 − 5x

Sanjay Singh MSNE 6

 Rose will not be able to take advantage of Colin’s mixed strategy
if these two expected values are same:
3
−3 + 5x = 3 − 3x ⇒ x =
4
3 1
If Colin plays mixed strategy A and B, Colin can assure that
4 4
3
Rose wins on average, no more than unit per game, regardless
4
of how Rose plays

Sanjay Singh MSNE 7

Figure 1: Game with oddments, and mixed strategy probability calculation

Value of the game is computed as:

2 × 6 + (−3) × 2 3
= using R1
6+2 4
0×6+3×2 3
= using R2
6+2 4
2×3+0×5 3
= using C1
3+5 4
(−3) × 3 + 3 × 5 3
= using C2
3+5 4
Sanjay Singh MSNE 8
Now consider the games with 2 × n or m × 2
If such a game doesn’t have saddle point, it has a mixed strategy
solution to one of its 2 × 2 subgames
For large m or n there could be large number of 2 × 2 subgames
to try
There is an elegant graphical way to find which 2 × 2 subgame
gives solution to the game

Sanjay Singh MSNE 9

For each Rose strategy, mark the payoff if Colin

plays A on the left axis
Payoff if Colin plays B on the right axis, and connect
them with a line
The vertical coordinate of this line above any point x
gives Rose’s expected payoff if Colin plays mixed
strategy (1 − x)A, xB
If Rose knew Colin’s mixed strategy, she would take
advantage by choosing best response (i.e outcome
would lie on the upper envelope of graph)
Colin would choose x to make the corresponding
payoff to Rose as small as possible to get the lowest
point on the upper envelope
Such a point (circled) is at the intersection of lines for
Rose A and Rose B

Sanjay Singh MSNE 10

The appropriate game to solve is
Colin Rose
A B probabilities
Rose
A 2 -3 2/7
B 0 2 5/7
Colin prob 5/7 2/7
Rose expectations if Colin plays (5/7)A, (2/7)B:
5 2 4
Rose A: (2) + (−3) =
7 7 7
5 2 4
Rose B: (0) + (2) =
7 7 7
5 2 5
Rose C: (−5) + (10) = −
7 7 7
Colin expectations if Rose plays (2/7)A, (5/7)B, (0)C:
2 5 4
Colin A: (2) + (0) + (0)(−5) =
7 7 7
2 5 4
Colin B: (−3) + (2) + (0)(10) =
7 7 7
Sanjay Singh MSNE 11

All of Rose’s expectations are ≤ 4/7, and all of Colin’s

expectations are ≥ 4/7
Colin assures that Rose will not get get more than 4/7 and Rose
assures that she will not get less than 4/7
Thus, the value of the game is 4/7

Sanjay Singh MSNE 12

Interpretation of these results on graph

The lowest point on the upper envelope lies

2 5
above x = ( of the way toward Colin A)
7 7
The vertical coordinate of this point (i.e
4
horizontal projection on left axis) is at ,
7
the value of the game
2
The vertical project on Rose C at x = has
7
5
vertical coordinate − , which is lower than
7
the value of the game, hence Rose C should
not be used

Sanjay Singh MSNE 13

A 2 × n game

A B C D E
A -2 5 1 0 -4
B 3 -3 -1 3 8

Colin would try to choose her strategy to

stay on the lower envelope
Rose would want to choose x to get the
highest point on the lower envelope, which
is obtained at intersection of A and C
The reduced 2 × 2 game has only strategy
A and C for Colin
The optimal mixed strategies are
2 5 4 3
Colin : ( , 0, , 0, 0), Rose : ( , )
7 7 7 7

Sanjay Singh MSNE 14

What is game value?
Rose expectation against Colin optimal
2 5 1
Rose A: (−2) + (1) =
7 7 7
2 5 1 The value of the game
Rose B: (3) + (−1) = 1
7 7 7 is
Colin expectation against Rose optimal 7
4 3 1 All of Colin’s
Colin A: (−2) + (3) = expectations against
7 7 7 1
4 3 11 Rose optimal are ≥
Colin B: (5) + (−3) = 7
7 7 7 Even if one had been
4 3 1 1
Colin C: (1) + (−1) = less than , we would
7 7 7 7
4 3 9 infer that there is error
Colin D: (0) + (3) = in claimed solution
7 7 7
4 3 8
Colin E: (−4) + (8) =
7 7 7

Sanjay Singh MSNE 15

m × n game

Theorem (Minimax Theorem)

Every m × n matrix game has a solution. That is, there is a unique
number v, called the value of the game, and there are optimal (pure or
mixed) strategies for Rose and Colin such that
1 if Rose plays her optimal strategy, Rose’s expected payoff will be
≥ v, no matter what Colin does, and
2 if Colin plays her optimal strategy, Rose’s expected payoff will
be ≤ v, no matter what Rose does.

The solution of a m × n can always be found as the solution to

some k × k subgame of original game
The pure strategies which are involved in solution are called
active strategies
Active strategies should be played according to certain
probabilities, and other strategies should not be played at all
Sanjay Singh MSNE 16
 Colin
A B C
Rose
A 1 2 2
B 2 1 2
C 2 2 0

Let us solve this 3 × 3 game by method of equalizing

expectations
This game does not have a saddle point
Suppose Colin plays A,B,and C with probabilities
(x, y, 1 − x − y), the Rose’s expectations are:
Rose A: x(1) + y(2) + (1 − x − y)(2) = 2 − x
Rose B: x(2) + y(1) + (1 − x − y)(2) = 2 − y
Rose C: x(2) + y(2) + (1 − x − y)(0) = 2x + 2y

Sanjay Singh MSNE 17

Rose will be unable to take advantage of Colin’s mixed strategy

if these expectations are equal:
2 − x = 2 − y = 2x + 2y
These equations give a system of two equations in two
unknowns:
x−y=0
2x + 3y = 2
2
On solving, we get x = y =
5
Hence,
 Colin’s
 expectation-equalizing mixed strategy is
2 2 1
, ,
5 5 5
By symmetry of the matrix, this is also Rose’s
expectation-equalizing mixed strategy
These strategies do give a solution, and the value of the game is
8
5
Sanjay Singh MSNE 18
 The method of expectation-equalization fails if the solution to
the 3 × 3 game involves a 1 × 1 or 2 × 2 subgame
We should check for saddle point and dominance before trying
for expectation-equalization
If equalizing expectation fails, then we should for a 2 × 2
solution
The best way to do is to use graphical analysis on three 2 × 3
subgames

A B C
A 1 2 2
B 2 1 2
C 2 2 0

A B C A B C A B C
A 1 2 2 B 2 1 2 A 1 2 2
B 2 1 2 C 2 2 0 C 2 2 0

Sanjay Singh MSNE 19

Some definitions

Definition (Pure Strategy)

A pure strategy defines a specific move or action that a player will
follow in every possible attainable situation in a game. Such moves
may not be random, or drawn from a distribution, as in the case of
mixed strategies

Definition (Mixed Strategy)

A strategy consisting of possible moves and a probability distribution
(collection of weights) which corresponds to how frequently each
move is to be played. A player would only use a mixed strategy when
she is indifferent between several pure strategies, and when keeping
the opponent guessing is desirable - that is, when the opponent can
benefit from knowing the next move.

Sanjay Singh MSNE 20

Mixed Strategies

Consider a strategic form game Γ = hN, (Si ), (ui )i

Item of Si are called actions or pure strategy of player i
If player i chooses a strategy in Si according to a probability
distribution, we have mixed strategy

Definition (Mixed Strategy)

Given a player i with Si as the set of pure strategies, a mixed strategy
(a.k.a randomized strategy) σi of player i is a probability distribution
over Si . That is, σi : Si 7→ [0, 1] is a mapping that assigns to each pure
strategy si ∈ Si , a probability σi (si ) such that
X
σi (si ) = 1.
si ∈Si

Sanjay Singh MSNE 21

A pure strategy of a player, say si ∈ Si , can be considered as a mixed

strategy that assigns a probability 1 to si and probability 0 to all other
strategies of player i
Such a mixed strategy is called a degenerate mixed strategy and is
denoted by e(si ) or si
If Si = {si1 , si2 , . . . , sim }, then set of all mixed strategies of player i is
the set of probability distribution on set Si
∆(Si ) =
 
 m
X 
m
(σ , σ , . . . , σim ) ∈ R : σij ≥ 0 for j = 1, . . . , m and σij = 1
 i1 i2 
j=1

Set ∆(Si ) is called the mixed extension of Si

Using the mixed extension of strategy set, we can define a mixed
extension of the pure strategy game Γ = hN, (Si ), (ui )i
The mixed extension of Γ is denoted as ΓME = hN, (∆(Si )), (Ui )i
For i = 1, 2, . . . , n, Ui is a mapping that maps mixed strategy profiles
to real numbers: Ui : ×i∈N ∆(Si ) → R or
Ui : ∆(S1 ) × ∆(S2 ) × . . . × ∆(Sn ) 7→ R
Sanjay Singh MSNE 22
 Given σi ∈ ∆(Si ) for i = 1, 2, . . . , n we compute Ui as follows
We make the standard assumption that the randomization of
individual players are mutually independent
It implies that given a mixed strategy profile (σ1 , . . . , σn ), the
random variables σ1 , . . . , σn are mutually independent
Joint probability of a pure strategy profile (s1 , s2 , . . . , sn ) is given
by Y
σ(s1 , . . . , sn ) = σi (si )
i∈N

The payoff functions Ui are defined as

X
Ui (σ1 , . . . , σn ) = σ(s1 , . . . , sn )ui (s1 , . . . , sn )
(s1 ,...,sn )∈Si

Ui (σ1 , . . . , σn ) for i = 1, . . . , n is the expected payoff when the

profiles (s1 , . . . , sn ) are chosen according to joint distribution σ
When there is no confusion we’ll write ui instead of Ui , that is,
instead of Ui (σ1 , . . . , σn ) we’ll write ui (σ1 , . . . , σn )
Sanjay Singh MSNE 23

Mixed Strategies in BOS Problem

2
1
A B
A 2,1 0,0
B 0,0 1,2

Suppose (σ1 , σ2 ) is a mixed strategy profile

It means that σ1 is a probability distribution on S1 = {A, B} and
σ2 is a probability distribution on S2 = {A, B}
Lets represent σ1 = (σ1 (A), σ1 (B)); σ2 = (σ2 (A), σ2 (B))
We have S = S1 × S2 = {(A, A), (A, B), (B, A), (B, B)}, we’ll
compute the payoff function u1 and u2
X
For i = 1, 2, ui (σ1 , σ2 ) = σ(s1 , s2 )ui (s1 , s2 )
(s1 ,s2 )∈S

Sanjay Singh MSNE 24

 The function u1 can be computed as

u1 (σ1 , σ2 ) = σ1 (A)σ2 (A)u1 (A, A) + σ1 (A)σ2 (B)u1 (A, B)

+ σ1 (B)σ2 (A)u1 (B, A) + σ1 (B)σ2 (B)u1 (B, B)
= 2σ1 (A)σ2 (A) + σ1 (B)σ2 (B)
= 2σ1 (A)σ2 (A) + (1 − σ1 (A))(1 − σ2 (A))
= 1 + 3σ1 (A)σ2 (A) − σ1 (A) − σ2 (A)

Similarly, we can get

u2 (σ1 , σ2 ) = 2 + 3σ1 (A)σ2 (A) − 2σ1 (A) − 2σ2 (A)
2 1 1 2
Suppose σ1 ( , ) and σ2 ( , ), then
3 3 3 3
2 2
u1 (σ1 , σ2 ) = ; u2 (σ1 , σ2 ) =
3 3
Values of u1 (σ1 , σ2 ) and u2 (σ1 , σ2 ) are same due to the structure
of payoff matrix

Sanjay Singh MSNE 25

Digression
Inequalities

Inequalities and intervals

x>a (a, ∞)
x≥a [a, ∞)
x<a (−∞, a)
x≤a (−∞, a]
Addition and subtraction property for inequalities
If a < b then a + c < b + c
If a > b then a − c > b − c
Addition or subtraction does not change the sense of inequality
Multiplication and division property for inequality
If a < b AND c is positive then ac < bc
a b
If a < b AND c is positive then <
c c
If a < b AND c is negative then ac > bc
a b
If a < b AND c is negative then >
c c

Sanjay Singh MSNE 26

 Solving linear inequalities
Procedure for solving linear inequalities in one variable is
similar to solving basic equations
We need to be careful about the sense of the equality when
multiplying or dividing by negative numbers
Solving non-linear inequalities
Rewrite the inequality so that there is a zero on the right side
Find all linear factors of the function
To find the critical values, set each linear function to zero and
solve for x
Determine the sign of the function in the intervals formed by the
critical values
The solution will be those intervals in which the function has the
correct signs satisfying the inequality

Sanjay Singh MSNE 27

Solve inequality x2 − 3 > 2x.

x2 − 2x − 3 > 0, which can be factored to give (x + 1)(x − 3) > 0
Setting both factors to 0, we get critical values as x = −1, and
x=3
These critical values divide the number line into 3 intervals
x < −1
−1 < x < 3
x>3
For the interval, x < −1, the value of (x + 1) and (x − 3) will be
negative
So, in the interval x < −1, the value of function x2 − 2x − 3 will
be −ve × −ve = +ve
We continue doing this for the other 2 intervals and summarize
the results in a table (given on next slide) as

Sanjay Singh MSNE 28

 Interval (x + 1) (x − 3) Sign of f (x)
x < −1 - - +
−1 < x < 3 + - -
x>3 + + +

We are solving for (x + 1)(x − 3) > 0

The intervals that satisfy this inequality will be those where f (x)
has a positive sign
Hence, the solution is either x < −1 or x > 3

Sanjay Singh MSNE 29

BRock BScissors BPaper

ARock 0 1 -1
AScissors -2 0 2
APaper 1 -1 0
1 1 1
, . -1/3 0 1/3
3 3 3
1 1 1
, . 0 -1/4 1/4
4 4 2
2 1 2
, . 0 0 0
5 5 5
p1 , p2 , p3 p1 .0 + p2 .(−2) + p3 .1 p1 .1 + p2 .0 + p3 .(−1) p1 .(−1) + p2 .2 + p3 .0

Smallest entries in first six rows are, -1,-2,-1,-1/3, -1/4, and 0

Among the six strategies, the one with largest guarantee for player A is the
2 1 2
strategy mix, , .
5 5 5
Remember that there are infinitely many possible rows
Might there be rows with better guarantees?

Sanjay Singh MSNE 30

Mixed Maxmin Strategy

B
A
Left Middle Right
Up A1,1 , B1,1 A1,2 , B1,2 A1,3 , B1,3
Middle A2,1 , B2,1 A2,2 , B2,2 A2,3 , B2,3
Down A3,1 , B3,1 A3,2 , B3,2 A3,3 , B3,3

Player A’s task is to maximize the minimum of three values:

p1 .A1,1 + p2 .A2,1 + p3 .A3,1
p1 .A1,2 + p2 .A2,2 + p3 .A3,2
p1 .A1,3 + p2 .A2,3 + p3 .A3,3
3
X
by choosing her probabilities p1 , p2 , and p3 such that pi = 1
i=1

Sanjay Singh MSNE 31

We can reformulate the problem stated on last slide as

1 Player A has to choose four values v, p1 , p2 , and p3 satisfying
2 p1 ≥ 0
p2 ≥ 0
p3 ≥ 0
p1 + p2 + p3 = 1
v ≥ p1 .A1,1 + p2 .A2,1 + p3 .A3,1
v ≥ p1 .A1,2 + p2 .A2,2 + p3 .A3,2
v ≥ p1 .A1,3 + p2 .A2,3 + p3 .A3,3
3 Such that v is maximized
It is a linear program, which can be solved using simplex
method

Sanjay Singh MSNE 32

Mixed Strategy Nash Equilibria
Definition (Mixed Strategy Nash Equilibria)
Given a strategic form game Γ = hN, (Si ), (ui )i, a mixed strategy
profile σ1∗ , . . . , σn∗ is called a Nash equilibrium if ∀i ∈ N,

ui (σi∗ , σ−i
∗ ∗
) ≥ ui (σi , σ−i ) ∀σi ∈ ∆(Si ).

The best response function bi (.) is defined as

bi (σ−i ) = {σi ∈ ∆(Si ) : ui (σi , σ−i ) ≥ ui (σi0 , σ−i
∗
) ∀σi0 ∈ ∆(Si )}
That is, given σ−i , bi (σ−i ) is the set of all mixed strategies of
player i, each of which is a best response mixed strategy of
player i when the rest of the players are playing the strategy
profile σ−i
Then, a mixed strategy profile (σ1∗ , . . . , σn∗ ) is a Nash
equilibrium iff
σi∗ ∈ bi (σ−i
∗
) ∀i ∈ N

Sanjay Singh MSNE 33

Mixed Strategy Nash Equilibria for BOS Game

Let (σ1∗ , σ2∗ ) be a mixed strategy equilibrium of BOS game, then

u1 (σ1∗ , σ2∗ ) ≥ u1 (σ1 , σ2∗ ) ∀σ1 ∈ ∆(S1 )
u2 (σ1∗ , σ2∗ ) ≥ u2 (σ1∗ , σ2 ) ∀σ2 ∈ ∆(S2 )
Any solution that satisfies above two equations is a mixed
strategy Nash equilibrium
Recall following equations from previous example

u1 (σ1 , σ2 ) = 1 + 3σ1 (A)σ2 (A) − σ1 (A) − σ2 (A)

u2 (σ1 , σ2 ) = 2 + 3σ1 (A)σ2 (A) − 2σ1 (A) − 2σ2 (A)

Writing first two inequalities using above equation yields

3σ1∗ (A)σ2∗ (A) − σ1∗ (A) ≥ 3σ1 (A)σ2∗ (A) − σ1 (A) ∀σ1 ∈ ∆(S1 )
3σ1∗ (A)σ2∗ (A) − 2σ2∗ (A) ≥ 3σ1∗ (A)σ2 (A) − 2σ2 (A) ∀σ2 ∈ ∆(S2 )

Sanjay Singh MSNE 34

 Rewriting last two equations
3σ1∗ (A)σ2∗ (A) − σ1∗ (A) ≥ 3σ1 (A)σ2∗ (A) − σ1 (A) ∀σ1 ∈ ∆(S1 )
3σ1∗ (A)σ2∗ (A) − 2σ2∗ (A) ≥ 3σ1∗ (A)σ2 (A) − 2σ2 (A) ∀σ2 ∈ ∆(S2 )
The above equations are equivalent to:
σ1∗ (A) (3σ2∗ (A) − 1) ≥ σ1 (A) (3σ2∗ (A) − 1) ∀σ1 ∈ ∆(S1 )
σ2∗ (A) (3σ1∗ (A) − 2) ≥ σ2 (A) (3σ1∗ (A) − 2) ∀σ2 ∈ ∆(S2 )
There are three possible cases:
Case 1: 3σ2∗ (A) > 1, this leads to the pure strategy Nash equilibrium (A,A)
Case 2: 3σ2∗ (A) < 1, this leads to the pure strategy Nash equilibrium (B,B)
Case 3: 3σ2∗ (A) = 1, this leads to the mixed strategy Nash equilibrium (σ1∗ , σ2∗ )
2 ∗ 1 1 2
Hence, σ1∗ (A) = ; σ1 (B) = ; σ2∗ (A) = ; σ2∗ (B) =
3 3 3 3

Sanjay Singh MSNE 35

Properties of Mixed Strategies

Mathematical Preliminaries

Definition (Convex set)

A set C is convex if, for any x, y ∈ C and λ ∈ R with 0 ≤ λ ≤ 1,

λx + (1 − λ)y ∈ C

Examples of a convex set (a) and a non-convex set (b)

Sanjay Singh MSNE 36

Definition (Convex function)
A function f : Rn → R is convex if its domain (denoted D(f )) is a convex set, and if,
for all x, y ∈ D(f ) and λ ∈ R with 0 ≤ λ ≤ 1,

f (λx + (1 − λ)y) ≤ λf (x) + (1 − λ)f (y).

Graph of a convex function

Definition (Convex combination)

Given real numbers y1 , y2 , . . . , yn , a convex combination of these numbers is a
weighted sum of the form λ1 y1 + λ2 y2 + . . . + λn yn , where
n
X
0 ≤ λi ≤ 1 for i = 1, 2, . . . , n; λi = 1
i=1

Sanjay Singh MSNE 37

Proposition
Let Γ = hN, (Si ), (ui )i be a strategic form game. Then ui (σi , σ−i ) can
be expressed as the convex combination:
X
ui (σi , σ−i ) = σi (si )ui (si , σ−i )
si ∈Si

where  
X Y
ui (si , σ−i ) =  σj (sj ) ui (si , s−i ).
s−i ∈S−i j6=i

Interpretation
Implication of this result is that the payoff for any player under mixed
strategy can be computed as a convex combination of the payoffs
obtained when the player plays pure strategies with the rest of the
players playing σ−i .

Sanjay Singh MSNE 38

Example

Suppose N = {1, 2}, S1 = {x1 , x2 , x3 , x4 , x5 } and

X
u1 (σ1 , σ2 ) = σ1 (s1 )u1 (s1 , σ2 )
s1 ∈S1
= σ1 (x1 )u1 (x1 , σ2 ) + σ1 (x2 )u1 (x2 , σ2 )
+ σ1 (x3 )u1 (x3 , σ2 ) + σ1 (x4 )u1 (x4 , σ2 )
+ σ1 (x5 )u1 (x5 , σ2 )

Suppose S2 is a finite set

Let u1 (x1 , σ2 ) = 5; u1 (x2 , σ2 ) = u1 (x3 , σ2 ) = 10 and
u1 (x4 , σ2 ) = u1 (x5 , σ2 ) = 20
u1 (σ1 , σ2 ) =
5σ1 (x1 ) + 10σ1 (x2 ) + 10σ1 (x3 ) + 20σ1 (x4 ) + 20σ1 (x5 )

Sanjay Singh MSNE 39

u1 (σ1 , σ2 ) =
5σ1 (x1 ) + 10σ1 (x2 ) + 10σ1 (x3 ) + 20σ1 (x4 ) + 20σ1 (x5 )
The maximum value of convex combination is 20, which is
obtained when
σ1 (x4 ) = 1 or σ1 (x5 ) = 1 or
σ1 (x4 ) + σ1 (x5 ) = 1, and
σ1 (x1 ) + σ1 (x2 ) + σ1 (x3 ) = 0 or σ1 (x1 ) = σ1 (x2 ) = σ1 (x3 ) = 0
Also, max u1 (σ1 , σ2 ) = 20
σ1 ∈∆(S1 )
max u1 (σ1 , σ2 ) = max u1 (s1 , σ2 )
σ1 ∈∆(S1 ) s1 ∈S1

Sanjay Singh MSNE 40

Let ρ ∈ {σ1 ∈ ∆(S1 ) : u1 (σ1 , σ2 ) ≥ u1 (σ10 , σ2 ) ∀σ10 ∈ ∆(S1 )}
⇐⇒ρ(x4 ) + ρ(x5 ) = 1
⇐⇒ρ(x1 ) + ρ(x2 ) + ρ(x3 ) = 0
⇐⇒ρ(x1 ) = ρ(x2 ) = ρ(x3 ) = 0
⇐⇒ρ(y) = 0 ∀y ∈
/ arg max u1 (s1 , σ2 )
s1 ∈S1

Proposition
Given a strategic form game hN, (Si ), (ui )i, then, for any σ ∈ ×i∈N ∆(Si )
and for any player i ∈ N,

max ui (σi , σ−i ) = max ui (si , σ−i )

σi ∈∆(Si ) si ∈Si

Furthermore
ρi ∈ arg max ui (σi , σ−i )
σi ∈∆(Si )

iff
ρi (x) = 0 ∀x ∈
/ arg max ui (si , σ−i )
si ∈Si

Sanjay Singh MSNE 41

Necessary and Sufficient Condition for a Profile to be a Mixed

Strategy Nash Equilibrium

Sanjay Singh MSNE 42

Definition (Support of a Mixed Strategy)
Let σi be any mixed strategy of a player i. The support of σi , denoted
by δ(σi ), is the set of all pure strategies which have non-zero
probabilities under σi , that is,

δ(σi ) = {si ∈ Si : σi (si ) > 0}

Example
Consider a SFG with S1 = {a, b, c, d}, and S2 = {a, b, e, f } with
σ1 (a) = 0.2, σ1 (b) = 0.5, σ1 (c) = 0.3, σ1 (d) = 0, and
σ2 (a) = 0.6, σ2 (b) = 0, σ2 (e) = 0.4, σ2 (f ) = 0. Find the support of
mixed strategies δ(σ1 ) and δ(σ2 ).
Support for σ1 and σ2 is given by δ(σ1 ) = {a, b, c}, and
δ(σ2 ) = {a, e}.

Sanjay Singh MSNE 43

Definition (Support of a Mixed Strategy Profile)

Let σ = (σ1 , . . . , σn ) be a mixed strategy profile with δ(σi ) as the
support of σi for i = 1, . . . , N. Then the support δ(σ) of the profile σ
is the Cartesian product of individual supports, that is
δ(σ1 ) × . . . × δ(σn ).

Example
Consider the computation from previous example and compute δ(σ).
From last example, we know that δ(σ1 ) = {a, b, c}, and
δ(σ2 ) = {a, e}.
The support of the strategy profile is given by

δ(σ) = δ(σ1 ) × σ2 (σ2 )

= {a, b, c} × {a, e}
= {(a, a), (a, e), (b, a), (b, e), (c, a), (c, e)}

Sanjay Singh MSNE 44

 Theorem (Indifference Theorem)
A mixed strategy of player A is a best response to mixed strategies of the
other players if each pure strategy in its support is a best response to the
given mixed strategies of the other players.

Theorem
The mixed strategy profile (σ1∗ , . . . , σn∗ ) is a mixed strategy Nash equilibrium
iff ∀i ∈ N,
∗
1 ui (si , σ−i ) is the same ∀si ∈ δ(σi∗ ) and
∗
2 ui (si , σ−i ) ≥ ui (s0i , σ−i
∗
) ∀si ∈ δ(σi∗ ); ∀s0i ∈
/ δ(σi∗ ).

Henceforth we’ll call to (1) and (2) as condition (1) and condition (2)
The theorem implies that the payoff for player i corresponding to any
pure strategy having non-zero probability is same
Moreover, the payoff is no less than the payoff corresponding to any
pure strategy having zero probability

Sanjay Singh MSNE 45

Implications of Necessary and Sufficient Conditions

Given a mixed strategy Nash equilibrium, each player gets the

same payoff (as in the equilibrium) by playing any pure strategy
having positive probability in her equilibrium mixed strategy
It means player can be indifferent about which of the pure
strategies she will play (having +ve probability in her
equilibrium mixed strategy)
To verify whether or not a mixed strategy profile is a Nash
equilibrium, it is enough to consider the effects of only pure
strategy deviations (with rest of the players playing their
equilibrium strategies)

Sanjay Singh MSNE 46

 Proposition
Given si ∈ Si , let e(si ) denote the degenerate mixed strategy that
assigns probability 1 to si and probability 0 to all other strategies in
Si . The strategy profile (s∗1 , . . . , s∗n ) is a pure strategy Nash
equilibrium of the game hN, (Si ), (ui )i iff the mixed strategy profile
(e(s∗1 ), . . . , e(s∗n )) is a mixed strategy Nash equilibrium of the game
hN, (Si ), (ui )i.

Implication of this theorem is that to identify pure strategy equilibria

of the game hN, (∆(Si )), (ui )i, it is enough to look at the pure strategy
game hN, (Si ), (ui )i.

Sanjay Singh MSNE 47

Mixed Strategy Nash Equilibria of BOS Game

2
1
A B
A 2,1 0,0
B 0,0 1,2
First we verify that (A, A) is a Nash equilibrium
For this profile we denote
σ1∗ (A) = 1; σ1∗ (B) = 0; σ2∗ (A) = 1; σ2∗ (B) = 0
Here, δ(σ1∗ ) = δ(σ2∗ ) = {A}  
X Y
We know that ui (si , σ−i ) =  σj (sj ) ui (si , s−i )
s−i ∈S−i j6=i
X
u1 (A, σ2∗ ) = σ2∗ (s2 )u1 (A, s2 )
s2 ∈{A,B}

= σ2∗ (A)u1 (A, A) + σ2∗ (B)u1 (A, B)

= 1.2 + 0.0 = 2
Similarly, we get u1 (B, σ2∗ ) = 0
Sanjay Singh MSNE 48
Condition (1) of NS theorem is trivially true and condition (2) of
that theorem is true because u1 (A, σ2∗ ) > u1 (B, σ2∗ )
These conditions are satisfied for player 2 also
Hence, (A, A) is a Nash equilibrium
Similarly, (B, B) is also a Nash equilibrium

Sanjay Singh MSNE 49

   
2 1 1 2
Candidate NE: ,, ,
3 3 3 3
2 1 1 2
Which means, σ1∗ (A) = ; σ1∗ (B) = ; σ2∗ (A) = ; σ2∗ (B) =
3 3 3 3
∗ ∗
Here, δ(σ1 ) = δ(σ2 ) = {A, B}
First we examine the situations with player 1, from last slide we
can write  
X Y
ui (si , σ−i ) =  σj (sj ) ui (si , s−i )
s−i ∈S−i j6=i
X
u1 (A, σ2∗ ) = σ2∗ (s2 )u1 (A, s2 )
s2 ∈{A,B}

= σ2∗ (A)u1 (A, A) + σ2∗ (B)u1 (A, B)

1 2 2
= (2) + (0) =
3 3 3
1 2 2
Similarly, u1 (B, σ2∗ ) = (0) + (1) =
3 3 3
Sanjay Singh MSNE 50
 ∗
Con1 : ui (si , σ−i ) is the same ∀si ∈ δ(σi∗ )
2
It is satisfied, because u1 (A, σ2∗ ) = u1 (B, σ2∗ ) =
3
∗ 0 ∗ ∗ 0 ∗
Con2 :ui (si , σ−i ) ≥ ui (si , σ−i ) ∀si ∈ δ(σi ); ∀si ∈
/ δ(σi )
Condition 2 is trivially satisfied because δ(σ1∗ ) = {A, B}, the
entire set, there is nothing to compare
For player 2, from last  slide we  can write
X Y
ui (si , σ−i ) =  σj (sj ) ui (si , s−i )
s−i ∈S−i j6=i
X
u2 (σ1∗ , A) = σ1∗ (s1 )u2 (s1 , A)
s1 ∈{A,B}

= σ1∗ (A)u2 (A, A) + σ1∗ (B)u2 (B, A)

2 1 2
= (1) + (0) =
3 3 3
2 1 2
Similarly, u2 (σ1∗ , B) = (0) + (2) =
3 3 3
Condition (1) satisfied and condition (2) is trivially satisfied
Sanjay Singh MSNE 51

Lets check if there are any other Nash equilibria

The equilibrium (A,A) corresponds to the support {A} × {A},
and equilibrium (B,B) corresponds to the support {B} × {B}
There is no Nash equilibria with support {A} × {A, B}. If player
1 plays A, then player 2 has to play only A, which leads to PSNE
(A,A). There is no way player will play B with non-zero
probability
Similarly, there is no NE with any of the following supports:
{B} × {A, B}
{A, B} × {A}
{A, B} × {B}
{B} × {A}
{A} × {B}

Sanjay Singh MSNE 52

Lets check if there is any other NE with support {A, B} × {A, B}
Let (σ1∗ , σ2∗ ) be defined by

σ1∗ (A) = x σ1∗ (B) = 1 − x

σ2∗ (A) = y σ2∗ (B) = 1 − y

be a NE such that neither x ∈ (0, 1), and

y ∈ (0, 1)(0 < x < 1; 0 < y < 1)
u1 (A, σ2∗ ) = σ2∗ (A)u1 (A, A) + σ2∗ (B)u1 (A, B) = 2y,
u1 (B, σ2∗ ) = 1 − y
X
∗
u2 (σ1 , A) = σ1∗ (s1 )u2 (s1 , A) = x, and
s1 ∈{A,B}
u2 (σ1∗ , B)
= 2(1 − x)
As per condition (1) of the theorem

u1 (A, σ2∗ ) = u1 (B, σ2∗ )

u2 (σ1∗ , A) = u2 (σ1∗ , B)

Sanjay Singh MSNE 53

Substituting values in condition (1) equation yields

1
2y = 1 − y =⇒ y =
3
2
x = 2(1 − x) =⇒ x =
3
This leads to the NE
   
2 1 1 2
σ1∗ = , ; σ2∗ = ,
3 3 3 3

Thus the game does not have any other equilibria

Sanjay Singh MSNE 54

Maxmin and Minmax Values in Mixed Strategies

Given a SFG, the maxmin value of a player is the highest payoff the
player can guarantee himself even in the worst case when other
players are free to play any mixed strategies, formally
Definition (Maxmin Value in Mixed Strategies)
Given a strategic form game, Γ = hN, (Si ), (ui )i, the maxmin value or
security value, in mixed strategies, of a player i(i = 1, . . . , n) is given
by
vi = max min ui (σi , σ−i ).
σi ∈∆(Si ) σ−i ∈×j6=i ∆(Sj )

Any mixed strategy σi ∈ ∆(Si ) that guarantees this payoff to player i

is called a maxmin mixed strategy or security strategy of player i.

Sanjay Singh MSNE 55

A player may have multiple maxmin mixed strategies

The payoff of a player in a MSNE is at least the maxmin value in
mixed strategies of the player, formally

Proposition
Suppose a strategic form game Γ = hN, (Si ), (ui )i has a mixed
strategy Nash equilibrium (σ1∗ , . . . , σn∗ ). Then

ui (σ1∗ , . . . , σn∗ ) ≥ vi ∀i ∈ N

where vi is the maxmin value in mixed strategies of player i

Sanjay Singh MSNE 56

The minmax value in mixed strategies of a player i is the lowest
payoff that the other players will be able to force on player i when
they choose mixed strategies that hurt player i the most, formally
Definition (Minmax Value in Mixed Strategies)
Given a strategic form game, Γ = hN, (Si ), (ui )i, the minmax value,
in mixed strategies, of a player i(i = 1, . . . , n) is given by

vi = min max ui (σi , σ−i ).

σ−i ∈×j6=i ∆(Sj ) σi ∈∆(Si )

Any mixed strategy σ−i that forces this payoff on player i is called a
minmax mixed strategy profile against player i.

Sanjay Singh MSNE 57

The maxmin value in mixed strategies of a player must be less than or

equal to the minmax value in mixed strategies of that player
Proposition
Consider a strategic form game Γ = hN, (Si ), (ui )i. Then

vi ≥ vi ∀i ∈ N

where vi is the maxmin value in mixed strategies of player i and vi is

the minmax value in mixed strategies of player i.

In two player SFG, the maxmin value in mixed strategies is equal

to the minmax value in mixed strategies
However, it need not be true in pure strategies

Sanjay Singh MSNE 58

 The payoff of a player in a MSNE (if one exists) is at least the
minmax value of the player, formally
Proposition
Suppose a strategic form game Γ = hN, (Si ), (ui )i has a mixed
strategy Nash equilibrium (σ1∗ , . . . , σn∗ ). Then

ui (σ1∗ , . . . , σn∗ ) ≥ vi ∀i ∈ N

where vi is the minmax value in mixed strategies of player i

Also, if a MSNE exists then ui (σ1∗ , . . . , σn∗ ) ≥ vi ≥ vi ∀i ∈ N

Sanjay Singh MSNE 59

Domination in Mixed Strategies

Definition
Given two mixed strategies σi , σi0 ∈ ∆(Si ) of player i, we say σi strictly dominates σi0
if
ui (σi , σ−i ) > ui (σi0 , σ−i ) ∀σ−i ∈ ×j6=i ∆(Sj ).
We say σi weakly dominates σi0 if

ui (σi , σ−i ) ≥ ui (σi0 , σ−i ) ∀σ−i ∈ ×j6=i ∆(Sj )

and
ui (σi , σ−i ) > ui (σi0 , σ−i ) ∃σ−i ∈ ×j6=i ∆(Sj ).

We say σi very weakly dominates σi0 if

ui (σi , σ−i ) ≥ ui (σi0 , σ−i ) ∀σ−i ∈ ×j6=i ∆(Sj ).

In the above cases we say the strategy σi0 is strongly/weakly/very weakly dominated
by σi

Sanjay Singh MSNE 60

Definition (Dominant Mixed Strategy Equilibrium)
If the mixed strategy σi∗ strongly(weakly or very weakly) dominates
all other strategies σi0 ∈ ∆(Si ), we say σi∗ is a strongly (weakly or
very weakly dominant) strategy of player i. A strategy profile
(σ1∗ , . . . , σn∗ ) such that σi∗ is a strictly (weakly or very weakly)
dominant strategy for player i, ∀i ∈ N, is called a strictly (weakly or
very weakly) dominant mixed strategy equilibrium.

Any dominant mixed strategy equilibrium is also a mixed

strategy Nash equilibrium
A strictly dominant mixed strategy for any player, if one exists,
is unique

Sanjay Singh MSNE 61

2 2
1 1 2
NC C C 1
C
NC -2,-2 -10,-1 NC -10,-1
C -5,-5
C -1,-10 -5,-5 C -5,-5

Strategy NC is strictly dominated by strategy C for player 2

Player 2 will never play NC
Strategy NC for player 2 can be eliminated, resulting in second
bimatrix
Now the strategy NC of player 1 is dominated by strategy C,
which can also be eliminated leading to a degenerate payoff
matrix with a single entry corresponding to the profile (C,C),
which happens to be a strongly dominant strategy equilibrium

Sanjay Singh MSNE 62

 2
1
X Y Z
A 3,1 0,1 0,0
B 0,1 4,1 0,0
C 1,1 1,1 5,0

u2 (A, X) = u2 (A, Y) > u2 (A, Z)

u2 (B, X) = u2 (B, Y) > u2 (B, Z)
u2 (C, X) = u2 (C, Y) > u2 (C, Z)
Strategy Z is strictly dominated by X and also Y
Player 2 will never play Z
Strategy Z can be eliminated

Sanjay Singh MSNE 63

2
1
X Y
A 3,1 0,1
B 0,1 4,1
C 1,1 1,1

u1 (A, X) > u1 (C, X) > u1 (B, X)

u1 (B, Y) > u1 (C, Y) > u1 (A, Y)
None of the pure strategy of player 1 is dominated by any of its pure
strategies
However, strategy C is strictly dominated by the mixed strategy of
player 1 that assigns equal probability to A and B
C was not dominated by any mixed strategy in original game
A strategy that was not dominated may become dominated when a
strictly dominated strategy is eliminated
Also, a pure strategy may not be dominated by any other pure
strategies but could be dominated by a mixture of those pure strategies
Sanjay Singh MSNE 64
 2
1
X Y
A 3,1 0,1
B 0,1 4,1

No more strategies can be eliminated from this game

Sanjay Singh MSNE 65

Iterated Elimination of Dominated Strategies (IEDS)

Elimination of dominated strategies simplifies the game

Consider a strategic form game, Γ = hN, (Si ), (ui )i
Let k = 1, 2, . . . , K denotes the successive rounds in which
strictly dominated strategies are eliminated
For each player i ∈ N, define the set of strategies Sik as follows
Si1 = Si
Sik+1 ⊆ Sik for k = 1, 2, . . . , K − 1
For k = 1, 2, . . . , K − 1, all strategies si ∈ Sik \Sik+1 are strictly
dominated strategies which are eliminated in the kth round from
the game in which the set of strategies of j ∈ N is Sjk
No strategy in SiK is strictly dominated in the game in which the
set of strategies of each player j ∈ N is SjK
Set of strategy profiles {(s1 , s2 , . . . , sn ) : si ∈ SiK , i = 1, . . . , n} is
said to survive the iterated elimination of strictly dominated
strategies

Sanjay Singh MSNE 66

Example
In last game, S1 = {A, B, C}; S2 = {X, Y, Z}
For this game
S11 = S1 = {A, B, C}; S21 = S2 = {X, Y, Z}
S12 = {A, B, C}; S22 = {X, Y}
S13 = {A, B}; S23 = {X, Y}
The strategy profiles {(A, X), (A, Y), (B, X), (B, Y)} survives the
IEDS

Sanjay Singh MSNE 67

Iterated removal of strongly dominated strategies may

sometimes simplify NE computation
Also, many a times, IEDS may not lead to any simplification as
well
For finite games, IEDS must end in a finite number of rounds
The order of removal of strongly dominant strategies does not
affect the final outcome of the iterated elimination process
However, the order in which weakly or very weakly dominated
strategies are eliminated does influence the final outcome of the
process
Elimination of weakly or very weakly dominated strategies
yields smaller reduced games compared to elimination of
strongly dominated strategies

Sanjay Singh MSNE 68