Author: Daisuke Oyama
Compute mixed Nash equilibria of a 2-player normal form game by the Lemke-Howson algorithm.
lemke_howson(g, init_pivot=0, max_iter=1000000, capping=None, full_output=False)¶
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. [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.
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 [R1]:
- 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 [R1] suggests that capping be set to 10.
[R1] (1, 2, 3, 4) B. Codenotti, S. De Rossi, and M. Pagan, “An Experimental Analysis of Lemke-Howson 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), 413-423. [R3] (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 [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