Source files

Subpackages

• nash.algorithms package
  • Submodules
  • nashpy.algorithms.support_enumeration module
    • indifference_strategies()
    • is_ne()
    • obey_support()
    • potential_support_pairs()
    • powerset()
    • solve_indifference()
    • support_enumeration()
  • nashpy.algorithms.vertex_enumeration module
    • vertex_enumeration()
  • nashpy.algorithms.lemke_howson module
    • lemke_howson()
• nash.learning package
  • Submodules
  • nashpy.learning.fictitious_play module
    • fictitious_play()
    • get_best_response_to_play_count()
    • update_play_count()

Submodules

nashpy.game module

A class for a normal form game

class nashpy.game.Game(*args: Any)

Bases: object

A class for a normal form game.

Parameters:

• A (-) – non zero sum games.

• B (2 dimensional list/arrays representing the payoff matrices for) – non zero sum games.

• A – zero sum game.

asymmetric_replicator_dynamics(x0=None, y0=None, timepoints=None)

Returns two arrays, corresponding to the two players, showing the probability of each strategy being played over time using the asymmetric replicator dynamics algorithm.

Parameters:

• x0 (array) – The initial population distribution of the row player.

• y0 (array) – The initial population distribution of the column player.

• timepoints (array) – The iterable of timepoints.

Returns:

The 2 population distributions over time.

Return type:

Tuple

fictitious_play(iterations, play_counts=None)

Return a given sequence of actions through fictitious play. The implementation corresponds to the description of chapter 2 of [Fudenberg1998].

1. Players have a belief of the strategy of the other player: a vector representing the number of times the player has chosen a given strategy. 2. Players choose a best response to the belief. 3. Players update their belief based on the latest choice of the opponent.

Parameters:

• iterations (int) – The number of iterations of the algorithm.

• play_counts (array) – The play counts.

Returns:

The play counts

Return type:

Generator

fixation_probabilities(initial_population, repetitions, replacement_stochastic_matrix: ndarray[Any, dtype[_ScalarType_co]] | None = None, interaction_graph_adjacency_matrix: ndarray[Any, dtype[_ScalarType_co]] | None = None)

Return the fixation probabilities for all types of individuals.

The returned array will have the same dimension as the number of rows or columns as the payoff matrix A. The ith element of the returned array corresponds to the probability that the ith strategy becomes fixed given the initial population.

This is a stochastic algorithm and the probabilities are estimated over a number of repetitions.

Parameters:

• initial_population (array) – the initial population

• repetitions (int) – The number of iterations of the algorithm.

• replacement_stochastic_matrix (array) – Individual i chosen for replacement will replace individual j with probability P_{ij}. Default is None: this is equivalent to P_{ij} = 1 / N for all i, j.

• interaction_graph_adjacency_matrix (array) – the adjacency matrix for the interaction graph G: individuals of type i interact with individuals of type j count towards fitness iff G_{ij} = 1. Default is None: if so a complete graph is used – this corresponds to all individuals interacting with each other (with no self interactions)

Returns:

The fixation probability of each type.

Return type:

array

imitation_dynamics(population_size=100, iterations=1000, random_seed=None, threshold=0.5)

Simulate the imitation dynamics for a given game represented by payoff matrices A and B.

Parameters:

• population_size (number) – number of individuals in the population of the group (default: 100)

• iterations (number) – number of generations to simulate (default: 1000)

• random_seed (number) – seed for reproducibility (default: None)

• threshold (float) – threshold value for representing strategies as 0 or 1 (default: 0.5)

Returns:

The equilibria.

Return type:

Generator

is_best_response(sigma_r, sigma_c)

Checks if sigma_r is a best response to sigma_c and vice versa.

Parameters:

• sigma_r (array) – The row player strategy

• sigma_c (array) – The column player strategy

Returns:

A pair of booleans, the first indicates if sigma_r is a best response to sigma_c. The second indicates if sigma_c is a best response to sigma_r.

Return type:

tuple

lemke_howson(initial_dropped_label)

Obtain the Nash equilibria using the Lemke Howson algorithm implemented using integer pivoting.

Algorithm implemented here is Algorithm 3.6 of [Nisan2007].

1. Start at the artificial equilibrium (which is fully labeled)

2. Choose an initial label to drop and move in the polytope for which the vertex has that label to the edge that does not share that label. (This is implemented using integer pivoting)

3. A label will now be duplicated in the other polytope, drop it in a similar way.

4. Repeat steps 2 and 3 until have Nash Equilibrium.

Parameters:

initial_dropped_label (int) – The initial dropped label.

Returns:

An equilibria

Return type:

Tuple

lemke_howson_enumeration()

Obtain Nash equilibria for all possible starting dropped labels using the lemke howson algorithm. See Game.lemke_howson for more information.

Note: this is not guaranteed to find all equilibria.

Yields:

Tuple – An equilibria

linear_program()

Returns the Nash Equilibrium for a zero sum game by solving the Linear Program that corresponds to the minimax theorem.

Returns:

The Nash equilibria

Return type:

tuple

Raises:

ValueError – A value error is raised if the game is not zero sum

moran_process(initial_population, mutation_probability=0, replacement_stochastic_matrix: ndarray[Any, dtype[_ScalarType_co]] | None = None, interaction_graph_adjacency_matrix: ndarray[Any, dtype[_ScalarType_co]] | None = None)

Return a generator of population across the Moran process. The last population is when only a single type of individual is present in the population.

Parameters:

• initial_population (array) – the initial population

• mutation_probability (float) – the probability of an individual selected to be copied mutates to another individual from the original set of strategies (even if they are no longer present in the population).

• replacement_stochastic_matrix (array) – Individual i chosen for replacement will replace individual j with probability P_{ij}. Default is None: this is equivalent to P_{ij} = 1 / N for all i, j.

• interaction_graph_adjacency_matrix (array) – the adjacency matrix for the interaction graph G: individuals of type i interact with individuals of type j count towards fitness iff G_{ij} = 1. Default is None: if so a complete graph is used – this corresponds to all individuals interacting with each other (with no self interactions)

Returns:

The generations.

Return type:

Generator

regret_minimization(learning_rate=0.1, iterations=100)

Obtain the Nash equilibria using regret minimization method using N number of itreations. The code provided is based on the concept of regret matching, with the fixed learning rate.

Algorithm implemented here is Algorithm 4.3 Theorem 4.4 of [Nisan2007]

1. Build best Strategies probability of both players

Parameters:

• learning_rate (float) – The learning_rate determines the magnitude of the update towards the regrets

• iterations (Integer) – This value is defaulted to 100 itrations, this number could be modified to a larger or smaller number based on the untilities/payoff matrix shape

Returns:

The equilibria.

Return type:

Generator

replicator_dynamics(y0=None, timepoints=None, mutation_matrix=None)

Implement replicator dynamics Return an array showing probability of each strategy being played over time. The total population is constant. Strategies can either stay constant if equilibria is achieved, replicate or die.

Parameters:

• y0 (array) – The initial population distribution.

• timepoints (array) – The iterable of timepoints.

• mutation_matrix (array) – The mutation rate matrix. Element [i, j] gives the probability of an individual of type i mutating to an individual of type j. Default behaviour is to be the identity matrix which corresponds to no mutation.

Returns:

The population distributions over time.

Return type:

array

stochastic_fictitious_play(iterations, play_counts=None, etha=0.1, epsilon_bar=0.01)

Return a given sequence of actions and mixed strategies through stochastic fictitious play. The implementation corresponds to the description given in [Hofbauer2002].

Parameters:

• iterations (int) – The number of iterations of the algorithm.

• play_counts (array) – The play counts.

• etha (float) – The noise parameter for the logit choice function.

• epsilon_bar (float) – The maximum stochastic perturbation.

Returns:

The play counts

Return type:

Generator

support_enumeration(non_degenerate=False, tol=1e-16)

Obtain the Nash equilibria using support enumeration.

Algorithm implemented here is Algorithm 3.4 of [Nisan2007].

1. For each k in 1…min(size of strategy sets)

2. For each I,J supports of size k

3. Solve indifference conditions

4. Check that have Nash Equilibrium.

Parameters:

• non_degenerate (bool) – Whether or not to consider supports of equal size. By default (False) only considers supports of equal size.

• tol (float) – A tolerance parameter for equality.

Returns:

The equilibria.

Return type:

generator

vertex_enumeration()

Obtain the Nash equilibria using enumeration of the vertices of the best response polytopes.

Algorithm implemented here is Algorithm 3.5 of [Nisan2007].

1. Build best responses polytopes of both players

2. For each vertex pair of both polytopes

3. Check if pair is fully labelled

4. Return the normalised pair

Returns:

The equilibria.

Return type:

generator

Module contents

A library with algorithms on 2 player games.