Author: Daisuke Oyama

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 [R3], implemented with “complementary pivoting” (see, e.g., von Stengel [R4] for details).


g : NormalFormGame

NormalFormGame instance with 2 players.

init_pivot : scalar(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_iter : scalar(int), optional(default=10**6)

Maximum number of pivoting steps.

capping : scalar(int), optional(default=None)

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

full_output : bool, 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.


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

Tuple of computed Nash equilibrium mixed actions.

res : NashResult

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


  • 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 [R2]:

    • 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 [R2] suggests that capping be set to 10.


[R2](1, 2, 3, 4) B. Codenotti, S. De Rossi, and M. Pagan, “An Experimental Analysis of Lemke-Howson Algorithm,” arXiv:0811.3247, 2008.
[R3](1, 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.
[R4](1, 2, 3) 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.


Consider the following game from von Stengel [R4]:

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

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
>>> res.num_iter  # Number of pivoting steps performed