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]], ...] | tuple[tuple[numpy.ndarray[typing.Any, numpy.dtype[+_ScalarType_co]], ...], quantecon.game_theory.utilities.NashResult][source]

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:

NEtuple(ndarray(float, ndim=1)): Tuple of computed Nash equilibrium mixed actions. A Nash Equilibrium if not stopped early by reaching max_iter.
resNashResult: Object containing information about the computation: the number of iterations, whether it has converged, and the initial conditions of the algorithm. Returned only when full_output is True. See NashResult for details.

References

[1]

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