Computing constrained approximate equilibria in polymatrix games

DOI10.1007/978-3-319-66700-3_8zbMATH Open1403.91017arXiv1705.02266OpenAlexW2612502501MaRDI QIDQ681849FDOQ681849

Authors: Argyrios Deligkas, John Fearnley, Rahul Savani 

Publication date: 13 February 2018

Abstract: This paper is about computing constrained approximate Nash equilibria in polymatrix games, which are succinctly represented many-player games defined by an interaction graph between the players. In a recent breakthrough, Rubinstein showed that there exists a small constant $epsilon$, such that it is PPAD-complete to find an (unconstrained) $epsilon$-Nash equilibrium of a polymatrix game. In the first part of the paper, we show that is NP-hard to decide if a polymatrix game has a constrained approximate equilibrium for 9 natural constraints and any non-trivial approximation guarantee. These results hold even for planar bipartite polymatrix games with degree 3 and at most 7 strategies per player, and all non-trivial approximation guarantees. These results stand in contrast to similar results for bimatrix games, which obviously need a non-constant number of actions, and which rely on stronger complexity-theoretic conjectures such as the exponential time hypothesis. In the second part, we provide a deterministic QPTAS for interaction graphs with bounded treewidth and with logarithmically many actions per player that can compute constrained approximate equilibria for a wide family of constraints that cover many of the constraints dealt with in the first part.

Full work available at URL: https://arxiv.org/abs/1705.02266

Recommendations

• Approximating Nash equilibria in tree polymatrix games
• Computing approximate Nash equilibria in polymatrix games
• Computing approximate Nash equilibria in polymatrix games
• Inapproximability of Nash equilibrium
• Inapproximability of Nash equilibrium

zbMATH Keywords

polymatrix gamesconstrained approximate Nash equilibria

Mathematics Subject Classification ID

Noncooperative games (91A10) (n)-person games, (n>2) (91A06)

Cited In (10)

• Approximating Nash equilibria in tree polymatrix games
• Computing approximate Nash equilibria in polymatrix games
• Computing approximate Nash equilibria in polymatrix games
• Inapproximability results for constrained approximate Nash equilibria
• Computing Nash equilibria by iterated polymatrix approximation
• Approximating the existential theory of the reals
• Polynomial-time computation of exact correlated equilibrium in compact games
• The polymatrix gap conjecture
• Limited memory solution of bound constrained convex quadratic problems arising in video games
• Approximating the existential theory of the reals

This page was built for publication: Computing constrained approximate equilibria in polymatrix games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q681849)