### 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

- P. Goldberg. Game theory and computational complexity. Lecture slides for EWSCS 2009. 2009. [pdf]
- V. Conitzer, T. Sandholm. New complexity results about Nash
equilibria.
*Games and Economic Behavior*, v. 63, n. 2, pp. 621-641, 2008. - Y. Shoham. Computer science and game theory.
*Commun. of ACM*, v. 51, n. 8, pp. 74-79, 2008. - C. Daskalakis, P. W. Goldberg, C. H. Papadimitriou. The complexity
of computing a Nash equilibrium.
*Commun. of ACM*, v. 52, n. 2, pp. 89-97, 2009.

Last changed **
March 11, 2009 10:53 EET**
by
local organizers, ewscs09(at)cs.ioc.ee

EWSCS'09 page:
//cs.ioc.ee/ewscs/2009/