Computer Science Thesis Oral
- Gates Hillman Centers
- Traffic21 Classroom 6501
- CHRISTIAN KROER
- Ph.D. Student
- Computer Science Department
- Carnegie Mellon University
Large-Scale Sequential Imperfect-Information Game Solving: Theoretical Foundations and Practical Algorithms with Guarantees
Game-theoretic equilibrium concepts provide a sound definition of how rational agents should act inmultiagent settings. To operationalize them, they have to be accompanied by techniques to computeequilibria. We study the computation of equilibria for extensive-form games, a broad game class that can model sequential interaction, imperfect information, and outcome uncertainty. Equilibrium computation in large-scale extensive-form games typically relies on two complementary methods: abstraction and iterative equilibrium-finding algorithms. We present new algorithmic and structural results for both methods.
For abstraction, we develop new theoretical guarantees on the solution quality of equilibria computed in abstractions. We develop new results for several types of games and abstractions: discrete and continuous extensive-form games, and perfect and imperfect-recall abstractions. For all settings, our results are the first algorithm-agnostic solution-quality guarantees. Additionally, even compared to algorithm-specific results, our approach leads to exponentially stronger bounds than prior results, and extend to more general games and abstractions. For equilibrium computation, we focus on two-player zero-sum Nash equilibrium computation via convex optimization. We consider a smoothing method based on a dilated entropy function. We prove bounds on the strong convexity and polytope diameter associated with this function that are significantly stronger, and more general, than bounds for prior smoothing methods. This leads to thestate-of-the-art in convergence rate for iterative methods for computing a Nash equilibrium. In particular, we develop the first convergence rate that generalizes the well-known logarithmic dependence on dimension in the matrix-game setting. In GPU-based experiments on large-scale realworld games we show that our methods lead to a convergence rate that beats all but the best practical algorithm. We also extend this smoothing approach to the computation of approximate Nash equilibrium refinements.
Finally, we investigate a number of new extensive-form game models. We develop new solution concepts and associated algorithmic results for games where opponents have limited lookahead. We then initiate the study of robust Stackelberg extensive-form games. We develop algorithms for computing solutions and classify computational complexity.
Tuomas Sandholm (Chair)
Geoffrey J. Gordon
Vince Conitzer (Duke University)
Yurii Nesterov (Université Catholique de Louvain)