Complexity of the gale string problem for equilibrium computation in games

Casetti, Marta (2016) Complexity of the gale string problem for equilibrium computation in games. MPhil thesis, London School of Economics and Political Science.

Preview

Text - Submitted Version Download (1MB) | Preview

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 Lemke-Howson 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 Lemke-Howson 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 normal-form games is PPAD-complete, 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’ polynomial-time algorithm for a perfect matching in a graph [7]. The proof given in Casetti, Merschen and von Stengel [4] covered only the case of even-dimensional 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].

Item Type:	Thesis (MPhil)
Additional Information:	© 2016 Marta Maria Casetti
Library of Congress subject classification:	Q Science > QA Mathematics
Sets:	Departments > Mathematics
Supervisor:	Von Stengel, Bernhard
URI:	http://etheses.lse.ac.uk/id/eprint/3250

Actions (login required)

Record administration - authorised staff only