lemke.bimatrix#

Bimatrix game representation and Nash equilibrium computation.

Functions

`common_options`(f)
`rangesplit`(s[, endrange])	Parse a comma-separated range string such as "1-3,10,4-7" into a list of integers.
`str_eq`(eq, m, n)	Format an equilibrium strategy pair as a readable string.
`submatrix`(A, rowset, colset)	Extract a submatrix at the given row and column indices.
`supports`(eq, m, n)	Return the index sets where each player's strategy is nonzero.
`uniform`(n)	Return the uniform distribution over n outcomes as fractions.

Classes

`bimatrix`(A, B)	A two-player bimatrix game and methods to find its equilibria.
`payoffmatrix`(A)	A single player's payoff matrix, stored as exact fractions.

class lemke.bimatrix.bimatrix(A, B)[source]#

A two-player bimatrix game and methods to find its equilibria.

Parameters:

A (payoffmatrix) – Row player’s payoff matrix.
B (payoffmatrix) – Column player’s payoff matrix.

A#

Row player’s payoff matrix.

Type:: payoffmatrix

B#

Column player’s payoff matrix.

Type:: payoffmatrix

Examples

>>> from fractions import Fraction as F
>>> from lemke.bimatrix import bimatrix, payoffmatrix
>>> game = bimatrix(
...     A=payoffmatrix([[F(3), F(0)], [F(0), F(2)]]),
...     B=payoffmatrix([[F(2), F(0)], [F(0), F(7)]]),
... )
>>> game.A.numrows
2

LH(LHstring)[source]#

Find equilibria by running Lemke-Howson from several labels.

Parameters:: LHstring (str) – Range specification of labels to try, e.g. "1-3,7".
Returns:: Mapping from each distinct equilibrium found (as a tuple) to the list of labels that produced it. Also printed to stdout as equilibria are found.
Return type:: dict

Examples

Run Lemke-Howson for all labels. This prints progress as each label is tried, then a summary of all distinct equilibria found with the list of labels that produced it:

>>> from lemke.bimatrix import bimatrix
>>> game = bimatrix.from_file("game.txt")
>>> game.LH("1-")

createLCP()[source]#

Build the linear complementarity problem for this game.

Returns:: The LCP corresponding to this game.
Return type:: lcp

eqindex(eq, m, n)[source]#

Compute the index (+1/-1/0) of an equilibrium.

Parameters:

eq (sequence of fractions.Fraction) – Equilibrium strategy pair, flat tuple of length m + n.
m (int) – Number of rows (row player’s strategies).
n (int) – Number of columns (column player’s strategies).

Returns:

+1 or -1 for a regular equilibrium, 0 if the equilibrium is degenerate (supports of unequal size or singular submatrices).

Return type:

int

classmethod from_file(filename, decimals=4)[source]#

Create a bimatrix game from a text file.

Expects the file format:

<m> <n>
m*n entries of A
m*n entries of B

Blank lines and lines starting with # are ignored.

Parameters:

filename (str or pathlib.Path) – Path to the game file.
decimals (int, optional) – Number of decimal places to which payoffs written as decimals (e.g. 0.145) are rounded before conversion to fractions. Must be between 0 and utils.MAXDECIMALS. Default is utils.DEFAULT_DECIMALS.

Returns:

The game described by the file.

Return type:

bimatrix

Raises:

TypeError – If decimals is not an integer.
ValueError – If decimals is out of range, or a payoff is not a valid number.
SystemExit – If the number of payoff values in the file is incorrect.

Examples

Given a file game.txt containing::

# m,n= 2 2

# A= 3 0 0 2

# B= 2 0 0 7

>>> from lemke.bimatrix import bimatrix
>>> game = bimatrix.from_file("game.txt")
>>> print(game.A.numrows)
2

runLH(droppedlabel)[source]#

Run Lemke-Howson from a given dropped label.

Parameters:: droppedlabel (int) – The label to drop as the starting label for the Lemke-Howson path.
Returns:: The equilibrium strategy pair found, as a tuple of length m + n.
Return type:: tuple of fractions.Fraction
Raises:: RuntimeError – If the underlying Lemke’s algorithm unexpectedly fails to find a solution.

runtrace(xprior, yprior)[source]#

Run the tracing procedure from a given prior.

Parameters:

xprior (array_like of fractions.Fraction) – Row player’s prior strategy: m exact rational probabilities summing to 1, where m is the number of rows. Floats are not supported.
yprior (array_like of fractions.Fraction) – Column player’s prior strategy: n exact rational probabilities summing to 1, where n is the number of columns. Floats are not supported.

Returns:

The equilibrium strategy pair found, as a tuple of length m + n.

Return type:

tuple of fractions.Fraction

Raises:

RuntimeError – If the underlying Lemke’s algorithm unexpectedly fails to find a solution.

trace_random_priors(trace, seed=None, accuracy=1000)[source]#

Run the tracing procedure from several random priors.

Parameters:

trace (int) – Number of random priors to try. Must be positive.
seed (int, optional) – Random seed. If given, each prior k is seeded deterministically from seed and k, so results are reproducible. If None, priors are unseeded. Default is None.
accuracy (int, optional) – Denominator used to round each random prior’s coordinates to rational numbers. Default is 1000.

Raises:

ValueError – If trace is not a positive integer.

Examples

Run the tracing procedure from one random prior and print the equilibrium found:

>>> from lemke.bimatrix import bimatrix
>>> game = bimatrix.from_file("game.txt")
>>> game.trace_random_priors(1)

trace_uniform_prior()[source]#

Run the tracing procedure once, starting from a uniform prior.

Prints the resulting equilibrium.

Examples

Run the tracing procedure from a uniform prior and print the equilibrium found:

>>> from lemke.bimatrix import bimatrix
>>> game = bimatrix.from_file("game.txt")
>>> game.trace_uniform_prior()

lemke.bimatrix.common_options(f)[source]#

class lemke.bimatrix.payoffmatrix(A)[source]#

A single player’s payoff matrix, stored as exact fractions.

Wraps a matrix of fractions.Fraction entries as a NumPy array.

Parameters:: A (array_like of fractions.Fraction) – Payoff matrix of shape (m, n). Every entry must be a fractions.Fraction; ints and floats are not converted.
Raises:: TypeError – If any entry of A is not a fractions.Fraction.

numrows#

Number of rows, m.

Type:: int

numcolumns#

Number of columns, n.

Type:: int

matrix#

The payoff matrix as exact fractions.

Type:: numpy.ndarray of fractions.Fraction

max#

Running maximum entry of matrix.

Type:: fractions.Fraction

min#

Running minimum entry of matrix.

Type:: fractions.Fraction

negshift#

int(max) + 1, the shift used to make all entries positive.

Type:: int

negmatrix#

matrix shifted by negshift so all entries are positive (used when constructing the LCP).

Type:: numpy.ndarray

Examples

>>> from fractions import Fraction as F
>>> from lemke.bimatrix import payoffmatrix
>>> payoffs = payoffmatrix([[F(3), F(0)], [F(0), F(2)]])
>>> payoffs.numrows
2
>>> print(payoffs.max)
3

addcolumn(col)[source]#

Append a column to the matrix and update max/min.

Parameters:: col (array_like of fractions.Fraction) – Column to append; must have length numrows.
Raises:: TypeError – If any entry of col is not a fractions.Fraction.

addrow(row)[source]#

Append a row to the matrix and update max/min.

Parameters:: row (array_like of fractions.Fraction) – Row to append; must have length numcolumns.
Raises:: TypeError – If any entry of row is not a fractions.Fraction.

fullmaxmin()[source]#: Recompute max and min over the entire matrix.

updatemaxmin(fromrow, fromcol)[source]#

Update max, min, and negmatrix over a submatrix range.

Recomputes max/min by scanning entries from (fromrow, fromcol) to the end of the matrix, then recomputes negshift and negmatrix from the result.

Parameters:

fromrow (int) – First row index to include in the scan.
fromcol (int) – First column index to include in the scan.

lemke.bimatrix.rangesplit(s, endrange=50)[source]#: Parse a comma-separated range string such as “1-3,10,4-7” into a list of integers. Open-ended ranges like “5-” extend to endrange.

lemke.bimatrix.str_eq(eq, m, n)[source]#: Format an equilibrium strategy pair as a readable string.

lemke.bimatrix.submatrix(A, rowset, colset)[source]#: Extract a submatrix at the given row and column indices.

lemke.bimatrix.supports(eq, m, n)[source]#: Return the index sets where each player’s strategy is nonzero.

lemke.bimatrix.uniform(n)[source]#: Return the uniform distribution over n outcomes as fractions.