support_enumeration

Compute all mixed Nash equilibria of a 2-player (non-degenerate) normal form game by support enumeration.

References

B. von Stengel, “Equilibrium Computation for Two-Player Games in Strategic and Extensive Form,” Chapter 3, N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani eds., Algorithmic Game Theory, 2007.

quantecon.game_theory.support_enumeration.support_enumeration(g)[source]

Compute mixed-action Nash equilibria with equal support size for a 2-player normal form game by support enumeration. For a non-degenerate game input, these are all the Nash equilibria.

The algorithm checks all the equal-size support pairs; if the players have the same number n of actions, there are 2n choose n minus 1 such pairs. This should thus be used only for small games.

Parameters:

gNormalFormGame: NormalFormGame instance with 2 players.

Returns:

list(tuple(ndarray(float, ndim=1))): List containing tuples of Nash equilibrium mixed actions.

Examples

>>> from pprint import pprint
>>> np.set_printoptions(precision=4)  # Reduce the digits printed
>>> bimatrix = [[(3, 3), (3, 2)],
...             [(2, 2), (5, 6)],
...             [(0, 3), (6, 1)]]
>>> g = NormalFormGame(bimatrix)
>>> NEs = support_enumeration(g)
>>> pprint(NEs)
[(array([1., 0., 0.]), array([1., 0.])),
 (array([0.8, 0.2, 0. ]), array([0.6667, 0.3333])),
 (array([0.    , 0.3333, 0.6667]), array([0.3333, 0.6667]))]

quantecon.game_theory.support_enumeration.support_enumeration_gen(g)[source]

Generator version of support_enumeration.

Parameters:

gNormalFormGame: NormalFormGame instance with 2 players.

Yields:

tuple(ndarray(float, ndim=1)): Tuple of Nash equilibrium mixed actions.

Examples

>>> np.set_printoptions(precision=4)  # Reduce the digits printed
>>> bimatrix = [[(3, 3), (3, 2)],
...             [(2, 2), (5, 6)],
...             [(0, 3), (6, 1)]]
>>> g = NormalFormGame(bimatrix)
>>> gen = support_enumeration_gen(g)
>>> for NE in gen:
...     print(NE)
...
(array([1., 0., 0.]), array([1., 0.]))
(array([0.8, 0.2, 0. ]), array([0.6667, 0.3333]))
(array([0.    , 0.3333, 0.6667]), array([0.3333, 0.6667]))