Pure-Circuit: Tight Inapproximability within PPAD

7^th December 2022, 11:00 Ashton Lecture Theatre
John Fearnley

Abstract

I will talk about a new technique for showing strong inapproximability results within PPAD based on a new problem called Pure-Circuit. In particular, I will talk about a new hardness result for epsilon approximate well-supported equilibria (WSNE) in polymatrix games which applies for all epsilon < 1/3 and is tight for two-action games, a new hardness result for finding epsilon-WSNEs in graphical games for all epsilon < 1, which is tight for all games, and a new hardness result for finding epsilon approximate Nash equilibria in graphical games for all epsilon < 1/2, which is tight for two-action games.

This is joint work with Argyrios Deligkas (Royal Holloway), Alexandros Hollender (Oxford & EPFL), and Themistoklis Melissourgos (Essex), and is presented in the following papers
- Pure-Circuit: Strong Inapproximability in PPAD, FOCS 2022.
- Tight Inapproximability for Graphical Games, AAAI 2023.