John Fearnley

2 accepted papers

2023

Tight Inapproximability for Graphical Games

Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos

AAAI 2023technical

We provide a complete characterization for the computational complexity of finding approximate equilibria in two-action graphical games. We consider the two most well-studied approximation notions: ε-Nash equilibria (ε-NE) and ε-well-supported Nash equilibria (ε-WSNE), where ε is in [0,1]. We prove…

Cited by 7 Source ↗PDF ↗Scholar ↗

2022

Pizza Sharing Is PPA-Hard

Argyrios Deligkas, John Fearnley, Themistoklis Melissourgos

AAAI 2022technical

We study the computational complexity of computing solutions for the straight-cut and square-cut pizza sharing problems. We show that finding an approximate solution is PPA-hard for the straight-cut problem, and PPA-complete for the square-cut problem, while finding an exact solution for the squ…

Cited by 10 Source ↗PDF ↗Scholar ↗