support-enumeration.rst

Support enumeration

Motivating example: Coordination Game

In the Coordination game <motivating-example-coordination-game> in how many situations do neither player have an incentive to independently change their strategy?

Neither player having a reason to change their strategy implies that both strategies are Best responses<definition-of-best-response> to each other.

To identify such pairs of strategies, we will use the best_response_condition by considering all possible non zero valued elements σ_r and σ_c.

Recall that for the Coordination game the matrices A and B are given by:

$$\begin{aligned} A = \begin{pmatrix} 3 & 1\\\ 0 & 2 \end{pmatrix} \end{aligned}$$

$$\begin{aligned} B = \begin{pmatrix} 2 & 1\\\ 0 & 3 \end{pmatrix} \end{aligned}$$

If we consider strategies that only play a single action there are two options for each strategy:

σ_r ∈ {(1, 0), (0, 1)}

and:

σ_c ∈ {(1, 0), (0, 1)}

We will inspect all four combinations:

• σ_r = (1, 0) and σ_c = (1, 0) which corresponds to both players playing their first action which gives: u_r(σ_r, σ_c) = 3 and u_c(σ_r, σ_c) = 2. If the row player where to modify their strategy (while the column player stayed unchanged) to play the second action their utility would decrease. Likewise, if the column player were to modify their strategy their utility would also decrease.
• σ_r = (1, 0) and σ_c = (0, 1) which corresponds to the row player playing their first action and the column player playing their second action which gives: u_r(σ_r, σ_c) = 1 and u_c(σ_r, σ_c) = 1. In this case, if either player were to move their utility would increase.
• σ_r = (0, 1) and σ_c = (1, 0) which corresponds to the row player playing their second action and the column player playing their first action which gives: u_r(σ_r, σ_c) = 0 and u_c(σ_r, σ_c) = 0. In this case, if either player were to move their utility would increase.
• σ_r = (0, 1) and σ_c = (0, 1) which corresponds to both players playing their second action which gives: u_r(σ_r, σ_c) = 2 and u_c(σ_r, σ_c) = 3. If the row player where to modify their strategy (while the column player stayed unchanged) to play the second action their utility would decrease. Likewise, if the column player were to modify their strategy their utility would also decrease.

If we now consider strategies that play both actions there is a single general form:

σ_r = (x, 1 − x) for 0 < x < 1

σ_c = (y, 1 − y) for 0 < y < 1

We can apply the best_response_condition here.

If σ_r is a best response to σ_c then:

(Aσ_cT)_i = max_{k ∈ {1, 2}}(Aσ_c^T)_k for all i ∈ {1, 2}

which gives:

$$\begin{aligned} 3y + 1(1-y) &= \text{max}_{k \in\{1, 2\}} (A\sigma_c^T)_k\\\ 0y + 2(1-y) &= \text{max}_{k \in\{1, 2\}} (A\sigma_c^T)_k \end{aligned}$$

which in turn corresponds to:

$$\begin{aligned} 3y + 1(1 - y) & = 2(1-y)\\\ y & = 1 / 4 \end{aligned}$$

Thus σ_r = (x, 1 − x) with 0 < x < 1 is a best response to σ_c if and only if σ_c = (1/4, 3/4).

We will now apply the best_response_condition again but to the column player:

If σ_c is a best response to σ_r then:

(σ_rB)_j = max_{k ∈ {1, 2}}(σ_rB)_k for all j ∈ {1, 2}

which gives:

$$\begin{aligned} 2x + 0(1-x) &= \text{max}_{k \in\{1, 2\}} (\sigma_rB)_k\\\ 1x + 3(1-x) &= \text{max}_{k \in\{1, 2\}} (\sigma_rB)_k \end{aligned}$$

which in turn corresponds to:

$$\begin{aligned} 2x & = x + 3(1-x)\\\ x & = 3 / 4 \end{aligned}$$

Thus σ_c = (y, 1 − y) with 0 < y < 1 is a best response to σ_r if and only if σ_r = (3/4, 1/4).

There are 3 pairs of strategies that are best responses to each other:

• σ_r = (1, 0) and σ_c = (1, 0).
• σ_r = (0, 1) and σ_c = (0, 1).
• σ_r = (3/4, 1/4) and σ_c = (1/4, 3/4).

The support enumeration algorithm

The approach used in motivating-example-coordination-game-nash-equilibria is in fact an application of a formalised algorithm called support enumeration.

The algorithm is as follows:

For a non Degenerate <degenerate-games-discussion> 2 player game (A, B) ∈ ℝ^m × n2 the following algorithm returns all pairs of best responses:

1. For all 1 ≤ k₁ ≤ m and 1 ≤ k₂ ≤ n;
2. For all pairs of support <definition-of-support-of-a-strategy> (I, J) with |I| = k₁ and |J| = k₂.

3. Solve the following equations (this ensures we have best responses):

   
   ∑_i ∈ Iσ_riB_ij = v for all j ∈ J
   
   ∑_j ∈ JA_ijσ_cj = u for all i ∈ I
   

4. Solve
   • $\sum_{i=1}^{m}{\sigma_{r}}_i=1$ and σ_ri ≥ 0 for all i
   • $\sum_{j=1}^{n}{\sigma_{c}}_i=1$ and σ_cj ≥ 0 for all j
5. Check the best response condition.

Repeat steps 3,4 and 5 for all potential support pairs.

Question

Use support enumeration to find all Nash equilibria for the game given by $A=\begin{pmatrix} 1 & 1 & -1 \\ 2 & -1 & 0 \end{pmatrix}$ and $B=\begin{pmatrix} 1/2 & -1 & -1/2 \\-1 & 3 & 2 \end{pmatrix}$.

Answer

1. It is immediate to note that there are no pairs of pure best responses.
2. All possible support pairs are:
   • I = {1, 2} and J = {1, 2}
   • I = {1, 2} and J = {1, 3}
   • I = {1, 2} and J = {2, 3}
3. Let us solve the corresponding linear equations:

   • I = {1, 2} and J = {1, 2}:

     
     1/2σ_r1 − σ_r2 =  − σ_r1 + 3σ_r2
     

     
     σ_r1 = 8/3σ_r2
     

     
     σ_c1 + σ_c2 = 2σ_c1 − σ_c2
     

     
     σ_c1 = 2σ_c2
     

   • I = {1, 2} and J = {1, 3}:

     
     1/2σ_r1 − σ_r2 =  − 1/2σ_r1 + 2σ_r2
     

     
     σ_r1 = 3σ_r2
     

     
     σ_c1 − σ_c3 = 2σ_c1 + 0σ_c3
     

     
     σ_c1 =  − σ_c3
     

   • I = {1, 2} and J = {2, 3}:

     
      − σ_r1 + 3σ_r2 =  − 1/2σ_r1 + 2σ_r2
     

     
     σ_r1 = 2σ_r2
     

     
     σ_c2 − σ_c3 =  − σ_c2 + 0σ_c3
     

     
     2σ_c2 = σ_c3
     

4. We check which supports give valid strategies:

   • I = {1, 2} and J = {1, 2}:

     
     σ_r = (8/11, 3/11)
     

     
     σ_c = (2/3, 1/3, 0)
     

   • I = {1, 2} and J = {1, 3}:

     
     σ_r = (3/4, 1/4)
     

     
     σ_c = (k, 0,  − k)
     

     which is not a valid strategy.

   • I = {1, 2} and J = {2, 3}:

     
     σ_r = (2/3, 1/3)
     

     
     σ_c = (0, 1/3, 2/3)
     

5. Let us verify the best response condition:

   • I = {1, 2} and J = {1, 2}:

     
     σ_c = (2/3, 1/3, 0)
     

     
     $$\begin{aligned} A\sigma_c^T= \begin{pmatrix} 1\\ 1 \end{pmatrix} \end{aligned}$$
     

     Thus σ_r is a best response to σ_c

     
     σ_r = (8/11, 3/11)
     

     
     σ_rB = (1/11, 1/11, 2/11)
     

     Thus σ_c is not a best response to σ_r (because there is a better response outside of the support of σ_c).

   • I = {1, 2} and J = {2, 3}:

     
     σ_c = (0, 1/3, 2/3)
     

     
     $$\begin{aligned} A\sigma_c^T= \begin{pmatrix} -1/3\\ -1/3 \end{pmatrix} \end{aligned}$$
     

     Thus σ_r is a best response to σ_c

     
     σ_r = (2/3, 1/3)
     

     
     σ_rB = (0, 1/3, 1/3)
     

     Thus σ_c is a best response to σ_r.

   Thus the (unique) Nash equilibrium for this game is:

   
   ((2/3, 1/3), (0, 1/3, 2/3))
   

Using Nashpy

See how-to-use-support-enumeration for guidance of how to use Nashpy to use support enumeration.