21 March 2022, Monday. 3PM. London Time. Online over Zoom
Title: The Complexity of Gradient Descent
Speaker: Rahul Savani, University of Liverpool
Abstract PPAD and PLS are successful classes that each capture the complexity of important game-theoretic 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. Many important problems, such as solving a Simple Stochastic Game or finding a mixed Nash equilibrium of a congestion game,lie in both classes. However, it was strongly believed that their intersection does not have natural complete problems. We show that it does: any problem that lies in both classes can be reduced in polynomial time to the problem of finding a stationary point of a function. Our result has been used to show that computing a mixed equilibrium of a congestion game is also complete for theintersection of PPAD and PLS. The talk will not assume a technical background in the area and will be aimed at a general audience.This is joint work with John Fearnley, Paul Goldberg, and Alexandros Hollender.
Bio Rahul Savani is a Professor of Economics and Computation at the University of Liverpool. He has worked extensively on the computation of equilibria in game-theoretic models. The paper that he will present won a Best Paper Award at STOC’21.
Zoom link https://mdx-ac-uk.zoom.us/j/6684138396?pwd=d0I5V2JlTHVKbjlKWXZ2MW1RZ0ozQT09
Meeting ID: 668 413 8396
Passcode: mdx