vertex_enumeration

Compute all mixed Nash equilibria of a 2-player normal form game by vertex 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.vertex_enumeration.vertex_enumeration(g, qhull_options=None)[source]

Compute mixed-action Nash equilibria of a 2-player normal form game by enumeration and matching of vertices of the best response polytopes. For a non-degenerate game input, these are all the Nash equilibria.

Internally, scipy.spatial.ConvexHull is used to compute vertex enumeration of the best response polytopes, or equivalently, facet enumeration of their polar polytopes. Then, for each vertex of the polytope for player 0, vertices of the polytope for player 1 are searched to find a completely labeled pair.

Parameters:
g : NormalFormGame

NormalFormGame instance with 2 players.

qhull_options : str, optional(default=None)

Options to pass to scipy.spatial.ConvexHull. See the Qhull manual for details.

Returns:
list(tuple(ndarray(float, ndim=1)))

List containing tuples of Nash equilibrium mixed actions.

quantecon.game_theory.vertex_enumeration.vertex_enumeration_gen(g, qhull_options=None)[source]

Generator version of vertex_enumeration.

Parameters:
g : NormalFormGame

NormalFormGame instance with 2 players.

qhull_options : str, optional(default=None)

Options to pass to scipy.spatial.ConvexHull. See the Qhull manual for details.

Yields:
tuple(ndarray(float, ndim=1))

Tuple of Nash equilibrium mixed actions.