support_enumeration

Author: Daisuke Oyama

Compute all mixed Nash equilibria of a 2-player (non-degenerate) normal form game by support enumeration.

References

B. von Stengel, “Equilibrium Computation for Two-Player Games in Strategic and Extensive Form,” Chapter 3, N. Nisan, T. Roughgarden, E. Tardos, and V. Vazirani eds., Algorithmic Game Theory, 2007.

quantecon.game_theory.support_enumeration.is_singular(a)

Determine whether matrix a is numerically singular, by checking its singular values.

Parameters:

a : ndarray(float, ndim=2)

2-dimensional array of floats.

Returns:

bool

Whether a is numerically singular.

quantecon.game_theory.support_enumeration.next_k_array

Given an array a of k distinct nonnegative integers, return the next k-array in lexicographic ordering of the descending sequences of the elements. a is modified in place.

Parameters:

a : ndarray(int, ndim=1)

Array of length k.

Returns:

a : ndarray(int, ndim=1)

View of a.

Examples

Enumerate all the subsets with k elements of the set {0, ..., n-1}.

>>> n, k = 4, 2
>>> a = np.arange(k)
>>> while a[-1] < n:
...     print(a)
...     a = next_k_array(a)
...
[0 1]
[0 2]
[1 2]
[0 3]
[1 3]
[2 3]

quantecon.game_theory.support_enumeration.next_k_combination

Find the next k-combination, as described by an integer in binary representation with the k set bits, by “Gosper’s hack”.

Copy-paste from en.wikipedia.org/wiki/Combinatorial_number_system

Parameters:

x : int

Integer with k set bits.

Returns:

int

Smallest integer > x with k set bits.

quantecon.game_theory.support_enumeration.support_enumeration(g)

Compute mixed-action Nash equilibria with equal support size for a 2-player normal form game by support enumeration. For a non-degenerate game input, these are all Nash equilibria.

The algorithm checks all the equal-size support pairs; if the players have the same number n of actions, there are 2n choose n minus 1 such pairs. This should thus be used only for small games.

Parameters:

g : NormalFormGame

NormalFormGame instance with 2 players.

Returns:

list(tuple(ndarray(float, ndim=1)))

List containing tuples of Nash equilibrium mixed actions.

Notes

This routine is jit-complied if Numba version 0.28 or above is installed.

quantecon.game_theory.support_enumeration.support_enumeration_gen(g)

Generator version of support_enumeration.

Parameters:

g : NormalFormGame

NormalFormGame instance with 2 players.