ipa_solve

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

Compute one mixed-action approximate Nash equilibrium of an N-player normal form game with the iterated polymatrix approximation (IPA) algorithm.

This function calls the IPA 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 IPA homotopy, of length sum(g.nums_actions), where the entries are interpreted in player-concatenated order. Different rays may lead to different 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 computed Nash equilibrium is returned. If True, the return value is (NE, res), where res is a NashResult object.

options :

Optional keyword arguments to pass to GameTracer.ipa_solve: zh_init (initial condition for z-hat, default all ones), alpha (step size fraction, default 0.02), fuzz (stopping tolerance, default 1e-6), max_iter (maximum number of iterations, i.e., polymatrix approximations, default 100000), and max_pivots (maximum number of pivoting steps per Lemke-Howson solve, default 1000000). See the GameTracer.jl documentation for details.

Returns

NEtuple(ndarray(float, ndim=1))

Tuple of computed (approximate) Nash equilibrium mixed actions. If the routine did not converge (see res.converged), the last iterate is returned.

resNashResult

Object containing the information about the result, returned only when full_output is True, with the following attributes: NE (same as NE above), converged (whether an equilibrium was found within max_iter iterations without the routine giving up), ret_code (return code from the IPA routine, 1 on success and 0 otherwise), 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
>>> np.set_printoptions(precision=3)  # Reduce the digits printed
>>> rng = np.random.default_rng(0)
>>> 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
>>> NE = jgt.ipa_solve(g, rng=rng)
>>> NE
(array([1., 0.]), array([1., 0.]), array([1., 0.]))
>>> g.is_nash(NE)
True

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

>>> NE = jgt.ipa_solve(g, rng=rng)
>>> NE
(array([0.25, 0.75]), array([0.5, 0.5]), array([0.333, 0.667]))
>>> g.is_nash(NE, tol=1e-5)  # Relax tolerance
True

References