gnm_solve

jlgametheory.gnm_solve(g, *, ray=None, rng=None, full_output=False, **options)[source]

Compute mixed-action Nash equilibria of an N-player normal form game with the global Newton method (GNM) algorithm.

This function calls the GNM routine of Govindan and Wilson [1] from the C++ library GameTracer through its Julia wrapper GameTracer.jl.

Parameters

gNormalFormGame

NormalFormGame instance with N >= 2 players.

rayarray_like(float, ndim=1), optional(default=None)

Perturbation ray for the GNM homotopy, of length sum(g.nums_actions), where the entries are interpreted in player-concatenated order. Different rays may lead to different sets of equilibria. If None, a ray is randomly generated by rng.

rngint or np.random.Generator, optional(default=None)

Random seed or random number generator used to generate the default ray (passed to np.random.default_rng). Irrelevant if ray is given.

full_outputbool, optional(default=False)

If False, only the list of computed Nash equilibria is returned. If True, the return value is (NEs, res), where res is a NashResult object.

options :

Optional keyword arguments to pass to GameTracer.gnm_solve: steps (number of steps within a support cell, default 100), fuzz (numerical zero threshold, default 1e-12), lnmfreq (frequency of local Newton method corrections, default 3), lnmmax (maximum iterations within the local Newton method, default 10), lambdamin (minimum value of the continuation parameter, default -10.0), wobble (whether to use “wobbles” of the perturbation vector, default False), threshold (error threshold to trigger a wobble, default 1e-2), and max_iter (maximum number of iterations, i.e., support cells traversed, default 5000; if reached, the equilibria found so far are returned). See the GameTracer.jl documentation for details.

Returns

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

List containing tuples of computed Nash equilibrium mixed actions. If max_iter is reached, the list contains the equilibria found up to that point.

resNashResult

Object containing the information about the result, returned only when full_output is True, with the following attributes: NEs (same as NEs above), ret_code (return code from the GNM routine, the number of equilibria found), num_iter (number of iterations performed), max_iter (maximum number of iterations), and ray (perturbation ray used).

Examples

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

>>> import numpy as np
>>> import quantecon.game_theory as gt
>>> import jlgametheory as jgt
>>> from pprint import pprint
>>> np.set_printoptions(precision=3)  # Reduce the digits printed
>>> rng = np.random.default_rng(28)
>>> 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.gnm_solve(g, rng=rng)
>>> pprint(NEs)
[(array([0., 1.]), array([1., 0.]), array([0., 1.])),
 (array([0.25, 0.75]), array([1., 0.]), array([0.25, 0.75])),
 (array([1., 0.]), array([1., 0.]), array([1., 0.]))]

Calls with different rays generally yield different sets of equilibria (here, rng generates a different ray on each call as its state advances):

>>> NEs = jgt.gnm_solve(g, rng=rng)
>>> pprint(NEs)
[(array([1., 0.]), array([0., 1.]), array([0., 1.])),
 (array([0.5, 0.5]), array([0.333, 0.667]), array([0.25, 0.75])),
 (array([0., 1.]), array([1., 0.]), array([0., 1.])),
 (array([0.25, 0.75]), array([1., 0.]), array([0.25, 0.75])),
 (array([0.25, 0.75]), array([0.5, 0.5]), array([0.333, 0.667])),
 (array([0., 1.]), array([0.333, 0.667]), array([0.333, 0.667])),
 (array([0., 1.]), array([0., 1.]), array([1., 0.])),
 (array([0.5, 0.5]), array([0.5, 0.5]), array([1., 0.])),
 (array([1., 0.]), array([1., 0.]), array([1., 0.]))]
>>> all(g.is_nash(NE, tol=1e-5) for NE in NEs)
True

References