nash.algorithms package

Submodules

nashpy.algorithms.support_enumeration module

A class for a normal form game

nashpy.algorithms.support_enumeration.indifference_strategies(A: ndarray[Any, dtype[_ScalarType_co]], B: ndarray[Any, dtype[_ScalarType_co]], non_degenerate: bool = False, tol: float = 1e-16) → Generator[Tuple[bool, bool, Any, Any], Any, None]

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[ndarray[Any, dtype[_ScalarType_co]], ndarray[Any, dtype[_ScalarType_co]]], payoff_matrices: Tuple[ndarray[Any, dtype[_ScalarType_co]], ndarray[Any, dtype[_ScalarType_co]]]) → bool

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: ndarray[Any, dtype[_ScalarType_co]], tol: float = 1e-16) → bool

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: ndarray[Any, dtype[_ScalarType_co]], B: ndarray[Any, dtype[_ScalarType_co]], non_degenerate: bool = False) → Generator[tuple, Any, None]

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

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) → bool | Any

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: ndarray[Any, dtype[_ScalarType_co]], B: ndarray[Any, dtype[_ScalarType_co]], non_degenerate: bool = False, tol: float = 1e-16) → Generator[Tuple[bool, bool], Any, None]

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: ndarray[Any, dtype[_ScalarType_co]], B: ndarray[Any, dtype[_ScalarType_co]]) → Generator[Tuple[float, float], Any, None]

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: ndarray[Any, dtype[_ScalarType_co]], B: ndarray[Any, dtype[_ScalarType_co]], initial_dropped_label: int = 0, lexicographic: bool = True) → Tuple[ndarray[Any, dtype[_ScalarType_co]], ndarray[Any, dtype[_ScalarType_co]]]

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.

• lexicographic (bool) – Whether to apply lexicographic sorting during pivoting, default True. Lexiographic sorting ensures solutions on degenerate games

Returns:

An equilibria

Return type:

Tuple