nash.algorithms package

Submodules

nashpy.algorithms.support_enumeration module

A class for a normal form game

nashpy.algorithms.support_enumeration.indifference_strategies(A, B, non_degenerate=False, tol=1e-16)[source]

A generator for the strategies corresponding to the potential supports

Returns:
  • A generator of all potential strategies that are indifferent on each
  • potential support. Return False if they are not valid (not a
  • probability vector OR not fully on the given support).
nashpy.algorithms.support_enumeration.is_ne(strategy_pair, support_pair, payoff_matrices)[source]

Test if a given strategy pair is a pair of best responses

Parameters:
  • strategy_pair (a 2-tuple of numpy arrays) –
  • support_pair (a 2-tuple of numpy arrays) –
nashpy.algorithms.support_enumeration.obey_support(strategy, support, tol=1e-16)[source]

Test if a strategy obeys its support

Parameters:
  • strategy (a numpy array) – A given strategy vector
  • support (a numpy array) – A strategy support
Returns:

  • A boolean (whether or not that strategy does indeed have the given)
  • support

nashpy.algorithms.support_enumeration.potential_support_pairs(A, B, non_degenerate=False)[source]

A generator for the potential support pairs

Returns:
Return type:A generator of all potential support pairs
nashpy.algorithms.support_enumeration.powerset(n)[source]

A power set of range(n)

Based on recipe from python itertools documentation:

https://docs.python.org/2/library/itertools.html#recipes

nashpy.algorithms.support_enumeration.solve_indifference(A, rows=None, columns=None)[source]

Solve the indifference for a payoff matrix assuming support for the strategies given by columns

Finds vector of probabilities that makes player indifferent between rows. (So finds probability vector for corresponding column player)

Parameters:
  • A (a 2 dimensional numpy array (A payoff matrix for the row player)) –
  • rows (the support played by the row player) –
  • columns (the support player by the column player) –
Returns:

  • A numpy array
  • A probability vector for the column player that makes the row
  • player indifferent. Will return False if all entries are not >= 0.

nashpy.algorithms.support_enumeration.support_enumeration(A, B, non_degenerate=False, tol=1e-16)[source]

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.
Returns:equilibria
Return type:A generator.

nashpy.algorithms.vertex_enumeration module

A class for the vertex enumeration algorithm

nashpy.algorithms.vertex_enumeration.vertex_enumeration(A, B)[source]

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:equilibria
Return type:A generator.

nashpy.algorithms.lemke_howson module

A class for the Lemke Howson algorithm

nashpy.algorithms.lemke_howson.lemke_howson(A, B, initial_dropped_label=0)[source]

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) –
Returns:equilibria
Return type:A tuple.
nashpy.algorithms.lemke_howson.shift_tableau(tableau, shape)[source]

Shift a tableau to ensure labels of pairs of tableaux coincide

Parameters:
  • tableau (a numpy array) –
  • shape (a tuple) –
Returns:

tableau

Return type:

a numpy array

nashpy.algorithms.lemke_howson.tableau_to_strategy(tableau, basic_labels, strategy_labels)[source]

Return a strategy vector from a tableau

Parameters:
  • tableau (a numpy array) –
  • basic_labels (a set) –
  • strategy_labels (a set) –
Returns:

strategy

Return type:

a numpy array