lemke_howson

Compute mixed Nash equilibria of a 2-player normal form game by the Lemke-Howson algorithm.

quantecon.game_theory.lemke_howson.lemke_howson(g, init_pivot=0, max_iter=1000000, capping=None, full_output=False)[source]

Find one mixed-action Nash equilibrium of a 2-player normal form game by the Lemke-Howson algorithm [2], implemented with “complementary pivoting” (see, e.g., von Stengel [3] for details).

Parameters:
gNormalFormGame

NormalFormGame instance with 2 players.

init_pivotscalar(int), optional(default=0)

Initial pivot, an integer k such that 0 <= k < m+n, where integers 0, …, m-1 and m, …, m+n-1 correspond to the actions of players 0 and 1, respectively.

max_iterscalar(int), optional(default=10**6)

Maximum number of pivoting steps.

cappingscalar(int), optional(default=None)

If supplied, the routine is executed with the heuristics proposed by Codenotti et al. [1]; see Notes below for details.

full_outputbool, optional(default=False)

If False, only the computed Nash equilibrium is returned. If True, the return value is (NE, res), where NE is the Nash equilibrium and res is a NashResult object.

Returns:
NEtuple(ndarray(float, ndim=1))

Tuple of computed Nash equilibrium mixed actions.

resNashResult

Object containing information about the computation. Returned only when full_output is True. See NashResult for details.

Notes

  • This routine is implemented with floating point arithmetic and thus is subject to numerical instability.

  • If capping is set to a positive integer, the routine is executed with the heuristics proposed by [1]:

    • For k = init_pivot, init_pivot + 1, …, init_pivot + (m+n-2), (modulo m+n), the Lemke-Howson algorithm is executed with k as the initial pivot and capping as the maximum number of pivoting steps. If the algorithm converges during this loop, then the Nash equilibrium found is returned.

    • Otherwise, the Lemke-Howson algorithm is executed with init_pivot + (m+n-1) (modulo m+n) as the initial pivot, with a limit max_iter on the total number of pivoting steps.

    Accoding to the simulation results for uniformly random games, for medium- to large-size games this heuristics outperforms the basic Lemke-Howson algorithm with a fixed initial pivot, where [1] suggests that capping be set to 10.

References

[1] (1,2,3)

B. Codenotti, S. De Rossi, and M. Pagan, “An Experimental Analysis of Lemke-Howson Algorithm,” arXiv:0811.3247, 2008.

[2]

C. E. Lemke and J. T. Howson, “Equilibrium Points of Bimatrix Games,” Journal of the Society for Industrial and Applied Mathematics (1964), 413-423.

[3] (1,2)

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.

Examples

Consider the following game from von Stengel [3]:

>>> 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)

Obtain a Nash equilibrium of this game by lemke_howson with player 0’s action 1 (out of the three actions 0, 1, and 2) as the initial pivot:

>>> lemke_howson(g, init_pivot=1)
(array([ 0.    ,  0.3333,  0.6667]), array([ 0.3333,  0.6667]))
>>> g.is_nash(_)
True

Additional information is returned if full_output is set True:

>>> NE, res = lemke_howson(g, init_pivot=1, full_output=True)
>>> res.converged  # Whether the routine has converged
True
>>> res.num_iter  # Number of pivoting steps performed
4