Deligkas, , Fearnley, and Savani, RSJ ORCID: 0000-0003-1262-7831
(2017)
Computing Constrained Approximate Equilibria in Polymatrix Games.
In: Symposium on Algorithmic Game Theory (SAGT).
Text
note.pdf - Author Accepted Manuscript Download (343kB) |
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.
Item Type: | Conference or Workshop Item (Unspecified) |
---|---|
Uncontrolled Keywords: | cs.GT, cs.GT |
Depositing User: | Symplectic Admin |
Date Deposited: | 25 Jul 2017 08:40 |
Last Modified: | 19 Jan 2023 06:58 |
DOI: | 10.1007/978-3-319-66700-3_8 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3008589 |