We provide the first FPTAS for computing an approximate mixed-strategy Nash Equilibrium (MSNE) in graphical multi-hypermatrix games, which are generalizations of normal-form games, graphical games (GGs), graphical polymatrix games, and hypergraphical games. The computational complexity of graphical polymatrix games, or polymatrix GGs for short, has been of great interest in the computational/algorithmic game theory community. The exact-MSNE formulation of the problem for polymatrix GGs is PPAD-compete, thus generally believed intractable, even for binary-action games with tree graphs. In contrast, to the best of our knowledge, we are the first to establish a corollary FPTAS (or quasi-PTAS) for tree polymatrix and normal-form GGs with the number of actions bounded by a constant (or a logarithm of the number of players, respectively).
['Luis E. Ortiz', 'Mohammad Tanvir Irfan']
FPTAS for Mixed-Strategy Nash Equilibria in Tree Graphical Games and Their Generalizations