Settling the Complexity of Nash Equilibrium in Congestion Games

Speaker
Yakov Babichenko
Date
15/12/2020 - 13:00 - 11:30Add To Calendar 2020-12-15 11:30:00 2020-12-15 13:00:00 Settling the Complexity of Nash Equilibrium in Congestion Games We consider (i) the problem of finding a (possibly mixed) Nash equilibrium in congestion game, and (ii) the problem of finding an (exponential precision) fixed point of the gradient descent dynamics of a smooth function over the cube. We prove that these problems are equivalent. Our result holds for various explicit descriptions of the function, ranging from (almost general) arithmetic  circuits, to degree-5 polynomials. By a very recent result of [Fearnley, Goldberg, Hollender, Savani 2020], this implies that these problems are PPAD∩PLS-complete. As a corollary, we also obtain the following equivalence of complexity classes: CCLS=PPAD∩PLS. Remark: The talk will not assume prior knowledge of the complexity classes (PPAD, PLS, CCLS). Joint work with Aviad Rubinstein To view the seminar recording, click here     Zoom https://us02web.zoom.us/j/82536086839 אוניברסיטת בר-אילן - Department of Economics Economics.Dept@mail.biu.ac.il Asia/Jerusalem public
Place
Zoom https://us02web.zoom.us/j/82536086839
Affiliation
Technion - Israel Institute of Technology
Abstract

We consider

(i) the problem of finding a (possibly mixed) Nash equilibrium in congestion game, and

(ii) the problem of finding an (exponential precision) fixed point of the gradient descent dynamics of a smooth function over the cube. We prove that these problems are equivalent.

Our result holds for various explicit descriptions of the function, ranging from (almost general) arithmetic  circuits, to degree-5 polynomials. By a very recent result of [Fearnley, Goldberg, Hollender, Savani 2020], this implies that these problems are PPAD∩PLS-complete. As a corollary, we also obtain the following equivalence of complexity classes: CCLS=PPAD∩PLS.

Remark: The talk will not assume prior knowledge of the complexity classes (PPAD, PLS, CCLS).

Joint work with Aviad Rubinstein

To view the seminar recording, click here

 

 

Last Updated Date : 22/12/2020