support_enumeration

jlgametheory.support_enumeration(g, ntofind=inf, tol=1e-08, **options)

Compute all mixed-action Nash equilibria of an N-player regular normal form game with N >= 3 by support enumeration, with the polynomial homotopy continuation method.

For each support profile, this function solves the system of polynomial equations that makes each player indifferent among the actions in their support, by using HomotopyContinuation.jl, and checks whether each solution is a Nash equilibrium. For a regular game, all the Nash equilibria are returned. For a non-regular game, all pure-action Nash equilibria are returned, as are the mixed-action ones that are nonsingular solutions of their support systems; other mixed-action equilibria may or may not be returned. This function is typically much faster than hc_solve, which solves a single large system of polynomial equations at once.

For 2-player games, use quantecon.game_theory.support_enumeration.

Parameters

gNormalFormGame

NormalFormGame instance with N >= 3 players.

ntofindscalar, optional(default=float(‘inf’))

Maximum number of Nash equilibria to find.

tolscalar(float), optional(default=1e-8)

Tolerance used to check that the probabilities on the supports are positive and that the mixed actions are best responses.

options :

Optional keyword arguments to pass to GameTheory.HCSolver: max_retries (maximum number of times a system is solved again with fresh random numbers when some solution paths fail to be tracked, default 2) and options to pass to HomotopyContinuation.solve, such as seed (integer in [0, 2**32) used as the random seed during the computations; by default, the global random number generator of Julia is used without being reseeded). See the GameTheory.jl documentation for details.

Returns

NEslist(tuple(ndarray(float, ndim=1)))

List containing tuples of Nash equilibrium mixed actions, ordered by increasing total support size.

Examples

Consider the 3-player 2-action game with 9 Nash equilibria in McKelvey and McLennan (1996) “Computation of Equilibria in Finite Games”:

>>> import quantecon.game_theory as gt
>>> import jlgametheory as jgt
>>> from pprint import pprint
>>> import numpy as np
>>> np.set_printoptions(precision=3)  # Reduce the digits printed
>>> g = gt.NormalFormGame((2, 2, 2))
>>> g[0, 0, 0] = 9, 8, 12
>>> g[1, 1, 0] = 9, 8, 2
>>> g[0, 1, 1] = 3, 4, 6
>>> g[1, 0, 1] = 3, 4, 4
>>> NEs = jgt.support_enumeration(g)
>>> len(NEs)
9
>>> pprint(NEs)
[(array([1., 0.]), array([1., 0.]), array([1., 0.])),
 (array([1., 0.]), array([0., 1.]), array([0., 1.])),
 (array([0., 1.]), array([1., 0.]), array([0., 1.])),
 (array([0., 1.]), array([0., 1.]), array([1., 0.])),
 (array([0., 1.]), array([0.333, 0.667]), array([0.333, 0.667])),
 (array([0.25, 0.75]), array([1., 0.]), array([0.25, 0.75])),
 (array([0.5, 0.5]), array([0.5, 0.5]), array([1., 0.])),
 (array([0.25, 0.75]), array([0.5, 0.5]), array([0.333, 0.667])),
 (array([0.5, 0.5]), array([0.333, 0.667]), array([0.25, 0.75]))]
>>> all(g.is_nash(NE) for NE in NEs)
True