gameanalysis.nash module

Module for computing nash equilibria

gameanalysis.nash.fictitious_play(game, mix)

Run fictitious play on a mixture

In fictitious play, players continually best respond to the empirical distribution of their opponents at each round. This tends to have very slow convergence.

Parameters

• game (RsGame) – The game to compute an equilibrium of.

• mix (array_like) – The initial mixture to respond to.

gameanalysis.nash.min_regret_profile(game)

Finds the profile with the confirmed lowest regret

An error will be raised if there are no profiles with a defined regret.

gameanalysis.nash.mixed_equilibria(game, style='best', *, regret_thresh=0.01, dist_thresh=0.1, processes=None)

Compute mixed equilibria

Parameters

• game (RsGame) – Game to compute equilibria of.

• style (str, optional) –

  The style of equilibria funding to run. Available styles are:

  fast - run minimal algorithms and return nothing on failure more - run minimal and if nothing run other reasonable algorithms best - run extra and if nothing run exponential with timeout one - run extra and if nothing run exponential <any>* - if nothing found, return minimum regret

• regret_thresh (float, optional) – Minimum regret for a mixture to count as an equilibrium.

• dist_thresh (float, optional) – Minimum role norm for equilibria to be considered distinct. [0, 1]

• processes (int, optional) – Number of processes to compute equilibria with. If None, all available processes will be used.

gameanalysis.nash.mixed_nash(game, *, regret_thresh=0.001, dist_thresh=0.1, grid_points=2, random_restarts=0, processes=0, min_reg=False, at_least_one=False, **methods)

Finds role-symmetric mixed Nash equilibria

This is the intended front end for nash equilibria finding, wrapping the individual methods in a convenient front end that also support parallel execution. Scipy optimize, and hence nash finding with the optimize method is NOT thread safe. This can be mitigated by running nash finding in a separate process (by setting processes > 0) if the game is pickleable.

This is the old style nash finding and provides more options. For new methods, mixture_equilibria is the preferred interface.

Parameters

• regret_thresh (float, optional) – The threshold to consider an equilibrium found.

• dist_thresh (float, optional) – The threshold for considering equilibria distinct.

• grid_points (int > 1, optional) – The number of grid points to use for mixture seeds. two implies just pure mixtures, more will be denser, but scales exponentially with the dimension.

• random_restarts (int, optional) – The number of random initializations.

• processes (int or None, optional) – Number of processes to use when finding Nash equilibria. If 0 (default) run nash finding in the current process. This will work with any game but is not thread safe for the optimize method. If greater than zero or none, the game must be pickleable and nash finding will be run in processes processes. Passing None will use the number of current processors.

• min_reg (bool, optional) – If True, and no equilibria are found with the methods specified, return the point with the lowest empirical regret. This is ignored if at_least_one is True

• at_least_one (bool, optional) – If True, always return an equilibrium. This will use the fixed point method with increasingly smaller tolerances until an equilibrium with small regret is found. This may take an exceedingly long time to converge, so use with caution.

• **methods ({'replicator', 'optimize', 'scarf', 'fictitious'}={options}) – All methods to use can be specified as key word arguments to additional options for that method, e.g. mixed_nash(game, replicator={‘max_iters’:100}). To use the default options for a method, simply pass a falsey value i.e. {}, None, False. If no methods are specified, this will use both replicator dynamics and regret optimization as they tend to be reasonably fast and find different equilibria. Scarfs algorithm is almost never recommended to be passed here, as it will be called if at_least_one is True and only after failing with a faster method and only called once.

Returns

eqm – A two dimensional array with mixtures that have regret below regret_thresh and have norm difference of at least dist_thresh.

Return type

ndarray

gameanalysis.nash.multiplicative_weights_bandit(game, mix, *, epsilon=0.5, max_iters=100000, converge_thresh=1e-07, converge_disc=0.1, min_prob=0.001, **kwargs)

Compute an equilibrium using the bandit multiplicative weights

This version of multiplicative weights takes the shortest amount of time per iteration but is less likely to converge to an equilibrium.

Parameters

• game (RsGame) – The game to compute an equilibrium of.

• mix (ndarray) – The initial mixture for searching.

• epsilon (float, optional) – The rate of update for new payoffs. Convergence results hold when epsilon in [0, 3/5].

• min_prob (float, optional) – The minimum probability a mixture is given when sampling from a profile. This is necessary to prevent the bandit from getting stuck in pure mixtures, and to bound the potential payoffs, as payoffs are divided by the probability to get unbiased estimates. However, larger settings of this will bias the overall result. (0, 1)

gameanalysis.nash.multiplicative_weights_dist(game, mix, *, epsilon=0.5, max_iters=10000, converge_thresh=1e-08, **kwargs)

Compute an equilibrium using the distribution multiplicative weights

This version of multiplicative weights takes the longest per iteration, but also has less variance and likely converges better.

Parameters

• game (RsGame) – The game to compute an equilibrium of.

• mix (ndarray) – The initial mixture for searching.

• epsilon (float, optional) – The rate of update for new payoffs. Convergence results hold when epsilon in [0, 3/5].

gameanalysis.nash.multiplicative_weights_stoch(game, mix, *, epsilon=0.5, max_iters=100000, converge_thresh=1e-07, converge_disc=0.2, **kwargs)

Compute an equilibrium using the stochastic multiplicative weights

This version of multiplicative weights takes a medium amount of time per iteration and converges better than the bandit version.

Parameters

• game (RsGame) – The game to compute an equilibrium of.

• mix (ndarray) – The initial mixture for searching.

• epsilon (float, optional) – The rate of update for new payoffs. Convergence results hold when epsilon in [0, 3/5].

gameanalysis.nash.pure_equilibria(game, *, epsilon=0)

Returns an array of all pure nash profiles

gameanalysis.nash.regret_matching(game, profile, *, slack=0.1)

Regret matching

Run regret matching. This selects new strategies to play proportionally to the gain they receive from deviating from the current profile.

Parameters

• game (Game) – The game to run replicator dynamics on. Game must support deviation_payoffs.

• profile (array_like) – The initial profile to start with.

• slack (float, optional) – The amount to make sure agents will always play their last played strategy. (0, 1)

gameanalysis.nash.regret_minimize(game, mix, *, gtol=1e-08)

A pickleable object to find Nash equilibria

This method uses constrained convex optimization to to attempt to solve a proxy for the nonconvex regret minimization. Since this may converge to a local optimum, it may return a mixture that is not an approximate equilibrium.

Parameters

• game (Game) – The game to run replicator dynamics on. Game must support deviation_payoffs.

• mix (mixture) – The mixture to initialize replicator dynamics with.

• gtol (float, optional) – The gradient tolerance used for optimization convergence. See scipy.optimize.minimize.

gameanalysis.nash.replicator_dynamics(game, mix, *, slack=0.001)

Replicator Dynamics

Run replicator dynamics on a game starting at mix. Replicator dynamics may not converge, and so the resulting mixture may not actually represent a nash equilibrium.

Parameters

• game (Game) – The game to run replicator dynamics on. Game must support deviation_payoffs.

• mix (mixture) – The mixture to initialize replicator dynamics with.

• slack (float) – For repliactor dynamics to operate, it must know the minimum and maximum payoffs for a role such that deviations always have positive probability. This is the proportional slack that given relative to the minimum and maximum payoffs. This has an effect on convergence, but the actual effect isn’t really know.

gameanalysis.nash.scarfs_algorithm(game, mix, *, regret_thresh=0.01, disc=8)

Uses fixed point method to find nash eqm

This is guaranteed to find an equilibrium with regret below regret_thresh if given enough time. However, it’s guaranteed convergence is assured by potentially exponential running time, and therefore is not recommended unless you’re willing to wait. The underlying algorithm is solving for an approximate Nash fixed point with greater and great approximation until its regret is below the threshold.

Parameters

• game (Game) – The game to run replicator dynamics on. Game must support deviation_payoffs.

• mix (mixture) – The mixture to initialize replicator dynamics with.

• regret_thresh (float, optional) – The maximum regret of the returned mixture.

• disc (int, optional) – The initial discretization of the mixture. A lower initial discretization means fewer possible starting points for search in the mixture space, but is likely to converge faster as the search at higher discretization will be seeded with an approximate equilibrium from a lower discretization. For example, with disc=2 there are only game.num_strats - game.num_roles + 1 possible starting points.