Fast Payoff Matrix Sparsification Techniques for Structured Extensive-Form Games

The practical scalability of many optimization algorithms for large extensive-form games is often limited by the games' huge payoff matrices. To ameliorate the issue, Zhang and Sandholm (2020) recently proposed a sparsification technique that factorizes the payoff matrix A into a sparser object A = Â + U V , where the total combined number of nonzeros of Â, U , and V is significantly smaller. Such a factorization can be used in place of the original payoff matrix in many optimization algorithm, such as interior-point and second-order methods, thus increasing the size of games that can be handled. Their technique significantly sparsifies poker (end)games, standard benchmarks used in computational game theory, AI, and more broadly. We show that the existence of extremely sparse factorizations in poker games can be tied to their particular Kronecker-product structure. We clarify how such structure arises and introduce the connection between that structure and sparsification. By leveraging such structure, we give two ways of computing strong sparsifications of poker games (as well as any other game with a similar structure) that are i) orders of magnitude faster to compute, ii) more numerically stable, and iii) produce a dramatically smaller number of nonzeros than the prior technique. Our techniques enable-for the first time-effective computation of high-precision Nash equilibria and strategies subject to constraints on the amount of allowed randomization. Furthermore, they significantly speed up parallel first-order game-solving algorithms; we show state-of-the-art speed on a GPU. Introduction Certain important quantities of interest in computational game theory can be expressed as the solution to a linear program (LP) and therefore-in principle-solved for by any algorithm for linear optimization. The practice is more nuanced. The size of the LP is usually dominated by the payoff matrix of the game, that is, the matrix of payoffs for each of the possible terminal states of the game. Correspondingly, in large extensive-form games, most out-of-the-box algorithms for linear programming-such as interior point methods and the simplex method-are unviable.