Submodules¶

gameanalysis.AGGFN module¶

class gameanalysis.AGGFN.Sym_AGG_FNA(num_players, num_strategies, action_weights, function_inputs, node_functions)[source]¶

Bases: gameanalysis.rsgame.BaseGame

Action Graph Game with Function Nodes.

Represented games are symmetric. Action node utilities have additive structure. Function nodes are contribution-independent. Graph is bipartite so that function nodes have in-edges only from action nodes and vise versa.

deviation_payoffs(mix, assume_complete=True, jacobian=False)[source]¶

static from_json(j_)[source]¶

Build a game from the info stored in a dictionary in the json format.

get_payoffs(profile)[source]¶

Returns an array of profile payoffs.

is_complete()[source]¶

max_payoffs()[source]¶

Returns an upper bound on the payoffs.

min_payoffs()[source]¶

Returns a lower bound on the payoffs.

to_json(strategy_names=None, function_names=None)[source]¶

Creates a json format of the game for storage

to_rsgame()[source]¶

Builds an rsgame.Game object that represents the same game.

gameanalysis.AGGgen module¶

gameanalysis.AGGgen.CGST_coef_dist(d)¶

gameanalysis.AGGgen.LEG_other_coef_dist(d)¶

gameanalysis.AGGgen.LEG_self_coef_dist(d)¶

gameanalysis.AGGgen.congestion_game(num_players, num_facilities, num_required, degree=2, coef_dist=<function <lambda>>)[source]¶

gameanalysis.AGGgen.default_coef_dist(d)¶

gameanalysis.AGGgen.local_effect_game(num_players, num_strategies, edge_prob=0.2, self_poly_deg=1, other_poly_deg=2, self_poly_coef=<function <lambda>>, other_poly_coef=<function <lambda>>)[source]¶

gameanalysis.AGGgen.random_AGGFNA(num_players, num_strategies, num_funcs, weight_distr=functools.partial(<MagicMock name='mock.random.normal' id='140422159146736'>, 0, 1), func_distr=<function random_polynomial>, act_edge_distr=<function random_bipartite_graph>, func_edge_distr=<function random_bipartite_graph>)[source]¶

gameanalysis.AGGgen.random_bipartite_graph(source_set_size, dest_set_size, p=0.2, min_inputs=1, min_outputs=1)[source]¶

gameanalysis.AGGgen.random_polynomial(degree=functools.partial(<MagicMock name='mock.random.choice' id='140422159061456'>, [1, 2, 3, 4, ]p=[0.4, 0.3, 0.2, 0.1]), coef_distr=<function <lambda>>)[source]¶

gameanalysis.AGGgen.randomize_weights(adjacency_matrix, weight_distr)[source]¶

gameanalysis.bootstrap module¶

Module for using bootstrap in analysis

gameanalysis.bootstrap.game_function(game, function, num_resamples, num_returned, percentiles=None, processes=None)[source]¶

Bootstrap the value of a function over a sample game

Parameters:	game (SampleGame) – The sample game to bootstrap the function value over. function (f(Game) -> float or f(Game) -> [float]) – The function of the game to compute. It must be pickleable unless processes is 1, and it must return either a float or an iterable of floats. If an iterable of floats, this bootstrap all indices of the return value independently. num_resamples (int) – The number of bootstrap samples. Higher will take longer but also give better accuracy. num_returned (int) – The number of float values your function returns. percentiles (int or [int]) – The percentiles to compute on the resulting data in [0, 100]. Standard percentiles are 95, or [2.5, 97.5]. By default, return all samples. processes (int (optional)) – The number of processes to use for computation. By default this is the number of cores.
Returns:	bootstrap_percentiles – An ndarray of the percentiles from bootstrapping. The shape will depend on the number of percentiles and the number of values returned from your function.
Return type:	ndarray

gameanalysis.bootstrap.mean(data, num_resamples, percentiles=None)[source]¶

Compute bootstrap bounds for the mean of a data set

One particular use is compute bootstrap bounds on social welfare of a mixture if all of the samples are iid draws of welfare from the mixture.

Parameters:	data ([float] or ndarray) – The data to get bootstrap estimates around the mean of. num_resamples (int) – The number of bootstrap samples. Higher will take longer but also give better accuracy. percentiles (int or [int]) – The percentiles to compute on the resulting data in [0, 100]. Standard percentiles are 95, or [2.5, 97.5].

gameanalysis.bootstrap.mixture_regret(game, mixtures, num_resamples, percentiles=None, processes=None)[source]¶

Compute percentile bounds on mixture regret

Parameters:	game (SampleGame) – The sample game to bootstrap the function value over. mixtures (ndararay) – The profiles to compute mixture regret bounds for. num_resamples (int) – The number of bootstrap samples. Higher will take longer but also give better accuracy. percentiles (int or [int]) – The percentiles to compute on the resulting data in [0, 100]. Standard percentiles are 95, or [2.5, 97.5]. By default, return all samples. processes (int (optional)) – The number of processes to use for computation. By default this is the number of cores.
Returns:	regret_percentiles – An ndarray of the percentiles for bootstrap regret for each profile.
Return type:	ndarray

gameanalysis.bootstrap.mixture_welfare(game, mixtures, num_resamples, percentiles=None, processes=None)[source]¶

Compute percentile bounds on mixture welfare

Parameters:	game (SampleGame) – The sample game to bootstrap the function value over. mixtures (ndarray) – The profiles to compute mixture welfare bounds for. num_resamples (int) – The number of bootstrap samples. Higher will take longer but also give better accuracy. percentiles (int or [int]) – The percentiles to compute on the resulting data in [0, 100]. Standard percentiles are 95, or [2.5, 97.5]. By default, return all samples. processes (int (optional)) – The number of processes to use for computation. By default this is the number of cores.
Returns:	bootstrap_percentiles – An ndarray of the percentiles for bootstrap welfare for each profile.
Return type:	ndarray

gameanalysis.bootstrap.profile_function(game, function, profiles, num_resamples, percentiles=None, processes=None)[source]¶

Compute a function over profiles

Parameters:	game (SampleGame) – The sample game to bootstrap the function value over. function (Game, profile -> float) – The function of the game profile pair to compute. It must be pickleable, and it must return a float (e.g. regret.mixture_regret). profiles (ndarray) – The profiles to compute bootstrap bounds over for function. num_resamples (int) – The number of bootstrap samples. Higher will take longer but also give better accuracy. percentiles (int or [int]) – The percentiles to compute on the resulting data in [0, 100]. Standard percentiles are 95, or [2.5, 97.5]. By default, return all samples. processes (int (optional)) – The number of processes to use for computation. By default this is the number of cores.
Returns:	bootstrap_percentiles – An ndarray of the percentiles from bootstrapping for each profile. The shape will depend on the number of percentiles and the number of profiles.
Return type:	ndarray

gameanalysis.bootstrap.sample_regret(game, mixture_payoffs, deviation_payoffs, num_resamples, percentiles=None)[source]¶

Compute bootstrap bounds on the mixture regret with samples

Parameters:	game (BaseGame) – The game the samples are from. mixture_payoffs (ndarray) – A sample of payoffs by role. The distribution must come from the desired mixture payoffs (deviation) – The payoff to the deviator when everyone else is played according to the mixture. The strategy payoffs can either by a mapping of strategy names, or just a list of payoffs. num_resamples (int) – The number of bootstrap samples. Higher will take longer but also give better accuracy. percentiles (int or [int]) – The percentiles to compute on the resulting data in [0, 100]. Standard percentiles are 95, or [2.5, 97.5].
Returns:	Note
Return type:	The lengths of every list must be the same

gameanalysis.collect module¶

class gameanalysis.collect.DynamicArray(item_shape, dtype=None, initial_room=8, grow_fraction=2)[source]¶

Bases: object

A object with a backed array that also allows adding data

append(array)[source]¶

Append an array

compact()[source]¶

Trim underlying storage to hold only valid data

data¶

A view of all of the data

ensure_capacity(new_capacity)[source]¶

Make sure the array has a least new_capacity

pop(num=None)[source]¶

Pop one or several arrays

gameanalysis.congestion module¶

class gameanalysis.congestion.CongestionGame(num_players, num_required, facility_coefs)[source]¶

Bases: gameanalysis.rsgame.BaseGame

Congestion Game

Parameters:	num_players (int) – The number of players in the symmetric congestion game. num_required (int) – The number of required facilities in a strategy. facility_coefs (ndarray, (num_facilities, 3)) – The polynomial coefficients for the congestion function. The first column is constant, then linear, then quadratic.

deviation_payoffs(mix, assume_complete=True, jacobian=False)[source]¶

gen_serializer()[source]¶

get_payoffs(profiles)[source]¶

is_complete()[source]¶

Congestion games are always complete

max_payoffs()[source]¶

Computes the max payoff per role

For computational efficiency, this computes an upper bound on max payoff by relaxing integer assignment to facilities. In practice it seems very close.

min_payoffs()[source]¶

to_game()[source]¶

to_json(serial=None)[source]¶

Convert game to json

Parameters:	serial (GameSerializer) – If unspecified, one will be generated using gen_serializer()

to_str(serial=None)[source]¶

Convert game to a human string

Parameters:	serial (GameSerializer) – If unspecified, one will be generated on the fly.

gameanalysis.congestion.gen_congestion_game(num_players, num_facilities, num_required, return_serial=False)[source]¶

Generates a random congestion game with num_players players and nCr(f, r) strategies

Congestion games are symmetric, so all players belong to one role. Each strategy is a subset of size #required among the size #facilities set of available facilities. Payoffs for each strategy are summed over facilities. Each facility’s payoff consists of three components:

-constant ~ U[0, num_facilities] -linear congestion cost ~ U[-num_required, 0] -quadratic congestion cost ~ U[-1, 0]

gameanalysis.congestion.read_congestion_game(json_)[source]¶

gameanalysis.dominance module¶

Module for computing dominated strategies

gameanalysis.dominance.iterated_elimination(game, criterion, conditional=True)[source]¶

Return a subgame mask resulting from iterated elimination of strategies

Parameters:	game (Game) – The game to run iterated elimination on criterion (str, {'weakdom', 'strictdom', 'neverbr'}) – The criterion to use to eliminated strategies. conditional (bool) – Whether to use conditional criteria. In general, conditional set to true will assume that unobserved payoffs are large. See the other methods for a more detailed explanation

gameanalysis.dominance.never_best_response(game, conditional=True)[source]¶

Return a mask of the strategies that are never a best response

If conditional, then missing data is treated as a best response. The counted best response will be the largest deviation that has data.

gameanalysis.dominance.strictly_dominated(game, conditional=True)[source]¶

Return a mask of the strategies that are strictly dominated

If conditional, then missing data will be treated as dominating.

gameanalysis.dominance.weakly_dominated(game, conditional=True)[source]¶

Return a mask of the strategies that are weakly dominated

If conditional, then missing data will be treated as dominating.

gameanalysis.gamegen module¶

gameanalysis.gamegen.add_noise(game, min_samples, max_samples=None, noise=<function default_distribution>)[source]¶

Generate sample game by adding noise to game payoffs

Parameters:

game (Game) – A Game or SampleGame (only current payoffs are used) min_samples (int) – The minimum number of observations to create per profile max_samples (int) – The maximum number of observations to create per profile. If None, it’s the same as min_samples. noise (shape -> ndarray) – A noise generating function. The function should take a single shape parameter, and return a number of samples equal to shape. In order to preserve mixed equilibria, noise should also be zero mean (aka unbiased)

gameanalysis.gamegen.add_noise_width(game, num_samples, max_width, noise=<function width_gaussian>)[source]¶

Create sample game where each profile has different noise level

Parameters:

game (Game) – The game to generate samples from. These samples are additive noise to standard payoff values. num_samples (int) – The number of samples to generate for each profile. max_width (float) – A parameter describing how much noise to generate. Larger max_width generates more noise. noise ((float, int, int) -> ndarray (optional)) – The noise generating function to use. The function must take three parameters: the max_width, the number of profiles, and the number of samples, and return an ndarray of the additive noise for each profile (shape: (num_profiles, num_samples)). The max_width should be used to generate sufficient statistics for each profile, and then each sample per profile should come from a distribution derived from those. For this to be accurate, this distribution should have expectation 0. Several default versions are specified in gamegen, and they’re all prefixed with width_. By default, this uses width_gaussian.

gameanalysis.gamegen.add_profiles(game, prob_or_count=1.0, distribution=<function default_distribution>)[source]¶

Add profiles to a base game

Parameters:	distribution ((shape) -> ndarray, optional) – Distribution function to draw profiles from. prob_or_count (float or int, optional) – If a float, the probability to add a profile from the full game. If an int, the number of profiles to add. independent (bool, optional) – If true then each profile has prob probability of being added, else num_all_profiles * prob profiles will be kept.

gameanalysis.gamegen.congestion_game(num_players, num_facilities, num_required, return_serial=False)[source]¶

Generates a random congestion game with num_players players and nCr(f, r) strategies

Congestion games are symmetric, so all players belong to one role. Each strategy is a subset of size #required among the size #facilities set of available facilities. Payoffs for each strategy are summed over facilities. Each facility’s payoff consists of three components:

-constant ~ U[0, num_facilities] -linear congestion cost ~ U[-num_required, 0] -quadratic congestion cost ~ U[-1, 0]

gameanalysis.gamegen.covariant_game(num_strategies, mean_dist=<function <lambda>>, var_dist=<function <lambda>>, covar_dist=<function default_distribution>)[source]¶

Generate a covariant game

Covariant games are asymmetric games where payoff values for each profile drawn according to multivariate normal.

The multivariate normal for each profile has a constant mean drawn from mean_dist, constant variance drawn from`var_dist`, and constant covariance drawn from covar_dist.

Parameters:

mean_dist ((shape) -> ndarray (shape)) – Distribution from which mean payoff for each profile is drawn. (default: lambda: 0) var_dist ((shape) -> ndarray (shape)) – Distribution from which payoff variance for each profile is drawn. (default: lambda: 1) covar_dist ((shape) -> ndarray (shape)) – Distribution from which the value of the off-diagonal covariance matrix entries for each profile is drawn. (default: uniform [-1, 1])

gameanalysis.gamegen.default_distribution(shape=None)[source]¶

gameanalysis.gamegen.drop_profiles(game, prob, independent=True)[source]¶

Drop profiles from a game

If independent then each profile has prob of being removed, if not independent, then num_profiles * prob profiles will be kept.

gameanalysis.gamegen.drop_samples(game, prob)[source]¶

Drop samples from a sample game

Samples are dropped independently with probability prob.

gameanalysis.gamegen.game_serializer(game)[source]¶

gameanalysis.gamegen.independent_game(num_strategies, distribution=<function default_distribution>)[source]¶

Generate a random independent (asymmetric) game

All payoffs are generated independently from distribution.

Parameters:	num_players (int > 0) – The number of players. num_strategies (int or [int], len == num_players) – The number of strategies for each player. If an int, then every player has the same number of strategies. distribution ((shape) -> ndarray (shape)) – The distribution to sample payoffs from. Must take a single shape argument and return an ndarray of iid values with that shape.

gameanalysis.gamegen.local_effect_game(num_players, num_strategies)[source]¶

Generates random congestion games with num_players (N) players and num_strategies (S) strategies.

Local effect games are symmetric, so all players belong to one role. Each strategy corresponds to a node in the G(N, 2/S) (directed edros-renyi random graph with edge probability of 2/S) local effect graph. Payoffs for each strategy consist of constant terms for each strategy, and interaction terms for the number of players choosing that strategy and each neighboring strategy.

The one-strategy terms are drawn as follows: -constant ~ U[-(N+S), N+S] -linear ~ U[-N, 0]

The neighbor strategy terms are drawn as follows: -linear ~ U[-S, S] -quadratic ~ U[-1, 1]

gameanalysis.gamegen.normalize(game, new_min=0, new_max=1)[source]¶

Return a normalized game

gameanalysis.gamegen.polymatrix_game(num_players, num_strategies, matrix_game=<function independent_game>, players_per_matrix=2)[source]¶

Creates a polymatrix game using the specified k-player matrix game function.

Each player’s payoff in each profile is a sum over independent games played against each set of opponents. Each k-tuple of players plays an instance of the specified random k-player matrix game.

Parameters:	num_players (int) – The number of players. num_strategies (int) – The number of strategies per player. matrix_game ((players_per_matrix, num_strategies) -> Game, optional) – A function to generate games between sub groups of players. players_per_matrix (int, optional) – The number of players that interact simultaneously.

Notes

The actual roles and strategies of matrix game are ignored.

gameanalysis.gamegen.prisoners_dilemma(distribution=<function default_distribution>)[source]¶

Return a random prisoners dilemma game

gameanalysis.gamegen.rock_paper_scissors(win=1, loss=-1, return_serial=False)[source]¶

Return an instance of rock paper scissors

gameanalysis.gamegen.role_symmetric_game(num_players, num_strategies, distribution=<function default_distribution>)[source]¶

Generate a random role symmetric game

Parameters:	num_roles (int > 0) – The number of roles in the game. num_players (int or [int], len == num_roles) – The number of players, same for each role if a scalar, or a list, one for each role. num_strategies (int or [int], len == num_roles) – The number of strategies, same for each role if a scalar, or a list, one for each role. distribution ((shape) -> ndarray (shape)) – Payoff distribution.

gameanalysis.gamegen.sym_2p2s_game(a=0, b=1, c=2, d=3, distribution=<function default_distribution>)[source]¶

Create a symmetric 2-player 2-strategy game of the specified form.

Four payoff values get drawn from U(min_val, max_val), and then are assigned to profiles in order from smallest to largest according to the order parameters as follows:

	s0	s1
s0	a,a	b,c
s1	c,b	d,d

So a=2,b=0,c=3,d=1 gives a prisoners’ dilemma; a=0,b=3,c=1,d=2 gives a game of chicken.

distribution must accept a size parameter a la numpy distributions.

gameanalysis.gamegen.sym_2p2s_known_eq(eq_prob)[source]¶

Generate a symmetric 2-player 2-strategy game

This game has a single mixed equilibrium where strategy one is played with probability eq_prob.

gameanalysis.gamegen.travellers_dilemma(players=2, max_value=100)[source]¶

Return an instance of travellers dilemma

Strategies range from 2 to max_value, thus there will be max_value - 1 strategies.

gameanalysis.gamegen.two_player_zero_sum_game(num_strategies, distribution=<function default_distribution>)[source]¶

Generate a two-player, zero-sum game

gameanalysis.gamegen.width_bimodal(max_width, num_profiles, num_samples)[source]¶

Bimodal width distribution

This returns standard deviations from U[0, max_width] and half spreads from N[0, sqrt(max_width)].

gameanalysis.gamegen.width_bimodal_old(scale=1)[source]¶

Old bimodal width distribution

This returns a valid distribution, taking a scale parameter to correct for the scale invariance of guassian variance.

gameanalysis.gamegen.width_gaussian(max_width, num_profiles, num_samples)[source]¶

Gaussian width distribution

This returns standard deviations from U[0, max_width].

gameanalysis.gamegen.width_gaussian_old(scale=1)[source]¶

Old gaussian width distribution

This returns a valid distribution, taking a scale parameter to correct for the scale invariance of guassian variance.

gameanalysis.gamegen.width_gumbel(max_width, num_profiles, num_samples)[source]¶

Gumbel width distribution

Generates scales in U[0, max_width]

gameanalysis.gamegen.width_uniform(max_width, num_profiles, num_samples)[source]¶

Uniform width distribution

Generates halfwidths in U[0, max_width]

gameanalysis.gameio module¶

Utility module that contains code for parsing legacy game formats

class gameanalysis.gameio.GameSerializer(*args)[source]¶

Bases: object

An object with utilities for serializing a game with names

Parameters:	strategy_dict ({role: [strategy]}) – A dictionary mapping role to strategies. The resulting serializer is the sorted version of all inputs. If included, this must be the only parameter. roles ([role]) – A list of ordered roles. This must be included with strategies. strategies ([[strategy]]) – A list of lists of ordered strategies for each role. This must be included with roles.

from_payoff_symgrp(symgrps, dest=None)[source]¶

Read a set of payoffs from symmetry groups

Parameters:	symgrps ([{payoff: float, role: str, strategy: str}]) – A description of a set of payoffs as a list of dictionaries, where each dictionary gives the average payoff for players in role playing strategy. dest (ndarray, optional) – If supplied, dest will be written to instead of allocating a new array.

from_prof(prof)[source]¶

Read a profile from an auto-detected format

from_prof_json(dictionary)[source]¶

Read a profile from json

from_prof_string(prof_string, dest=None)[source]¶

Read a profile from a string

from_prof_symgrp(symgrps, dest=None)[source]¶

Read a profile from symmetry groups

Parameters:	symgrps ([{count: int, role: str, strategy: str}]) – A description of a profile as a list of dictionaries, where each dictionary lists a unique role strategy pair, and a count as the number of players playing it. dest (ndarray, optional) – If supplied, dest will be written to instead of allocating a new array.

from_role_json(role_json)[source]¶

role_index(role)[source]¶

Return the index of a role

role_split(array, axis=-1)[source]¶

role_strat_index(role, strat)[source]¶

Return the index of a role strat pair

strat_name(role_strat_index)[source]¶

Get the strategy name from a full index

to_deviation_payoff_json(profile, payoffs)[source]¶

Format a profile and deviation payoffs as json

to_payoff_json(profile, payoffs)[source]¶

Format a profile and payoffs as json

to_prof_json(prof, filter_zeros=True)[source]¶

Convert a profile to json

to_prof_printstring(prof)[source]¶

Convert a profile to a printable string

to_prof_string(prof)[source]¶

Convert a profile to a string

to_prof_symgrp(prof)[source]¶

Convert a profile to a symmetry group

to_role_json(role_info)[source]¶

Format role data as json

gameanalysis.gameio.read_base_game(json)[source]¶

gameanalysis.gameio.read_game(json)[source]¶

Constructor for Game

gameanalysis.gameio.read_sample_game(json)[source]¶

gameanalysis.gpgame module¶

class gameanalysis.gpgame.BaseGPGame(game, cv_jobs=0, cv_iters=16)[source]¶

Bases: gameanalysis.rsgame.BaseGame

A game that regresses payoffs with a Gaussian process

cv_jobs and cv_iters are passed to train_gp and subsequently.

get_mean_dev_payoffs(profiles)[source]¶

Get the mean deviation payoff over role partial profiles

Parameters:	profiles (ndarray) – A (num_roles, num_samples, num_role_strats) array, where the first dimension corresponding to the deviating role, i.e. the number of players in role i of dimension i should num_players[i] - 1.

get_payoffs(profiles)[source]¶

Get the payoffs for a set of profiles

is_complete()[source]¶

max_payoffs()[source]¶

min_payoffs()[source]¶

class gameanalysis.gpgame.DprGPGame(game, dpr_players=None, **base_args)[source]¶

Bases: gameanalysis.gpgame.BaseGPGame

Constructs a DPR game from GPs to estimate payoffs.

Uses self.DPR_players to determine number of reduced-game players for each role.

deviation_payoffs(mix, assume_complete=True, jacobian=False)[source]¶

class gameanalysis.gpgame.FullGPGame(game, **base_args)[source]¶

Bases: gameanalysis.gpgame.BaseGPGame

Fills in every profile in the game to estimate payoffs

deviation_payoffs(mix, assume_complete=True, jacobian=False)[source]¶

class gameanalysis.gpgame.NeighborGPGame(game, num_devs=4, **base_args)[source]¶

Bases: gameanalysis.gpgame.BaseGPGame

Evaluates GPs at profiles with the highest probability under mix.

Computes the weighted sum for an exact deviation_payoffs calculation, but on a subset of the profiles. Evaluates the GPs at the EV_samples profiles closest to mix. Weights are normalized by the sum of probabilities of evaluated profiles.

deviation_payoffs(mix, assume_complete=True, jacobian=False)[source]¶

nearby_profs(prof, num_devs)[source]¶

Returns profiles reachable by at most num_devs deviations

class gameanalysis.gpgame.PointGPGame(game, **base_args)[source]¶

Bases: gameanalysis.gpgame.BaseGPGame

Evaluates GPs at the ‘profile’ corresponding to mixture fractions.

This is similar to neighbor_devs with devs=0, but without rounding to integer numbers of players.

deviation_payoffs(mix, assume_complete=True, jacobian=False)[source]¶

class gameanalysis.gpgame.SampleGPGame(game, num_samples=1000, **base_args)[source]¶

Bases: gameanalysis.gpgame.BaseGPGame

Averages GP payoff estimates over profiles sampled from mix.

samples random profiles are drawn, distributed according to mix. The learned GP for each strategy is queried at each random profile. The values returned are averages over payoff estimates at the sampled profiles.

deviation_payoffs(mix, assume_complete=True, jacobian=False)[source]¶

gameanalysis.nash module¶

Module for computing nash equilibria

class gameanalysis.nash.RegretOptimizer(game, gtol=1e-08)[source]¶

Bases: object

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.

grad(mix, penalty)[source]¶

class gameanalysis.nash.ReplicatorDynamics(game, max_iters=10000, converge_thresh=1e-08, slack=0.001)[source]¶

Bases: object

Replicator dynamics

This will run at most max_iters of replicator dynamics and return unless the difference between successive mixtures is less than converge_thresh. This is an object to support pickling. Replicator Dynamics needs minimum and maximum payoffs in order to project successive iterations into the simplex. If these aren’t known then they should return inf and -inf respectively. Otherwise they can be conservative bounds.

class gameanalysis.nash.ReplicatorDynamicsOde(game, final_time=1000)[source]¶

Bases: object

A pickleable object to find Nash equilibria

This method uses ode integration on the replicator dynamics differential equation.

func(t, mix)[source]¶

grad(t, mix)[source]¶

gameanalysis.nash.min_regret_grid_mixture(game, points)[source]¶

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)[source]¶

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)[source]¶

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=None, at_least_one=False, **methods)[source]¶

Finds role-symmetric mixed Nash equilibria

Parameters:	regret_thresh (float) – The threshold to consider an equilibrium found. dist_thresh (float) – The threshold for considering equilibria distinct. grid_points (int > 1) – 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) – The number of random initializations. processes (int) – Number of processes to use when finding Nash equilibria. If greater than one, the game will need to be pickleable. methods ([str] or {str: {...}}, str in {'replicator', 'optimize',) – ‘replicatorode’} The methods to use to converge to an equilibrium. Methods should be an iterable of strings. Optionally, it can be a dictionary with extra options for each of the methods. If None, defaults to using all methods. EXAMPLE: nash.mixed_nash(game, replicator={}) at_least_one (bool) – Returns the minimum regret mixture found by replicator dynamics if no equilibria were within the regret threshold
Returns:	eqm – A generator over low regret mixtures
Return type:	(Mixture)

gameanalysis.nash.pure_nash(game, epsilon=0)[source]¶

Returns an array of all pure nash profiles

gameanalysis.reduction module¶

Module for computing player reductions

class gameanalysis.reduction.DeviationPreserving(num_strats, full_players, reduced_players)[source]¶

Bases: object

Deviation Preserving Reduction

Either reduced or full players must be specified, the other will be taken from the game.

expand_deviation_profiles(subgame_mask, role_index=None)[source]¶

Expand profiles that contribute to deviation payoffs

expand_profiles(profiles, return_contributions=False)[source]¶

Expand a set of profiles

If return_contributions then a boolean array of matching shape is returned indicating the payoffs that are needed for the initial profiles.

reduce_game(game, allow_incomplete=False)[source]¶

Convert an input game to a reduced game with new players

If allow_incomplete is true, then profiles with incomplete payoff data will still be returned. If game is a SampleGame, then the payoff with the smallest number of nonzero values will be used.

reduce_profiles(profiles, return_contributions=False)[source]¶

Reduces a set of profiles

If return_contributions returns ancillary information.

Returns:	red_profs – The reduced profiles red_inds – Index in red_profs for each payoff value that was reduced. full_inds – Index into profiles for each payoff value that was reduced. strat_inds – Index into a profile for the index of each payoff. Parallel with red_inds and full_inds.

class gameanalysis.reduction.Hierarchical(num_strats, full_players, reduced_players)[source]¶

Bases: object

Hierarchical Reduction

Either reduced or full players must be specified, the other will be taken from the game.

expand_deviation_profiles(subgame_mask, role_index=None)[source]¶

Expand profiles that contribute to deviation payoffs

expand_profiles(profiles)[source]¶

Expand a set of profiles

reduce_game(game, allow_incomplete=False)[source]¶

Convert an input game to a reduced game with new players

Allow incomplete is unused for hierarchical reduction.

reduce_profiles(profiles)[source]¶

Reduce a set of profiles

class gameanalysis.reduction.Identity(num_strats, num_players)[source]¶

Bases: object

Identity reduction (lack of reduction)

expand_deviation_profiles(subgame_mask, role_index=None)[source]¶

Expand profiles that contribute to deviation payoffs

expand_profiles(profiles)[source]¶

Returns full game profiles that contribute to reduced profile

reduce_game(game, allow_incomplete=False)[source]¶

Convert an input game to a reduced game with new players

Allow complete is not used.

reduce_profiles(profiles)[source]¶

Returns reduced profiles that contribute to the full profile

class gameanalysis.reduction.Twins(num_strats, full_players)[source]¶

Bases: gameanalysis.reduction.DeviationPreserving

Twins Reduction

Same as Deviation Preserving, but where the reduced players are two.

gameanalysis.reduction.reduce_game_dpr(game, reduced_players, *args, **kwargs)[source]¶

gameanalysis.regret module¶

A module for computing regret and social welfare of profiles

class gameanalysis.regret.SocialWelfareOptimizer(game, gtol=1e-08)[source]¶

Bases: object

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.

obj_func(mix, penalty)[source]¶

gameanalysis.regret.max_mixed_social_welfare(game, grid_points=2, random_restarts=0, processes=None, **swopt_args)[source]¶

Returns the maximum role symmetric mixed social welfare profile

Parameters:	grid_points (int > 1) – 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) – The number of random initializations. processes (int) – Number of processes to use when finding Nash equilibria. If greater than one, the game will need to be pickleable.

gameanalysis.regret.max_pure_social_welfare(game)[source]¶

Get the max social welfare pure profile

Returns a tuple of the max welfare and the corresponding profile

gameanalysis.regret.mixed_social_welfare(game, mix)[source]¶

Returns the social welfare of a mixed strategy profile

gameanalysis.regret.mixture_deviation_gains(game, mix, assume_complete=False)[source]¶

Returns all the gains from deviation from a mixed strategy

The result is ordered by role, then strategy.

gameanalysis.regret.mixture_regret(game, mix)[source]¶

Return the regret of a mixture profile

gameanalysis.regret.pure_social_welfare(game, profile)[source]¶

Returns the social welfare of a pure strategy profile in game

gameanalysis.regret.pure_strategy_deviation_gains(game, prof)[source]¶

Returns the pure strategy deviations gains

The result is a compact array of deviation gains. Each element corresponds to the deviation from strategy i to strategy j ordered by (i, j) for all valid deviations.

gameanalysis.regret.pure_strategy_regret(game, prof)[source]¶

Returns the regret of a pure strategy profile

If prof has more than one dimension, the last dimension is taken as a set of profiles and returned as a new array.

gameanalysis.rsgame module¶

Module for Role Symmetric Game data structures

There are three types of games:

BaseGame - Have no data but do contain convenience methods for working

with games in general. This should be extended by every object that can function as a game.

Game - Contains payoff data at a profile level, but that data can be

sparse.

SampleGame - Contain several samples of payoffs for every profile. Access

to the sample data is relatively limited and intended mostly for other functions that operate on the entire game at once.

Everything internally is represented as an array. Most methods will take any dimensional array as input, treating the last axis as a profile / payoff / etc, and treating all other axes as multiple data points, but this isn’t universal.

Most game objects have attributes that start with num, these will always be an attribute or a property, not a method, so to get the number of profiles, it’s just num_profiles not num_profiles(). These will also only be numbers, either a single int, or an array of them depending on the attribute.

class gameanalysis.rsgame.BaseGame(*args)[source]¶

Bases: object

Role-symmetric game representation

This object only contains methods and information about definition of the game, and does not contain methods to operate on observation data.

Parameters:

game (BaseGame) – Copies info from game. Useful to keep convenience methods of game without attached data. This argument should be by itself. num_players (int or [int] or ndarray) – The number of players in each role in order, or the number of players per role if identical (will be broadcast to match the number of roles). This should be included with num_strategies. num_strategies (int or [int] or ndarray) – The number of strategies in each role in order, or the number of strategies per role if identical (will be broadcast to match the number of roles). This should be included with num_players. number of roles is deduced from the number of entries in num_players (The) – num_strategies. If either is an integer or has length 1, the other is (and) – if both are integers or have length 1, the game will have one role. (used;) –

all_profiles()[source]¶

Return all profiles

biased_mixtures(bias=0.9)[source]¶

Generates mixtures biased towards one strategy for each role

Each role has one strategy played with probability bias; the reamaining 1-bias probability is distributed uniformly over the remaining S or S-1 strategies. If there’s only one strategy, it is played with probability 1.

deviation_payoffs(mix, assume_complete=False, jacobian=False)[source]¶

Returns the payoff for deviating to each role from mixture

If assume_complete, then expensive checks for missing data won’t be made. If jacobian, a tuple is returned, where the second value is the jacobian with respect to the mixture.

get_expected_payoffs(mix, assume_complete=False, jacobian=False, deviations=None)[source]¶

Returns the payoff of each role under mixture

If the payoffs for deviating from mix is already known, that an be passed in to save computation.

grid_mixtures(num_points)[source]¶

Returns all of the mixtures in a grid with n points

Parameters:	num_points (int > 1) – The number of points to have along one dimensions

is_asymmetric()[source]¶

Returns true if this game is asymmetric

is_symmetric()[source]¶

Returns true if this game is symmetric

max_payoffs()[source]¶

Returns the maximum payoff for each role

max_prob_prof(mix)[source]¶

Returns the pure strategy profile with highest probability.

min_payoffs()[source]¶

Returns the minimum payoff for each role

num_all_dpr_profiles¶

The number of unique dpr profiles

This calculation takes time exponential in the number of roles.

num_all_payoffs¶

The number of payoffs in all profiles

num_all_profiles¶

The total number of profiles in the game

Not just the ones with data.

profile_id(profiles)[source]¶

Return a unique integer representing a profile

pure_mixtures()[source]¶

Returns all mixtures where the probability is either 1 or 0.

pure_profiles()[source]¶

Return all pure profiles

A pure profile is a profile where only one strategy is played per role.

random_dev_profiles(mixture, num_samples=1)[source]¶

Return partial profiles where dev player is missing

Resulting shape of profiles is (num_samples, num_roles, num_role_strats). The first dimension is the sample, the next is the deviating role, leaving the last dimension for the partial profile.

random_deviator_profiles(mixture, num_samples=1)[source]¶

Return a profiles where one player is deviating from mix

Resulting shape of profiles is (num_samples, num_role_strats, num_role_strats). The first dimension is the sample, the next is the deviating strategy, leaving the last dimension for the actual profile.

random_mixtures(num_samples=1, alpha=1)[source]¶

Return a random mixed profile

Mixed profiles are sampled from a dirichlet distribution with parameter alpha. If alpha = 1 (the default) this is a uniform distribution over the simplex for each role. alpha in (0, 1) is baised towards high entropy mixtures, i.e. mixtures where one strategy is played in majority. alpha in (1, oo) is baised towards low entropy (uniform) mixtures.

random_profiles(mixture, num_samples=1)[source]¶

Sample profiles from a mixture

role_biased_mixtures(bias=0.9)[source]¶

Generates mixtures where one role-strategy is played with bias

If no roles have more than one strategy (a degenerate game), then this returns nothing.

role_reduce(array, axis=-1, ufunc=<MagicMock name='mock.add' id='140422160220792'>, keepdims=False)[source]¶

Reduce an array over roles

Use this to sum the payoffs by role for a payoff array, etc.

Parameters:	array (ndarray) – Input array. ufunc (ufunc) – Numpy function to reduce with axis (int) – The axis to reduce over keepdims (bool) – If true, the shape of array will be unchanged

role_repeat(array, axis=-1)[source]¶

Repeat an array by role

Takes an array of shape num_roles and turns it into shape num_role_strats so that the arrays can interract.

role_sizes¶

The number of profiles in each role (independent of others)

role_split(array, axis=-1)[source]¶

Split an array by roles

Parameters:	array (ndarray) – The array to split axis (int) – The axis to split along

simplex_project(mixture)[source]¶

Project an invalid mixture array onto the simplex

to_json(serial)[source]¶

to_str(serial)[source]¶

trim_mixture_support(mixture, supp_thresh=0.001)[source]¶

Trims strategies played less than supp_thresh from the support

uniform_mixture()[source]¶

Returns a uniform mixed profile

verify_mixture(mix, axis=-1)[source]¶

Verify that a mixture is valid for game

verify_profile(prof, axis=-1)[source]¶

Verify that a profile is valid for game

class gameanalysis.rsgame.Game(*args, *, verify=True)[source]¶

Bases: gameanalysis.rsgame.BaseGame

Role-symmetric game representation

This representation uses a sparse mapping from profiles to payoffs for role symmetric games. There are several variants on constructors that are all valid, and use combinations of various inputs, listed below. Payoffs for specific players in a profile can be nan to indicate they are missing. The profiles will not be listed in num_complete_profiles or counted as in the game, but their data can be accessed via get_payoffs, and they will be used for calculating deviation payoffs if possible.

Parameters:

game (BaseGame) – Game to copy information out of. This will copy as much information out of the game as possible. This can optionally be specified with profiles and payoffs. profiles (ndarray-like, optional) – The profiles for the game, if unspecified, this will try to be grabbed from game. Must be specified with payoffs. payoffs (ndarray-like, optional) – The payoffs for the game, if unspecified, payoffs will try to be grabbed from game. Must be specified with profiles. num_players (int or [int] or ndarray) – The number of players per role. See BaseGame. This must be specified with num_strategies, and optionally with profiles and payoffs. num_strategies (int or [int] or ndarray) – The number of strategies per role. See BaseGame. profiles – The profiles for the game, if unspecified, game will be empty. Must be specified with payoffs. payoffs – The payoffs for the game, if unspecified, game will be empty. Must be specified with profiles. matrix (ndarray-like) – The matrix of payoffs for an asymmetric game. The last axis is the payoffs for each player, the first axes are the strategies for each player. matrix.shape[:-1] must correspond to the number of strategies for each player. matrix.ndim - 1 must equal matrix.shape[-1]. This must be specified by itself.

deviation_payoffs(mix, assume_complete=False, jacobian=False)[source]¶

Computes the expected value of each pure strategy played against all opponents playing mix.

Parameters:

mix (ndarray) – The mix all other players are using assume_complete (bool) – If true, don’t compute missing data and replace with nans. Just return the potentially inaccurate results. jacobian (bool) – If true, the second returned argument will be the jacobian of the deviation payoffs with respect to the mixture. The first axis is the deviating strategy, the second axis is the strategy in the mix the jacobian is taken with respect to. The values that are marked nan are not very aggressive, so don’t rely on accurate nan values in the jacobian.

get_max_social_welfare(by_role=False)[source]¶

Returns the maximum social welfare over the known profiles.

If by_role is specified, then max social welfare applies to each role independently.

get_payoffs(profile)[source]¶

Returns an array of profile payoffs

if default is not None and game doesn’t have profile data, then an array populated by default is returned.

is_complete()[source]¶

Returns true if every profile has data

is_constant_sum()[source]¶

Returns true if this game is constant sum

is_empty()[source]¶

Returns true if no profiles have data

max_payoffs()[source]¶

Returns the maximum payoff for each role

min_payoffs()[source]¶

Returns the minimum payoff for each role

to_json(serial)[source]¶

to_str(serial)[source]¶

class gameanalysis.rsgame.SampleGame(*args, *, verify=True)[source]¶

Bases: gameanalysis.rsgame.Game

A Role Symmetric Game that has multiple samples per observation

This behaves the same as a normal Game object, except that it has a resample method, which will resample the used payoffs from the empirical distribution of payoffs, allowing bootstrapping over arbitrary statistics.

Parameters:

game (BaseGame) – Game to copy information out of. This will copy as much information out of the game as possible. profiles (ndarray-like, optional) – The profiles for the game, if unspecified, this will try to be grabbed from game. Must be specified with payoffs. sample_payoffs ([ndarray-like], optional) – The sample payoffs for the game. Each list is a set of payoff observations grouped by number of observations and parallel with profiles. If unspecified, payoffs will try to be grabbed from game. Must be specified with profiles. num_players (int or [int] or ndarray) – The number of players per role. See BaseGame. num_strategies (int or [int] or ndarray) – The number of strategies per role. See BaseGame. profiles – The profiles for the game, if unspecified, game will be empty. Must be specified with payoffs. sample_payoffs – The sample payoffs for the game. Each list is a set of payoff observations grouped by number of observations and parallel with profiles. If unspecified, game will be empty. Must be specified with profiles. matrix (ndarray-like) – The matrix of payoffs for an asymmetric game. The last axis is the number of observations for each payoff, the second to last axis is payoffs for each player, the first axes are the strategies for each player. matrix.shape[:-2] must correspond to the number of strategies for each player. matrix.ndim - 2 must equal matrix.shape[-2].

remean()[source]¶

Overwrite payoff values with mean payoff

resample(num_resamples=None, independent_profile=False, independent_role=False, independent_strategy=False)[source]¶

Overwrite payoff values with a bootstrap resample

Keyword Arguments:

num_resamples (The number of resamples to take for each realized) – payoff. By default this is equal to the number of observations for that profile. independent_profile (Sample each profile independently. In general,) – only profiles with a different number of observations will be resampled independently. (default: False) independent_role (Sample each role independently. Within a profile,) – the payoffs for each role will be drawn independently. (default: False) independent_strategy (Sample each strategy independently. Within a) – profile, the payoffs for each strategy will be drawn independently. (default: False) Each of the `independent_` arguments will increase the time to do a resample. `independent_strategy` doesn’t make any particular sense.

to_json(serial)[source]¶

to_str(serial)[source]¶

gameanalysis.script module¶

gameanalysis.script.create_parser()[source]¶

gameanalysis.script.main()[source]¶

gameanalysis.scriptutils module¶

gameanalysis.scriptutils.load_profiles(strings)[source]¶

Load profiles from a list of strings

Parameters:	strings ([str]) – A list of strings that are file names or json, and represent either a single profile or a list of profiles.
Returns:	prof_gen – A generator of json profiles.
Return type:	(prof)

gameanalysis.subgame module¶

Module for performing actions on subgames

A subgame is a game with a restricted set of strategies that usually make analysis tractable. Most representations just use a subgame mask, which is a bitmask over included strategies.

gameanalysis.subgame.additional_strategy_profiles(game, subgame_mask, role_strat_ind)[source]¶

Returns all profiles added by strategy at index

gameanalysis.subgame.all_subgames(game)[source]¶

Return an array of all of the subgames

gameanalysis.subgame.deviation_profiles(game, subgame_mask, role_index=None)[source]¶

Return strict deviation profiles

Strict means that all returned profiles will have exactly one player where subgame_mask is false, i.e.

np.all(np.sum(profiles * ~subgame_mask, 1) == 1)

If role_index is specified, only profiles for that role will be returned.

gameanalysis.subgame.maximal_subgames(game)[source]¶

Returns all maximally complete subgame masks

gameanalysis.subgame.num_all_subgames(game)[source]¶

Number of unique subgames

gameanalysis.subgame.num_deviation_payoffs(game, subgame_mask)[source]¶

Returns the number of deviation payoffs

This is a closed form way to compute np.sum(deviation_profiles(game, subgame_mask) > 0).

gameanalysis.subgame.num_deviation_profiles(game, subgame_mask)[source]¶

Returns the number of deviation profiles

This is a closed form way to compute deviation_profiles(game, subgame_mask).shape[0].

gameanalysis.subgame.num_dpr_deviation_profiles(game, subgame_mask)[source]¶

Returns the number of dpr deviation profiles

gameanalysis.subgame.num_pure_subgames(game)[source]¶

The number of pure subgames

gameanalysis.subgame.pure_subgames(game)[source]¶

Returns every pure subgame mask in a game

A pure subgame is a subgame where each role only has one strategy. This returns the pure subgames in sorted order based off of role and strategy.

gameanalysis.subgame.random_subgames(game, n=1)[source]¶

Return n random subgames

gameanalysis.subgame.subgame(game, subgame_mask)[source]¶

Returns a new game that only has data for profiles in subgame_mask

gameanalysis.subgame.subgame_from_id(game, subgame_id)[source]¶

Return a subgame mask from its unique indicator

gameanalysis.subgame.subgame_id(game, subgame_mask)[source]¶

Return a unique integer representing a subgame

gameanalysis.subgame.subserializer(serial, subgame_mask)[source]¶

Return a serializer for a subgame

gameanalysis.subgame.translate(profiles, subgame_mask)[source]¶

Translate a mixture or profile from a subgame to the full game

gameanalysis.utils module¶

gameanalysis.utils.acartesian2(*arrays)[source]¶

Array cartesian product in 2d

Produces a new ndarray that has the cartesian product of every row in the input arrays. The number of columns is the sum of the number of columns in each input. The number of rows is the product of the number of rows in each input.

Parameters:	*arrays ([ndarray (xi, s)]) –

gameanalysis.utils.acomb(n, k, repetition=False)[source]¶

Compute an array of all n choose k options

The result will be an array shape (m, n) where m is n choose k optionally with repetitions.

gameanalysis.utils.axis_to_elem(array, axis=-1)[source]¶

Converts an axis of an array into a unique element

In general, this returns a copy of the array, unless the data is contiguous. This usually requires that the last axis is the one being merged.

Parameters:	array (ndarray) – The array to convert an axis to a view. axis (int, optional) – The axis to convert into a single element. Defaults to the last axis.

gameanalysis.utils.comb(n, k)[source]¶

gameanalysis.utils.elem_to_axis(array, dtype, axis=-1)[source]¶

Converts and array of axis elements back to an axis

gameanalysis.utils.game_size(players, strategies)[source]¶

Number of profiles in a symmetric game with players and strategies

class gameanalysis.utils.hash_array(array)[source]¶

Bases: object

gameanalysis.utils.multinomial_mode(p, n)[source]¶

Compute the mode of n samples from multinomial distribution p.

Notes

algorithm from: Finucan 1964. The mode of a multinomial distribution.

notation follows: Gall 2003. Determination of the modes of a Multinomial distribution.

gameanalysis.utils.one_line(string, line_width=80)[source]¶

If string s is longer than line width, cut it off and append ”...”

gameanalysis.utils.only(iterable)[source]¶

Return the only element of an iterable

Throws a value error if the iterable doesn’t contain only one element

gameanalysis.utils.ordered_permutations(seq)[source]¶

Return an iterable over all of the permutations in seq

The elements of seq must be orderable. The permutations are taken relative to the value of the items in seq, not just their index. Thus:

>>> list(ordered_permutations([1, 2, 1]))
[(1, 1, 2), (1, 2, 1), (2, 1, 1)]

This function is taken from this blog post: http://blog.bjrn.se/2008/04/lexicographic-permutations-using.html And this stack overflow post: https://stackoverflow.com/questions/6534430/why-does-pythons-itertools-permutations-contain-duplicates-when-the-original

gameanalysis.utils.prod(collection)[source]¶

Product of all elements in the collection

gameanalysis.utils.simplex_project(array)[source]¶

Return the projection onto the simplex

gameanalysis.utils.unique_axis(array, axis=-1, **kwargs)[source]¶

Find unique axis elements

Parameters:	array (ndarray) – The array to find unique axis elements of axis (int, optional) – The axis to find unique elements of. Defaults to the last axis. **kwargs (flags) – The flags to pass to numpys unique function
Returns:	uniques (ndarray) – The unique axes as rows of a two dimensional array. *args – Any other results of the unique functions due to flags

Module contents¶