Computing the index of an equilibrium component
The task is to implement a published algorithm to compute
the so-called index of an equilibrium component in a
bimatrix game. This component is the output to an existing
enumeration algorithm.
- Languages: C
- Prerequisites: Senior-level mathematics, interest in game theory
and some basic topology.
Fuller details:
The aim of this project is to implement an existing
algorithm that finds the index of an equilibrium component.
The relevant description of this is chapter 2 of
- which are pages 21-41 of
- http://www.maths.lse.ac.uk/Personal/stengel/phds/anne-final.pdf
The mathematics in this chapter are pretty scary (in
particular section 2.2, which is however not needed) but the
final page 41 which describes the algorithm is less scary.
Nevertheless, this is rather advanced material because it
builds on several different existing algorithms (for finding
extreme equilibria in bimatrix games, and “cliques” that
define convex sets of equilibria, and their non-disjoint
unions that define “components”). It requires the
understanding of what equilibria in bimatrix games are
about. These algorithms are described in
and students who do not eventually understand that text
should not work on this project. For this reason, at least
senior-level (= third year) mathematics is required in terms of
mathematical maturity. In the Avis et al. (2010) paper,
pages 19-21 describe the lexicographic method for pivoting
as it is used in the simplex method for linear programming.
A variant of this lexicographic method is used in the
chapter by Anne Balthasar. Understanding this is a
requirement to work on this project (and a good test of how
accessible all this is).
We give here two brief examples that supplement the above
literature. Consider the following bimatrix game. It is
very simple, and students of game theory may find it useful
to first find out on their own what the equilibria of this
game are:
2 x 2 Payoff matrix A:
1 1
0 1
2 x 2 Payoff matrix B:
1 1
0 1
EE = Extreme Equilibrium, EP = Expected Payoff
EE 1 P1: (1) 1 0 EP= 1 P2: (1) 1 0 EP= 1
EE 2 P1: (1) 1 0 EP= 1 P2: (2) 0 1 EP= 1
EE 3 P1: (2) 0 1 EP= 1 P2: (2) 0 1 EP= 1
Connected component 1:
{1, 2} x {2}
{1} x {1, 2}
This shows the following: there are 3 Nash equilibria,
which partly use the same strategies of the two players,
which are numbered (1), (2) for each player. It will take
a bit of time to understand the above output. For our
purposes, the bottom “component” is most relevant:
It has two lines, and {1, 2} x {2} means
that equilibrium (1),(2) - which is according to the
previous list the strategy pair (1,0), (1,0) as well as
(2),(2), which is (0,1), (1,0) are “extreme
equilibria”, and moreover any convex combination of (1) and
(2) of player 1 - this is the first {1, 2} - can be
combined with strategy (2) of player 2.
This is part of the “clique” output of Algorithm 2 on page
19 of Avis et al. (2010).
There is a second such convex set of equilibria in the
second line, indicated by {1} x {1, 2}.
Moreover, these two convex sets intersect (in the
equilibrium (1),(2)) and form therefore a “component” of
equilibria. For such a component, the index has to be
found, which happens to be the integer 1 in this case.
The following bimatrix game has also two convex sets of Nash
equilibria, but they are disjoint and therefore listed as
separate components on their own:
3 x 2 Payoff matrix A:
1 1
0 1
1 0
3 x 2 Payoff matrix B:
2 1
0 1
0 1
EE = Extreme Equilibrium, EP = Expected Payoff
Rational Output
EE 1 P1: (1) 1 0 0 EP= 1 P2: (1) 1 0 EP= 2
EE 2 P1: (2) 1/2 1/2 0 EP= 1 P2: (2) 0 1 EP= 1
EE 3 P1: (3) 1/2 0 1/2 EP= 1 P2: (1) 1 0 EP= 1
EE 4 P1: (4) 0 1 0 EP= 1 P2: (2) 0 1 EP= 1
Connected component 1:
{1, 3} x {1}
Connected component 2:
{2, 4} x {2}
Here the first component has index 1 and the second has
index 0. One reason for the latter is that if the game is
slightly perturbed, for example by giving a slightly lower
payoff than 1 in row 2 of the game, then the second strategy
of player 1 is strictly dominated and the equilibria (2) and
(4) of player 1, and thus the entire component 2, disappear
altogether. This can only happen if the index is zero, so
the index gives some useful information as to whether an
equilibrium component is “robust” or “stable” when payoffs
are slightly perturbed.