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]

  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

  • 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]

  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

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].

  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

  • 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