Support enumeration¶
The support enumeration algorithm implemented in Nashpy
is based on the
one described in [Nisan2007].
The algorithm is as follows:
For a degenerate 2 player game \((A, B)\in{\mathbb{R}^{m\times n}}^2\) the following algorithm returns all nash equilibria:
For all \(1\leq k_1\leq m\) and \(1\leq k_2\leq n\);
For all pairs of support \((I, J)\) with \(|I|=k_1\) and \(|J|=k_2\).
Solve the following equations (this ensures we have best responses):
\[ \begin{align}\begin{aligned} \sum_{i\in I}{\sigma_{r}}_iB_{ij}=v\text{ for all }j\in J\\\sum_{j\in J}A_{ij}{\sigma_{c}}_j=u\text{ for all }i\in I\end{aligned}\end{align} \]Solve
\(\sum_{i=1}^{m}{\sigma_{r}}_i=1\) and \({\sigma_{r}}_i\geq 0\) for all \(i\)
\(\sum_{j=1}^{n}{\sigma_{c}}_i=1\) and \({\sigma_{c}}_j\geq 0\) for all \(j\)
Check the best response condition.
Repeat steps 3,4 and 5 for all potential support pairs.
Discussion¶
Step 1 is a complete enumeration of all possible strategies that the equilibria could be.
Step 2 can be modified to only consider degenerate games ensuring that only supports of equal size are considered \(|I|=|J|\). This is described further in Degenerate games.
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.
Step 4 is to ensure we have mixed strategies.
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.