==================================================

Sunday March 8, 11:30-13:00 Feldman building, Middle floor, Hall 130

On the complexity of approximate Nash equilibrium in two-player games

Speaker: Yakov Babichenko, Technion

==================================================

The question whether there exists a polynomial algorithm for computing an approximate Nash equilibrium in two player games, is one of the major open questions in equilibrium complexity. A quasi-polynomial algorithm (n^{log n}) is known to exist [Lipton, Markakis, Mehta 2003].

The Probabilistically-Chackable-Proof (PCP) Thoerem is one of the central Theorems in complexity theory. The Theorem is stated on the complexity class NP.

We conjecture an analog of the PCP Theorem for the PPAD complexity class. Under this conjecture and the exponential time hypothesis for the PPAD class (i.e., the hypothesis that PPAD-hard problems require exponential time) we prove that quasi-polynomial algorithm is the best possible algorithm of computing an approximate Nash equilibrium in two-player games; I.e., polynomial algorithm for computing an approximate Nash equilibrium does not exist.

(Joint work with Christos Papadimitriou and Aviad Rubinstein)

Seminar web site: https://compeconseminar.wordpress.com/schedul/

Advertisements

## Leave a Reply