lemke_howson

Author: Daisuke Oyama

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

quantecon.game_theory.lemke_howson.get_mixed_actions

From tableaux and bases, extract non-slack basic variables and return a tuple of the corresponding, normalized mixed actions.

Parameters:

tableaux : tuple(ndarray(float, ndim=2))

Tuple of two arrays containing the tableaux, of shape (n, m+n+1) and (m, m+n+1), respectively.

bases : tuple(ndarray(int, ndim=1))

Tuple of two arrays containing the bases, of shape (n,) and (m,), respectively.

Returns:

tuple(ndarray(float, ndim=1))

Tuple of mixed actions as given by the non-slack basic variables in the tableaux.

quantecon.game_theory.lemke_howson.initialize_tableaux

Given a tuple of payoff matrices, initialize the tableau and basis arrays in place.

For each player i, if payoff_matrices[i].min() is non-positive, then stored in the tableau are payoff values incremented by abs(payoff_matrices[i].min()) + 1 (to ensure for the tableau not to have a negative entry or a column identically zero).

Suppose that the players 0 and 1 have m and n actions, respectively.

• tableaux[0] has n rows and m+n+1 columns, where columns 0, ..., m-1 and m, ..., m+n-1 correspond to the non-slack and slack variables, respectively.
• tableaux[1] has m rows and m+n+1 columns, where columns 0, ..., m-1 and m, ..., m+n-1 correspond to the slack and non-slack variables, respectively.
• In each tableaux[i], column m+n contains the values of the basic variables (which are initially 1).
• bases[0] and bases[1] contain basic variable indices, which are initially m, ..., m+n-1 and 0, ..., m-1, respectively.

Parameters:

payoff_matrices : tuple(ndarray(ndim=2))

Tuple of two arrays representing payoff matrices, of shape (m, n) and (n, m), respectively.

tableaux : tuple(ndarray(float, ndim=2))

Tuple of two arrays to be used to store the tableaux, of shape (n, m+n+1) and (m, m+n+1), respectively. Modified in place.

bases : tuple(ndarray(int, ndim=1))

Tuple of two arrays to be used to store the bases, of shape (n,) and (m,), respectively. Modified in place.

Returns:

tableaux : tuple(ndarray(float, ndim=2))

View to tableaux.

bases : tuple(ndarray(int, ndim=1))

View to bases.

Examples

>>> A = np.array([[3, 3], [2, 5], [0, 6]])
>>> B = np.array([[3, 2, 3], [2, 6, 1]])
>>> m, n = A.shape
>>> tableaux = (np.empty((n, m+n+1)), np.empty((m, m+n+1)))
>>> bases = (np.empty(n, dtype=int), np.empty(m, dtype=int))
>>> tableaux, bases = initialize_tableaux((A, B), tableaux, bases)
>>> tableaux[0]
array([[ 3.,  2.,  3.,  1.,  0.,  1.],
       [ 2.,  6.,  1.,  0.,  1.,  1.]])
>>> tableaux[1]
array([[ 1.,  0.,  0.,  4.,  4.,  1.],
       [ 0.,  1.,  0.,  3.,  6.,  1.],
       [ 0.,  0.,  1.,  1.,  7.,  1.]])
>>> bases
(array([3, 4]), array([0, 1, 2]))

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

Find one mixed-action Nash equilibrium of a 2-player normal form game by the Lemke-Howson 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, ..., 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.

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

References

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

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

quantecon.game_theory.lemke_howson.lemke_howson_tbl

Main body of the Lemke-Howson algorithm implementation.

Perform the complementary pivoting. Modify tablaux and bases in place.

Parameters:

tableaux : tuple(ndarray(float, ndim=2))

Tuple of two arrays containing the tableaux, of shape (n, m+n+1) and (m, m+n+1), respectively. Modified in place.

bases : tuple(ndarray(int, ndim=1))

Tuple of two arrays containing the bases, of shape (n,) and (m,), respectively. Modified in place.

init_pivot : scalar(int)

Integer k such that 0 <= k < m+n.

max_iter : scalar(int)

Maximum number of pivoting steps.

Returns:

converged : bool

Whether the pivoting terminated before max_iter was reached.

num_iter : scalar(int)

Number of pivoting steps performed.

Examples

>>> np.set_printoptions(precision=4)  # Reduce the digits printed
>>> A = np.array([[3, 3], [2, 5], [0, 6]])
>>> B = np.array([[3, 2, 3], [2, 6, 1]])
>>> m, n = A.shape
>>> tableaux = (np.empty((n, m+n+1)), np.empty((m, m+n+1)))
>>> bases = (np.empty(n, dtype=int), np.empty(m, dtype=int))
>>> tableaux, bases = initialize_tableaux((A, B), tableaux, bases)
>>> lemke_howson_tbl(tableaux, bases, 1, 10)
(True, 4)
>>> tableaux[0]
array([[ 0.875 ,  0.    ,  1.    ,  0.375 , -0.125 ,  0.25  ],
       [ 0.1875,  1.    ,  0.    , -0.0625,  0.1875,  0.125 ]])
>>> tableaux[1]
array([[ 1.    , -1.6   ,  0.8   ,  0.    ,  0.    ,  0.2   ],
       [ 0.    ,  0.4667, -0.4   ,  1.    ,  0.    ,  0.0667],
       [ 0.    , -0.0667,  0.2   ,  0.    ,  1.    ,  0.1333]])
>>> bases
(array([2, 1]), array([0, 3, 4]))

The outputs indicate that in the Nash equilibrium obtained, player 0’s mixed action plays actions 2 and 1 with positive weights 0.25 and 0.125, while player 1’s mixed action plays actions 0 and 1 (labeled as 3 and 4) with positive weights 0.0667 and 0.1333.

quantecon.game_theory.lemke_howson.lex_min_ratio_test

Perform the lexico-minimum ratio test.

Parameters:

tableau : ndarray(float, ndim=2)

Array containing the tableau.

pivot : scalar(int)

Pivot.

slack_start : scalar(int)

First index for the slack variables.

argmins : ndarray(int, ndim=1)

Empty array used to store the row indices. Its length must be no smaller than the number of the rows of tableau.

Returns:

row_min : scalar(int)

Index of the row with the lexico-minimum ratio.

quantecon.game_theory.lemke_howson.min_ratio_test_no_tie_breaking

Perform the minimum ratio test, without tie breaking, for the candidate rows in argmins[:num_candidates]. Return the number num_argmins of the rows minimizing the ratio and store thier indices in argmins[:num_argmins].

Parameters:

tableau : ndarray(float, ndim=2)

Array containing the tableau.

pivot : scalar(int)

Pivot.

test_col : scalar(int)

Index of the column used in the test.

argmins : ndarray(int, ndim=1)

Array containing the indices of the candidate rows. Modified in place to store the indices of minimizing rows.

num_candidates : scalar(int)

Number of candidate rows in argmins.

Returns:

num_argmins : scalar(int)

Number of minimizing rows.

quantecon.game_theory.lemke_howson.pivoting

Perform a pivoting step. Modify tableau in place.

Parameters:

tableau : ndarray(float, ndim=2)

Array containing the tableau.

pivot : scalar(int)

Pivot.

pivot_row : scalar(int)

Pivot row index.

Returns:

tableau : ndarray(float, ndim=2)

View to tableau.