Merschen, Julian
(2011)
Nash equilibria, gale strings, and perfect
matchings.
PhD thesis, London School of Economics and Political Science.
Abstract
This thesis concerns the problem 2NASH of ﬁnding a Nash equilibrium of a bimatrix
game, for the special class of socalled “hardtosolve” bimatrix games. The term “hardtosolve” relates to the exponential running time of the famous and often used Lemke–
Howson algorithm for this class of games. The games are constructed with the help of
dual cyclic polytopes, where the algorithm can be expressed combinatorially via labeled
bitstrings deﬁned by the “Gale evenness condition” that characterise the vertices of these
polytopes.
We deﬁne the combinatorial problem “Another completely labeled Gale string” whose
solutions deﬁne the Nash equilibria of any game deﬁned by cyclic polytopes, including
the games where the Lemke–Howson algorithm takes exponential time. We show that
“Another completely labeled Gale string” is solvable in polynomial time by a reduction to
the “Perfect matching” problem in Euler graphs. We adapt the Lemke–Howson algorithm
to pivot from one perfect matching to another and show that again for a certain class
of graphs this leads to exponential behaviour. Furthermore, we prove that completely
labeled Gale strings and perfect matchings in Euler graphs come in pairs and that the
Lemke–Howson algorithm connects two strings or matchings of opposite signs.
The equivalence between Nash Equilibria of bimatrix games derived from cyclic polytopes, completely labeled Gale strings, and perfect matchings in Euler Graphs implies that
counting Nash equilibria is #Pcomplete. Although one Nash equilibrium can be computed in polynomial time, we have not succeeded in ﬁnding an algorithm that computes
a Nash equilibrium of opposite sign. However, we solve this problem for certain special cases, for example planar graphs. We illustrate the difﬁculties concerning a general
polynomialtime algorithm for this problem by means of negative results that demonstrate
why a number of approaches towards such an algorithm are unlikely to be successful.
Actions (login required)

Record administration  authorised staff only 