The Computational Complexity of GameTheoretic Solutions
Rahul Savani (University of Liverpool).
Course Summary 
About the lecturer 
Location and schedule
This lecture series will focus on several prominent complexity classes, PPAD, PLS, CLS and UEOPL, that have been introduced and used to classify the complexity of finding gametheoretic solutions. We will first explore how PPAD and PLS exactly capture the complexity of two such problems: finding a mixed Nash equilibrium in a bimatrix game is PPADcomplete and finding a pure Nash equilibrium in a congestion game is PLScomplete. We will then introduce CLS and discuss two relatively recent results about it: We will show that CLS is equal to PPAD intersection PLS, and discuss how the problem of finding a mixed Nash equilibrium in a congestion game is CLScomplete. Lastly, we will explore the complexity class UEOPL and related open problems. UEOPL sits inside CLS and is presumed distinct from it; it contains problems that admit unique solutions, such as solving Simple Stochastic Games, finding a fixed point of a Contraction Map, and solving a Pmatrix Linear Complementarity problem.
About the lecturer:Rahul Savani is a Professor of Computer Science at the University of Liverpool. He has worked extensively on algorithms, complexity, and learning for gametheoretic problems. He is currently seconded to the Alan Turing Institute where he leads a project within the new Game Theory and Collective Decision Making Pillar.
Materials: Slides HomeworkLocation and schedule:


