Degenerate games

A two player game is called nondegenerate if no mixed strategy of support size \(k\) has more than \(k\) pure best responses.

For example, the zero sum game defined by the following matrix is degenerate:

\[\begin{split}A = \begin{pmatrix} 0 & -1 & 1\\ -1 & 0 & 1\\ -1 & 1 & 0 \end{pmatrix}\end{split}\]

The third column has two pure best responses.

When dealing with degenerate games unexpected results can occur:

>>> import nashpy as nash
>>> import numpy as np
>>> A = np.array([[0, -1, 1], [-1, 0, 1], [-1, 0, 1]])
>>> game = nash.Game(A)

Here is the output when using Support enumeration:

>>> for eq in game.support_enumeration():
...     print(np.round(eq[0], 2), np.round(eq[1], 2))
[ 0.5  0.5  0. ] [ 0.5  0.5  0. ]
[ 0.5  0.   0.5] [ 0.5  0.5  0. ]

Here is the output when using Vertex enumeration:

>>> for eq in game.vertex_enumeration():
...     print(np.round(eq[0], 2), np.round(eq[1], 2))
[ 0.5  0.   0.5] [ 0.5  0.5 -0. ]
[ 0.5  0.5 -0. ] [ 0.5  0.5 -0. ]

Here is the output when using the The Lemke Howson Algorithm:

>>> for eq in game.lemke_howson_enumeration():
...     print(np.round(eq[0], 2), np.round(eq[1], 2))
[ 0.33...  0.33...  0.33...] [ nan]

We see that the lemke-howson algorithm fails but also that the Support enumeration and Vertex enumeration fail to find some equilibria: there is in fact a range of strategies the row player can play against [ 0.5 0.5 0] that is still a best response.

The Support enumeration algorithm can be executed with two optional arguments that allow for control of it’s execution:

  • non_degenerate=True (False is the default) will only consider supports of equal size. If you know your game is non degenerate this will make support enumeration execute less checks.
  • tol=0 (10 ** -16 is the default), when considering the underlying linear system tol is considered to be a lower bound for difference between two real numbers. Using tol=0 ensures a very strict execution of the algorithm.

Here is an example:

>>> A = np.array([[4, 9, 9], [9, 1, 6], [9, 2, 3]])
>>> B = np.array([[2, 2, 5], [7, 4, 4], [1, 6, 4]])
>>> game = nash.Game(A, B)
>>> for eq in game.support_enumeration():
...     print(np.round(eq[0], 2), np.round(eq[1], 2))
[ 1.  0.  0.] [ 0.  0.  1.]
[ 0.  1.  0.] [ 1.  0.  0.]
[ 0.5  0.5  0. ] [ 0.38  0.    0.62]
[ 0.2  0.5  0.3] [ 0.57  0.32  0.11]
>>> for eq in game.support_enumeration(non_degenerate=True):
...     print(np.round(eq[0], 2), np.round(eq[1], 2))
[ 1.  0.  0.] [ 0.  0.  1.]
[ 0.  1.  0.] [ 1.  0.  0.]
[ 0.2  0.5  0.3] [ 0.57  0.32  0.11]
>>> for eq in game.support_enumeration(non_degenerate=False, tol=0):
...     print(np.round(eq[0], 2), np.round(eq[1], 2))
[ 1.  0.  0.] [ 0.  0.  1.]
[ 0.  1.  0.] [ 1.  0.  0.]
[ 0.2  0.5  0.3] [ 0.57  0.32  0.11]