support-enumeration.rst

Support enumeration

The support enumeration algorithm implemented in Nashpy is based on the one described in [Nisan2007].

The algorithm is as follows:

For a nondegenerate 2 player game (A, B) ∈ ℝ^m × n2 the following algorithm returns all nash equilibria:

1. For all 1 ≤ k ≤ min (m, n);
2. For all pairs of support (I, J) with |I| = |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.

Discussion

1. Step 1 is a complete enumeration of all possible strategies that the equilibria could be.
2. Step 2 is based on the definition of a non degenerate game which ensures that equilibria will be on supports of the same size.
3. Step 3 are the linear equations that are to be solved, for a given pair of supports these ensure that neither player has an incentive to move to another strategy on that support.
4. Step 4 is to ensure we have mixed strategies.
5. Step 5 is a final check that there is no better utility outside of the supports.

In Nashpy this is all implemented algebraically using Numpy to solve the linear equations.