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:
-
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]
For each k in 1…min(size of strategy sets)
For each I,J supports of size k
Solve indifference conditions
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]
Build best responses polytopes of both players
For each vertex pair of both polytopes
Check if pair is fully labelled
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].
Start at the artificial equilibrium (which is fully labeled)
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)
A label will now be duplicated in the other polytope, drop it in a similar way.
Repeat steps 2 and 3 until have Nash Equilibrium.
- Parameters
initial_dropped_label (int) –
- Returns
equilibria
- Return type
A tuple.