mclennan_tourky

Author: Daisuke Oyama

Compute mixed Nash equilibria of an N-player normal form game by applying the imitation game algorithm by McLennan and Tourky to the best response correspondence.

quantecon.game_theory.mclennan_tourky.mclennan_tourky(g, init=None, epsilon=0.001, max_iter=200, full_output=False)[source]

Find one mixed-action epsilon-Nash equilibrium of an N-player normal form game by the fixed point computation algorithm by McLennan and Tourky [R4].

Parameters:

g : NormalFormGame

NormalFormGame instance.

init : array_like(int or array_like(float, ndim=1)), optional

Initial action profile, an array of N objects, where each object must be an iteger (pure action) or an array of floats (mixed action). If None, default to an array of zeros (the zero-th action for each player).

epsilon : scalar(float), optional(default=1e-3)

Value of epsilon-optimality.

max_iter : scalar(int), optional(default=100)

Maximum number of iterations.

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.

References

[R4](1, 2) A. McLennan and R. Tourky, “From Imitation Games to Kakutani,” 2006.

Examples

Consider the following version of 3-player “anti-coordination” game, where action 0 is a safe action which yields payoff 1, while action 1 yields payoff \(v\) if no other player plays 1 and payoff 0 otherwise:

>>> N = 3
>>> v = 2
>>> payoff_array = np.empty((2,)*n)
>>> payoff_array[0, :] = 1
>>> payoff_array[1, :] = 0
>>> payoff_array[1].flat[0] = v
>>> g = NormalFormGame((Player(payoff_array),)*N)
>>> print(g)
3-player NormalFormGame with payoff profile array:
[[[[ 1.,  1.,  1.],   [ 1.,  1.,  2.]],
  [[ 1.,  2.,  1.],   [ 1.,  0.,  0.]]],
 [[[ 2.,  1.,  1.],   [ 0.,  1.,  0.]],
  [[ 0.,  0.,  1.],   [ 0.,  0.,  0.]]]]

This game has a unique symmetric Nash equilibrium, where the equilibrium action is given by \((p^*, 1-p^*)\) with \(p^* = 1/v^{1/(N-1)}\):

>>> p_star = 1/(v**(1/(N-1)))
>>> [p_star, 1 - p_star]
[0.7071067811865475, 0.29289321881345254]

Obtain an approximate Nash equilibrium of this game by mclennan_tourky:

>>> epsilon = 1e-5  # Value of epsilon-optimality
>>> NE = mclennan_tourky(g, epsilon=epsilon)
>>> print(NE[0], NE[1], NE[2], sep='\n')
[ 0.70710754  0.29289246]
[ 0.70710754  0.29289246]
[ 0.70710754  0.29289246]
>>> g.is_nash(NE, tol=epsilon)
True

Additional information is returned if full_output is set True:

>>> NE, res = mclennan_tourky(g, epsilon=epsilon, full_output=True)
>>> res.converged
True
>>> res.num_iter
18