Finding equilibria of a bimatrix game#
This tutorial shows how to define a two-player game in strategic form and compute its Nash equilibria with the Lemke-Howson algorithm and with the tracing procedure.
In a bimatrix game, the row player has \(m\) pure strategies, the column player has \(n\), and the payoffs are given by two \(m \times n\) matrices \(A\) (row player) and \(B\) (column player). All payoffs are stored as exact fractions.
Throughout we use this coordination game:
Creating a game#
A game is represented by the bimatrix class,
which contains two payoffmatrix objects, one per player.
A game instance can be created in two ways.
1) From Python#
First wrap each payoff matrix in a payoffmatrix,
then combine them:
>>> 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)],
... ]),
... )
>>> print(game.A.numrows)
2
A payoffmatrix also records useful facts about its entries,
for example its largest entry:
>>> print(game.A.max)
3
Note
Every entry must be an exact rational (fractions.Fraction).
Other types cannot be passed directly.
2) From a file#
Alternatively, describe the game in a text file and load it with
from_file().
First, create a file such as examples/game:
# m,n=
2 2
# A=
3 0
0 2
# B=
2 0
0 7
then load it:
>>> game = bimatrix.from_file("examples/game")
>>> print(game.A.numrows)
2
See details about how the input file should be formatted on the file formats page.
Lemke-Howson#
The Lemke-Howson algorithm finds one equilibrium for each starting label.
There are \(m + n\) labels, one for each pure strategy of either player.
LH() takes a string saying which labels to
try, for example "1-3,7". You can also pass "1-" for all labels:
>>> result = game.LH("1-")
label 1 found eq (1,0),(1,0)
supports: [0][0]
label 2 found eq (0,1),(0,1)
supports: [1][1]
-------- equilibria found: --------
(1,0),(1,0)
supports: [0][0] found by labels [1, 3]
(0,1),(0,1)
supports: [1][1] found by labels [2, 4]
This prints a line each time a new equilibrium is found, followed by a summary of all distinct equilibria and the labels that found them.
The same information is returned as a dictionary, which maps each equilibrium (a tuple) to the list of labels that produced it:
>>> for eq, labels in result.items():
... print(labels)
... print(eq)
[1, 3]
(Fraction(1, 1), Fraction(0, 1), Fraction(1, 1), Fraction(0, 1))
[2, 4]
(Fraction(0, 1), Fraction(1, 1), Fraction(0, 1), Fraction(1, 1))
Note
Different labels can lead to the same equilibrium, and Lemke-Howson may not find all equilibria of a game. For this game, it found two pure strategy equilibria, but not the mixed strategy one: \((\frac{7}{9}, \frac{2}{9}), (\frac{2}{5}, \frac{3}{5})\).
The tracing procedure#
The tracing procedure is another way to find an equilibrium. It starts from a prior: a pair of mixed strategies, one per player, that represents initial beliefs. The equilibrium found depends on the prior.
Uniform prior#
trace_uniform_prior() runs the procedure once
from the uniform prior, where each player mixes equally over all their
pure strategies, and prints the equilibrium found:
>>> game.trace_uniform_prior()
-------- statistics of equilibria found: --------
1 times found (0,1),(0,1)
supports: [1][1]
1 total priors, 1 equilibria found
Random priors#
trace_random_priors() runs the procedure from
several random priors, to see which equilibria they lead to and how often.
To make a run reproducible, pass a seed:
>>> game.trace_random_priors(100, seed=1, accuracy=100)
found eq (1,0),(1,0)
supports: [0][0] index 1
found eq (0,1),(0,1)
supports: [1][1] index 1
-------- statistics of equilibria found: --------
24 times found (1,0),(1,0)
supports: [0][0]
76 times found (0,1),(0,1)
supports: [1][1]
100 total priors, 2 equilibria found
The priors are sampled uniformly from the simplex and
rounded to fractions with denominator accuracy (default 1000).
Check this tutorial to see how the sampling and rounding work.