Computer Science/Discrete Mathematics Seminar II | |

Topic: | Settling the complexity of computing approximate two-player Nash equilibria |

Speaker: | Aviad Rubinstein |

Affiliation: | University of California, Berkeley |

Date: | Tuesday, November 1 |

Time/Room: | 10:30am - 12:30pm/West Building Lecture Hall |

Video Link: | https://video.ias.edu/csdm/2016/1101-AviadRubinstein |

We prove that there exists a constant $\epsilon > 0$ such that, assuming the Exponential Time Hypothesis for PPAD, computing an $\epsilon$-approximate Nash equilibrium in a two-player ($n \times n$) game requires quasi-polynomial time, $n^{\log^{1-o(1)}n}$. This matches (up to the $o(1)$ term) the algorithm of Lipton, Markakis, and Mehta [LMM03]. Our proof relies on a variety of techniques from the study of probabilistically checkable proofs (PCP); this is the first time that such ideas are used for a reduction between problems inside PPAD.