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