Christian Kroer

Large-Scale Sequential Imperfect-Information Game Solving: Theoretical Foundations and Practical Algorithms with Guarantees Degree Type: Ph.D. in Computer Science
Advisor(s): Tuomas Sandholm
Graduated: December 2018

Abstract:

Game-theoretic solution concepts provide a sound notion of rational behavior in multiagent settings. To operationalize them, they have to be accompanied by techniques to compute equilibria. We study the computation of equilibria for extensive- form games, a broad game class that can model sequential interaction, imperfect in- formation, 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 establish 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 in the case of algorithm-specific guarantees, 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 the state-of-the-art in convergence rate for iterative methods for computing a Nash equilibrium. In particular, we obtain 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 real-world games we show that our methods lead to a convergence rate that beats all but the fastest practical method. We extend our smoothing approach to the computation of approximate Nash equilibrium refinements as well.

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 the computational complexity of the problem.

Thesis Committee:
Tuomas Sandholm (Chair)
Geoffrey J. Gordon
Fatma Kılınc ̧-Karzan
Vince Conitzer, Duke University
Yurii Nesterov (Universite ́ catholique de Louvain)

Srinivasan Seshan, Head, Computer Science Department
Andrew W. Moore, Dean, School of Computer Science

Keywords:
equilibrium finding, extensive-form games, sequential games, imperfect-information games, Nash equilibrium, abstraction, convex optimization, first-order methods, limited lookahead