gameanalysis.nash module

Module for computing nash equilibria

gameanalysis.nash.fictitious_play(game, mix, *, max_iters=10000, converge_thresh=1e-08)

Run fictitious play on a mixture

In fictitious play, players continually best respond to the empirical distribution of their opponents at each round.

gameanalysis.nash.min_regret_grid_mixture(game, points)

Finds the mixed profile with the confirmed lowest regret

The search is done over a grid with points per dimensions.

Parameters:points (int > 1) – Number of points per dimension to search.

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.min_regret_rand_mixture(game, mixtures)

Finds the mixed profile with the confirmed lowest regret

The search is done over a random sampling of mixtures mixed profiles.

Parameters:mixtures (int > 0) – Number of mixtures to evaluate the regret of.

gameanalysis.nash.mixed_nash(game, *, regret_thresh=0.001, dist_thresh=0.001, 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.

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.pure_nash(game, *, epsilon=0)

Returns an array of all pure nash profiles

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) – The gradient tolerance used for optimization convergence. See scipy.optimize.minimize.

gameanalysis.nash.replicator_dynamics(game, mix, *, max_iters=10000, converge_thresh=1e-08, 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.
• max_iters (int) – Replicator dynamics may never converge and this prevents replicator dynamics from running forever.
• converge_thresh (float) – This will terminate early if successive updates differ with a norm smaller than converge_thresh.
• 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.001, disc=8)

Uses fixed point method to find nash eqm

This is guaranteed to find an equilibrium with regret below regret_thresh, 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 fixed point.

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) – The maximum regret of the returned mixture.
• disc (int) – 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.