14th Estonian Winter School in Computer Science (EWSCS)
XIV Eesti Arvutiteaduse Talvekool

Palmse, Estonia, March 1-6, 2009

Paul W. Goldberg

Dept. of Computer Science
University of Liverpool
UK

Computational Complexity in Game Theory

Abstract

Game theory studies mathematical models of competitive situations, with the aim of predicting the outcome of interactions amongst multiple agents who do not necessarily cooperate with each other. This gives rise to computational problems of finding the outcome algorithmically. In cases where the problem is apparently computationally hard, this requires different notions of "computational hardness" from NP-hardness. In particular, the complexity class PPAD captures the difficulty of computing a classical Nash equilibrium, and PLS captures the difficulty of solving various kinds of potential games. The course will contain an introduction to these complexity classes, and how they relate to corresponding game theory problems. I will then go over some recent results that obtain weaker solutions in polynomial time. These include, for example, approximate Nash equilibrium, and correlated equilibrium.

Course materials

Valid CSS! Valid XHTML 1.0 Strict Last changed March 11, 2009 10:53 EET by local organizers, ewscs09(at)cs.ioc.ee
EWSCS'09 page: http://cs.ioc.ee/ewscs/2009/