We provide the first fully polynomial time approximation scheme (FPTAS) for
computing an approximate mixed-strategy Nash equilibrium in tree-structured
graphical multi-hypermatrix games (GMhGs). GMhGs are generalizations of
normal-form games, graphical games, graphical polymatrix games, and
hypergraphical games. Computing an exact mixed-strategy Nash equilibria in
graphical polymatrix games is PPAD-complete and thus generally believed to be
intractable. In contrast, to the best of our knowledge, we are the first to
establish an FPTAS for tree polymatrix games as well as tree graphical games
when the number of actions is bounded by a constant. As a corollary, we give a
quasi-polynomial time approximation scheme (quasi-PTAS) when the number of
actions is bounded by the logarithm of the number of players.

该文提供了第一个完全多项式时间的近似混合策略纳什均衡算法，用于计算树形图多超矩阵博弈中的纳什均衡，并证明当操作数量受到限制时，该算法适用于树状多项式博弈和树形图博弈，并引出了拟多项式时间的近似算法。