Casetti, Marta
(2016)
Complexity of the gale string problem for equilibrium computation in games.
MPhil thesis, The London School of Economics and Political Science (LSE).
Abstract
This thesis presents a report on original research, extending a result published as joint work with Merschen and von Stengel in Electronic Notes in Discrete Mathematics [4]. We present a polynomial time algorithm for two problems on labeled Gale strings, a combinatorial structure introduced by Gale [11] that can be used in the representation of a particular class of games.
These games were used by Savani and von Stengel [25] as an example of exponential running time for the classical LemkeHowson algorithm to find a Nash equilibrium of a bimatrix game [16]. It was therefore conjectured that solving these games was a complete problem in the class PPAD (Polynomial Parity Argument, Directed version, see Papadimitriou [24]). In turn, a major motivation for the definition of PPAD was the study of complementary pivoting methods, such as the LemkeHowson algorithm.
Our result, unexpectedly, sets apart this class of games as a case where a Nash equilibrium can be found in polynomial time. Since Daskalakis, Goldberg and Papaditrimiou [6] and Chen and Deng [5] proved that finding a Nash equilibrium in general normalform games is PPADcomplete, we have a special class of games, unless PPAD = P.
Our proof exploits two results. As seen in Savani and von Stengel [25] [26], we represent the Nash equilibria of these special games as Gale strings. We then give a graph where the perfect matchings correspond to Nash equilibria via Gale strings, and we exploit Edmonds’ polynomialtime algorithm for a
perfect matching in a graph [7]. The proof given in Casetti, Merschen and von Stengel [4] covered only the case of evendimensional Gale strings; here we extend the result to the general case.
Merschen [19] and V´egh and von Stengel [28] expanded on our ideas, proving further results on the index of Nash equilibria (see Shapley [27]) in the framework of “oiks” introduced by Edmonds [8] and Edmonds and Sanit`a [9].
Actions (login required)

Record administration  authorised staff only 