דלג לתוכן (מקש קיצור 's')
Logo of Technion
Logo of CS Department
אירועים

אירועים

Theory Seminar: Settling the Complexity of Nash equilibrium in Congestion Games
event speaker icon
יעקב בביצ'נקו
event date icon
יום רביעי, 10.11.2021, 12:30
event location icon
טאוב 201
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. Joint work with Aviad Rubinstein.
[בחזרה לאינדקס האירועים]