Prof. Yakov Babichenko 

Technion

ירצה על

Will lecture on

Settling the complexity of Nash equilibrium in congestion games.

Joint work with Aviad Rubinstein.

הרצאה פרונטלית – נא להגיע פיזית להרצאה:

 בניין 216 חדר 201 

Building 216  Room 201

Abstract

We consider

(i) the problem of finding a (possibly mixed) Nash equilibrium in congestion games, and 
(ii) the problem of finding an (exponential precision) fixed point of the gradient descent dynamics of a smooth function f:[0,1]^n -> R 
We prove that these problems are equivalent.
Our result holds for various explicit descriptions of f, ranging from (almost general) arithmetic circuits, to degree-5 polynomials.
By a very recent result of [Fearnley, Goldberg, Hollender, Savani '21] this implies that these problems are PPAD\cap\PLS-complete. 
As a corollary, we also obtain the following equivalence of complexity classes:
CCLS = PPAD \cap PLS.

Bio

Yakov Babichenko is an associate professor at the Technion whose major research interest is game theory. Selected awards: 
- Krill Prize for excellence in scientific research (Wolf foundation) 2018.
- The Prize in Game Theory and Computer Science in Honour of Ehud Kalai 2020.