lemke_howson¶
Author: Daisuke Oyama
Compute mixed Nash equilibria of a 2player normal form game by the LemkeHowson algorithm.

quantecon.game_theory.lemke_howson.
lemke_howson
(g, init_pivot=0, max_iter=1000000, capping=None, full_output=False)[source]¶ Find one mixedaction Nash equilibrium of a 2player normal form game by the LemkeHowson algorithm [R2], implemented with “complementary pivoting” (see, e.g., von Stengel [R3] for details).
Parameters: 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, …, m1 and m, …, m+n1 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. [R1]; 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.
Returns: 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.
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 [R1]:
 For k = init_pivot, init_pivot + 1, …, init_pivot + (m+n2), (modulo m+n), the LemkeHowson 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 LemkeHowson algorithm is executed with init_pivot + (m+n1) (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 largesize games this heuristics outperforms the basic LemkeHowson algorithm with a fixed initial pivot, where [R1] suggests that capping be set to 10.
References
[R1] (1, 2, 3, 4) B. Codenotti, S. De Rossi, and M. Pagan, “An Experimental Analysis of LemkeHowson Algorithm,” arXiv:0811.3247, 2008. [R2] (1, 2) C. E. Lemke and J. T. Howson, “Equilibrium Points of Bimatrix Games,” Journal of the Society for Industrial and Applied Mathematics (1964), 413423. [R3] (1, 2, 3) B. von Stengel, “Equilibrium Computation for TwoPlayer 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 [R3]:
>>> 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