2022/09/30 by Argyrios Deligkas, Deligkas, Argyrios, John Fearnley +5
Decision Sciences · Economics, Econometrics and Finance · #Game Theory and Applications #Economic theories and models #Game Theory and Voting Systems
paper · pdf · doi:10.48550/arxiv.2209.15151
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 ε ∈ [0,1]. We prove that computing an ε-NE is PPAD-complete for any constant ε < 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 ε < 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.