Computer Science Thesis Proposal

Monday, January 23, 2017 -
10:30am to 11:30am


Traffic21 Classroom Gates Hillman Center



For More Information, Contact:

Game-theoretic equilibrium concepts provide a sound definition of how rational agents should act 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 information, and outcome uncertainty. Practical equilibrium computation in extensive-form games relies on two complementary methods: abstraction methods and sparse iterative equilibrium-finding algorithms. These methods are necessary in order to handle the size of many real-world games. We present new algorithmic and structural results for both parts of extensive-form game solving. We introduce state-of-the-art theoretical guarantees on the performance of our algorithms, and first-of-their-kind guarantees on the solution quality of abstractions for large games. 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 the formulation of an extensive-form two-player zero-sum Nash equilibrium as a bilinear saddle-point problem. This allows us to leverage methods from the convex optimization literature. 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 than bounds for prior smoothing methods. This leads to the state-of-the-art in convergence rate for sparse iterative methods for computing a Nash equilibrium. Our results can also be viewed more generally as strong convexity results for a class of convex polytopes called treeplexes. These results could be of independent interest in other sequential decision-making settings. Finally, we develop new solution concepts and associated algorithmic results for games where opponents have limited lookahead.Thesis Committee: Tuomas Sandholm (Chair)Geoffrey J. GordonFatma Kılınc-KarzanVince Conitzer (Duke University) Yurii Nesterov (Université Catholique de Louvain) Copy of Thesis Summary


Thesis Proposal