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:
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 run with two optional arguments:
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 make less checks.tol=0
(10 ** -16
is the default), when considering the underlying linear systemtol
is considered to be a lower bound for difference between two real numbers. Usingtol=0
ensures a strict run 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]