Fast Iterative Methods for Large-Scale Game-Theoretic Problems and Beyond

Game-theoretic models provide powerful frameworks for reasoning about settings with multiple strategic agents whose interests do not, always align. These models are utilized in the real world in high-stakes settings such as security (cybersecurity, airport security,, etc.), war games, naval strategic planning, markets (e.g. auctions), and recreational games (e.g. poker). Operationalizing these m,odels requires algorithms for computing equilibria. Typically, real-world game models are very large, and thus these algorithms need, to be scalable. Recent results in the AI literature have shown that, given such scalable algorithms, it is possible to approximatel,y solve extremely-large poker games well enough to create AIs that can beat even the best human poker players. However, a comprehens,ive understanding of the best optimization methods for solving these games at scale is largely limited to the setting of determinist,ic algorithms for two-player zero-sum Nash equilibrium computation.This project proposes a new class of algorithms that will attempt, to bridge the gap between the theory and practice of solving large-scale games, as well as develop new more scalable methods for pr,oblems that go beyond the two-player zero-sum case. This will be done by developing new methods along several concurrent directions:,(1)Developing a better theory of how to instantiate first-order methods for solving games, including the design of new distance meas,ures for creating first-order methods that adapt to the geometry and curvature of the problem.(2)Developing an understanding of how,to apply first-order methods and other scalable methods to game-theoretic problems beyond two-player zero-sum games, such as the com,putation of correlated equilibria and solving games where teams compete against each other.(3)An understanding of stochastic first-o,rder methods for solving games, including the interplay between distance measures and variance-reduced gradient estimation.(4)Levera,ging the lessons from large-scale game solving in other domains, such as solving robust Markov decision processes and robust machine,-learning problems.Approved for Public Release