howson_lcp

Compute a Nash Equilibrium of a Polymatrix Game.

Examples

Find a Nash Equilibrium of a Matching Pennies Game. (This NE is unique so this works reliably.)

>>> matrices = {
...     (0, 1): [[1., -1.], [-1., 1.]],
...     (1, 0): [[-1., 1.], [1., -1.]]
... }
>>> polymg = PolymatrixGame(matrices)
>>> result = polym_lcp_solver(polymg, full_output=True)
>>> print(result[0])
(array([0.5, 0.5]), array([0.5, 0.5]))
>>> print(result[1])
        NE: (array([0.5, 0.5]), array([0.5, 0.5]))
 converged: True
      init: {0: 0, 1: 0}
  max_iter: -1
  num_iter: 4

quantecon.game_theory.howson_lcp.polym_lcp_solver(polymg: PolymatrixGame, starting_player_actions: Sequence[int] | None = None, max_iter: int = -1, full_output: bool = False) → tuple[numpy.ndarray[typing.Any, numpy.dtype[+_ScalarType_co]]] | ~quantecon.game_theory.utilities.NashResult

Finds a Nash Equilbrium of a Polymatrix Game.

Uses Howson’s algorithm which utilises linear complementarity [1].

Parameters:

polymgPolymatrixGame

Polymatrix game to solve.

starting_player_actionsSequence[int], optional

Pure actions for each player at which the algorithm begins. Defaults to each player playing their first action.

max_iterint, optional

Maximum number of iterations of the complementary pivoting before giving up. Howson proves that with enough iterations, it will reach a Nash Equilibrium. Defaults to never giving up.

full_outputbool, optional

When True, adds information about the run to the output actions and puts them in a NashResult. Defaults to False.

Returns:

tuple(ndarray(float, ndim=1)) or NashResult

The mixed actions at termination, a Nash Equilibrium if not stopped early by reaching max_iter. If full_output, then the number of iterations, whether it has converged, and the initial conditions of the algorithm are included in the returned NashResult alongside the actions.

References

[1]

Howson, Joseph T. “Equilibria of Polymatrix Games.” Management Science 18, no. 5 (1972): 312–18. http://www.jstor.org/stable/2634798.