On Sparse Discretization for Graphical Games

Abstract

Graphical games are one of the earliest examples of the impact that the general field of graphical models have had in other areas, and in this particular case, in classical mathematical models in game theory. Graphical multi-hypermatrix games, a concept formally introduced in this research note, generalize graphical games while allowing the possibility of further space savings in model representation to that of standard graphical games. The main focus of this research note is discretization schemes for computing approximate Nash equilibria, with emphasis on graphical games, but also briefly touching on normal-form and polymatrix games. The main technical contribution is a theorem that establishes sufficient conditions for a discretization of the players’ space of mixed strategies to contain an approximate Nash equilibrium. The result is actually stronger because every exact Nash equilibrium has a nearby approximate Nash equilibrium on the grid induced by the discretization. The sufficient conditions are weaker than those of previous results. In particular, a uniform discretization of size linear in the inverse of the approximation error and in the natural game-representation parameters suffices. The theorem holds for a generalization of graphical games, introduced here. The result has already been useful in the design and analysis of tractable algorithms for graphical games with parametric payoff functions and certain game-graph structures. For standard graphical games, under natural conditions, the discretization is logarithmic in the game-representation size, a substantial improvement over the linear dependency previously required. Combining the improved discretization result with old results on constraint networks in AI simplifies the derivation and analysis of algorithms for computing approximate Nash equilibria in graphical games.