Tight Inapproximability for Graphical Games
Argyrios Deligkas, John Fearnley, Alexandros Hollender, Themistoklis Melissourgos
Abstract
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 that computing an ε-NE is PPAD-complete for any constant ε smaller than 1/2, while a very simple algorithm (namely, letting all players mix uniformly between their two actions) yields a 1/2-NE. On the other hand, we show that computing an ε-WSNE is PPAD-complete for any constant ε smaller than 1, while a 1-WSNE is trivial to achieve, because any strategy profile is a 1-WSNE. All of our lower bounds immediately also apply to graphical games with more than two actions per player.
BibTeX
@article{Deligkas_Fearnley_Hollender_Melissourgos_2023, title={Tight Inapproximability for Graphical Games}, volume={37}, url={https://ojs.aaai.org/index.php/AAAI/article/view/25695}, DOI={10.1609/aaai.v37i5.25695}, abstractNote={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 that computing an ε-NE is PPAD-complete for any constant ε smaller than 1/2, while a very simple algorithm (namely, letting all players mix uniformly between their two actions) yields a 1/2-NE. On the other hand, we show that computing an ε-WSNE is PPAD-complete for any constant ε smaller than 1, while a 1-WSNE is trivial to achieve, because any strategy profile is a 1-WSNE. All of our lower bounds immediately also apply to graphical games with more than two actions per player.}, number={5}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Deligkas, Argyrios and Fearnley, John and Hollender, Alexandros and Melissourgos, Themistoklis}, year={2023}, month={Jun.}, pages={5600-5607} }