Application of the support enumeration algorithm
Consider the following game of two players (row and column player):
5,4 1,3
3,2 3,3
• S1 = S2 = {1,2}
• Variables: σ1(1),σ1(2),σ2(1),σ2(2),w1,w2
Now enumerate all possible pairs of supports and solve for each of them separately.
We shall use strict inequalities in the constraint 4 (see slide 96 of the lecture) to
ensure that the strategies have exactly the prescribed supports. (The version from
the slide allows smaller supports but is still correct and complete.)
The constraint system from the slide 96 instantiates into the following form:
The constraints 1 and 2 are
σ2(1)·5+σ2(2)·1 {≤,=} w1 (k = 1)
σ2(1)·3+σ2(2)·3 {≤,=} w1 (k = 2)
σ1(1)·4+σ1(2)·2 {≤,=} w2 (ℓ = 1)
σ1(1)·3+σ1(2)·3 {≤,=} w2 (ℓ = 2)
Here the concrete relations (≤ or =) depend on the support (see below for the
individual cases). The constraints in 3 do not change with supports:
σ1(1)+σ1(2) = 1 σ2(1)+σ2(2) = 1
The constraints 4 and 5 depend on the supports and will be presented individually.
Now let us enumerate the support sets.
1. supp1 = {1},supp2 = {1}: The constraints:
σ2(1)·5+σ2(2)·1 = w1 (k = 1)
σ2(1)·3+σ2(2)·3 ≤ w1 (k = 2)
σ1(1)·4+σ1(2)·2 = w2 (ℓ = 1)
σ1(1)·3+σ1(2)·3 ≤ w2 (ℓ = 2)
and
σ1(1) > 0 σ1(2) = 0 σ2(1) > 0 σ2(2) = 0
Thus, by the constraint 3, σ1(1) = σ2(1) = 1 and the above constraints reduce
to
5 = w1
3 ≤ w1
4 = w2
3 ≤ w2
Giving w1 = 5 and w2 = 4 and σ1(1) = 1 and σ2(1) = 1.
1
2. supp1 = {1},supp2 = {2}: The constraints:
σ2(1)·5+σ2(2)·1 = w1 (k = 1)
σ2(1)·3+σ2(2)·3 ≤ w1 (k = 2)
σ1(1)·4+σ1(2)·2 ≤ w2 (ℓ = 1)
σ1(1)·3+σ1(2)·3 = w2 (ℓ = 2)
and
σ1(1) > 0 σ1(2) = 0 σ2(1) = 0 σ2(2) > 0
Thus σ1(1) = σ2(2) = 1 and the constraints reduce to
1 = w1
3 ≤ w1
4 ≤ w2
3 = w2
which apparently does not have any solution. No Nash equilibrium exists
with this support.
3. supp1 = {2},supp2 = {1}: The constraints:
σ2(1)·5+σ2(2)·1 ≤ w1 (k = 1)
σ2(1)·3+σ2(2)·3 = w1 (k = 2)
σ1(1)·4+σ1(2)·2 = w2 (ℓ = 1)
σ1(1)·3+σ1(2)·3 ≤ w2 (ℓ = 2)
and
σ1(1) = 0 σ1(2) > 0 σ2(1) > 0 σ2(2) = 0
Reduce to
5 ≤ w1
3 = w1
2 = w2
3 ≤ w2
Which does not have a solution.
4. supp1 = {2},supp2 = {2}: The constraints:
σ2(1)·5+σ2(2)·1 ≤ w1 (k = 1)
σ2(1)·3+σ2(2)·3 = w1 (k = 2)
σ1(1)·4+σ1(2)·2 ≤ w2 (ℓ = 1)
σ1(1)·3+σ1(2)·3 = w2 (ℓ = 2)
2
and
σ1(1) = 0 σ1(2) > 0 σ2(1) = 0 σ2(2) > 0
Reduce to
1 ≤ w1
3 = w1
2 ≤ w2
3 = w2
Giving w1 = w2 = 3 and σ1(2) = 1 and σ2(2) = 1.
5. supp1 = {1},supp2 = {1,2} The constraints:
σ2(1)·5+σ2(2)·1 = w1 (k = 1)
σ2(1)·3+σ2(2)·3 ≤ w1 (k = 2)
σ1(1)·4+σ1(2)·2 = w2 (ℓ = 1)
σ1(1)·3+σ1(2)·3 = w2 (ℓ = 2)
and
σ1(1) > 0 σ1(2) = 0 σ2(1) > 0 σ2(2) > 0
Reduce to
σ2(1)·5+σ2(2)·1 = w1 (k = 1)
σ2(1)·3+σ2(2)·3 ≤ w1 (k = 2)
σ1(1)·4 = w2 (ℓ = 1)
σ1(1)·3 = w2 (ℓ = 2)
which does not have a solution.
6. supp1 = {2},supp2 = {1,2} The constraints:
σ2(1)·5+σ2(2)·1 ≤ w1 (k = 1)
σ2(1)·3+σ2(2)·3 = w1 (k = 2)
σ1(1)·4+σ1(2)·2 = w2 (ℓ = 1)
σ1(1)·3+σ1(2)·3 = w2 (ℓ = 2)
and
σ1(1) = 0 σ1(2) > 0 σ2(1) > 0 σ2(2) > 0
Reduce to
σ2(1)·5+σ2(2)·1 ≤ w1 (k = 1)
σ2(1)·3+σ2(2)·3 = w1 (k = 2)
σ1(2)·2 = w2 (ℓ = 1)
σ1(2)·3 = w2 (ℓ = 2)
Which does not have a solution.
3
7. supp1 = {1,2},supp2 = {1} The constraints:
σ2(1)·5+σ2(2)·1 = w1 (k = 1)
σ2(1)·3+σ2(2)·3 = w1 (k = 2)
σ1(1)·4+σ1(2)·2 = w2 (ℓ = 1)
σ1(1)·3+σ1(2)·3 ≤ w2 (ℓ = 2)
and
σ1(1) > 0 σ1(2) > 0 σ2(1) > 0 σ2(2) = 0
Reduce to
σ2(1)·5 = w1 (k = 1)
σ2(1)·3 = w1 (k = 2)
σ1(1)·4+σ1(2)·2 = w2 (ℓ = 1)
σ1(1)·3+σ1(2)·3 ≤ w2 (ℓ = 2)
Which does not have a solution.
8. supp1 = {1,2},supp2 = {2} The constraints:
σ2(1)·5+σ2(2)·1 = w1 (k = 1)
σ2(1)·3+σ2(2)·3 = w1 (k = 2)
σ1(1)·4+σ1(2)·2 = w2 (ℓ = 1)
σ1(1)·3+σ1(2)·3 ≤ w2 (ℓ = 2)
and
σ1(1) > 0 σ1(2) > 0 σ2(1) = 0 σ2(2) > 0
Reduce to
σ2(2)·1 = w1 (k = 1)
σ2(2)·3 = w1 (k = 2)
σ1(1)·4+σ1(2)·2 = w2 (ℓ = 1)
σ1(1)·3+σ1(2)·3 ≤ w2 (ℓ = 2)
Which does not have a solution.
9. supp1 = {1,2},supp2 = {1,2}: The constraints:
σ2(1)·5+σ2(2)·1 = w1 (k = 1)
σ2(1)·3+σ2(2)·3 = w1 (k = 2)
σ1(1)·4+σ1(2)·2 = w2 (ℓ = 1)
σ1(1)·3+σ1(2)·3 = w2 (ℓ = 2)
4
Reduce (using the contraint 3) to
σ2(1)·5+(1−σ2(1))·1 = σ2(1)·3+(1−σ2(1))·3
σ1(1)·4+(1−σ1(1))·2 = σ1(1)·3+(1−σ1(1))·3
Which is solved by σ2(1) = 1/2 and σ1(1) = 1/2.
5