Title: Computing Constrained Approximate Equilibria in Polymatrix Games,
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.