nash.algorithms package¶
Submodules¶
nashpy.algorithms.support_enumeration module¶
A class for a normal form game
- nashpy.algorithms.support_enumeration.indifference_strategies(A: numpy.ndarray[Any, numpy.dtype[numpy.typing._generic_alias.ScalarType]], B: numpy.ndarray[Any, numpy.dtype[numpy.typing._generic_alias.ScalarType]], non_degenerate: bool = False, tol: float = 1e-16) Generator[Tuple[bool, bool, Any, Any], Any, None] [source]¶
A generator for the strategies corresponding to the potential supports
- Parameters
A (array) – The row player utility matrix.
B (array) – The column player utility matrix
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.
- Yields
Generator – 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: tuple, support_pair: Tuple[numpy.ndarray[Any, numpy.dtype[numpy.typing._generic_alias.ScalarType]], numpy.ndarray[Any, numpy.dtype[numpy.typing._generic_alias.ScalarType]]], payoff_matrices: Tuple[numpy.ndarray[Any, numpy.dtype[numpy.typing._generic_alias.ScalarType]], numpy.ndarray[Any, numpy.dtype[numpy.typing._generic_alias.ScalarType]]]) bool [source]¶
Test if a given strategy pair is a pair of best responses
- Parameters
strategy_pair (tuple) – a 2-tuple of numpy arrays.
support_pair (tuple) – a 2-tuple of numpy arrays of integers.
payoff_matrices (tuple) – a 2-tuple of numpy array of payoff matrices.
- Returns
True if a given strategy pair is a pair of best responses.
- Return type
bool
- nashpy.algorithms.support_enumeration.obey_support(strategy, support: numpy.ndarray[Any, numpy.dtype[numpy.typing._generic_alias.ScalarType]], tol: float = 1e-16) bool [source]¶
Test if a strategy obeys its support
- Parameters
strategy (array) – A given strategy vector
support (array) – A strategy support
tol (float) – A tolerance parameter for equality.
- Returns
whether or not that strategy does indeed have the given support
- Return type
bool
- nashpy.algorithms.support_enumeration.potential_support_pairs(A: numpy.ndarray[Any, numpy.dtype[numpy.typing._generic_alias.ScalarType]], B: numpy.ndarray[Any, numpy.dtype[numpy.typing._generic_alias.ScalarType]], non_degenerate: bool = False) Generator[tuple, Any, None] [source]¶
A generator for the potential support pairs
- Parameters
A (array) – The row player utility matrix.
B (array) – The column player utility matrix
non_degenerate (bool) – Whether or not to consider supports of equal size. By default (False) only considers supports of equal size.
- Yields
Generator – A pair of possible supports.
- nashpy.algorithms.support_enumeration.powerset(n: int) Iterator[Tuple[Any, ...]] [source]¶
A power set of range(n)
Based on recipe from python itertools documentation:
https://docs.python.org/2/library/itertools.html#recipes
- Parameters
n (int) – The defining parameter of the powerset.
- Returns
The powerset
- Return type
Iterator
- nashpy.algorithms.support_enumeration.solve_indifference(A, rows=None, columns=None) Union[bool, Any] [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 (array) – The row player utility matrix.
rows (array) – Array of integers corresponding to rows to consider.
columns (array) – Array of integers corresponding to columns to consider.
- Returns
The solution to the indifference equations.
- Return type
Union
- nashpy.algorithms.support_enumeration.support_enumeration(A: numpy.ndarray[Any, numpy.dtype[numpy.typing._generic_alias.ScalarType]], B: numpy.ndarray[Any, numpy.dtype[numpy.typing._generic_alias.ScalarType]], non_degenerate: bool = False, tol: float = 1e-16) Generator[Tuple[bool, bool], Any, None] [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.
- Parameters
A (array) – The row player utility matrix.
B (array) – The column player utility matrix
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.
- Yields
Generator – The equilibria.
nashpy.algorithms.vertex_enumeration module¶
A class for the vertex enumeration algorithm
- nashpy.algorithms.vertex_enumeration.vertex_enumeration(A: numpy.ndarray[Any, numpy.dtype[numpy.typing._generic_alias.ScalarType]], B: numpy.ndarray[Any, numpy.dtype[numpy.typing._generic_alias.ScalarType]]) Generator[Tuple[float, float], Any, None] [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
- Parameters
A (array) – The row player utility matrix.
B (array) – The column player utility matrix
- Yields
Generator – The equilibria.
nashpy.algorithms.lemke_howson module¶
A class for the Lemke Howson algorithm
- nashpy.algorithms.lemke_howson.lemke_howson(A: numpy.ndarray[Any, numpy.dtype[numpy.typing._generic_alias.ScalarType]], B: numpy.ndarray[Any, numpy.dtype[numpy.typing._generic_alias.ScalarType]], initial_dropped_label: int = 0) Tuple[numpy.ndarray[Any, numpy.dtype[numpy.typing._generic_alias.ScalarType]], numpy.ndarray[Any, numpy.dtype[numpy.typing._generic_alias.ScalarType]]] [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
A (array) – The row player payoff matrix
B (array) – The column player payoff matrix
initial_dropped_label (int) – The initial dropped label.
- Returns
An equilibria
- Return type
Tuple
- nashpy.algorithms.lemke_howson.shift_tableau(tableau: numpy.ndarray[Any, numpy.dtype[numpy.typing._generic_alias.ScalarType]], shape: Tuple[int, ...]) numpy.ndarray[Any, numpy.dtype[numpy.typing._generic_alias.ScalarType]] [source]¶
Shift a tableau to ensure labels of pairs of tableaux coincide
- Parameters
tableau (array) – a tableau corresponding to a vertex of a polytope.
shape (tuple) – the required shape of the tableau
- Returns
The shifted tableau
- Return type
array
- nashpy.algorithms.lemke_howson.tableau_to_strategy(tableau: numpy.ndarray[Any, numpy.dtype[numpy.typing._generic_alias.ScalarType]], basic_labels: Set[int], strategy_labels: Iterable) numpy.ndarray[Any, numpy.dtype[numpy.typing._generic_alias.ScalarType]] [source]¶
Return a strategy vector from a tableau
- Parameters
tableau (array) – a tableau corresponding to a vertex of a polytope.
basic_labels (set) – the set of basic labels.
strategy_labels (Iterable) – the set of labels that correspond to strategies.
- Returns
A strategy.
- Return type
array