The Computational Complexity of Game-Theoretic 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 game-theoretic 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 PPAD-complete and finding a pure Nash equilibrium in a congestion game is PLS-complete. 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 CLS-complete. 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 P-matrix 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 game-theoretic 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:
|
|
|
||||||||||||||||