Gabriele Farina

Game-Theoretic Decision Making in Imperfect-Information Games: Learning Dynamics, Equilibrium Computation, and Complexity Degree Type: Ph.D. in Computer Science
Advisor(s): Tuomas Sandholm
Graduated: May 2023

Abstract:

Designing machines that can reason strategically and make optimal decisions even in the presence of imperfect information and adversarial behavior is a fundamental goal of artificial intelligence. Our understanding of game-theoretic decision making is fairly advanced in normal-form games, strategic interactions in which all players act once and simultaneously, selecting (possibly randomizing their choice) an action from a pre-determined finite set of possibilities. In contrast, this dissertation focuses on the more realistic imperfect-information extensive-form games, tree-form decision-making problems in which decision makers can face multiple decisions interleaved with observations about the way previous decisions affected the (partially hidden and possibly adversarial) multiagent environment.

This dissertation seeks to close some recognized open problems in this area, and provide solid theoretical and algorithmic foundations for strategic, game-theoretic decision-making in imperfect-information extensive-form games. We highlight the following contributions.

• We close the long-standing open question of whether extensive-form correlated equilibria can arise from efficient, uncoupled learning dynamics, establishing unconditional positive results.
• We settle the complexity of computing extensive-form perfect equilibria in two-player games, a recognized open problem, showing it matches that of Nash equilibrium.
• We establish learning dynamics with state-of-the-art O_T (log T/T) convergence to coarse correlated equilibrium, improving as a corollary known bounds for normal-form games.
• We uncover a kernelized version of the classic multiplicative weights update algorithm. This algorithm leads to learning dynamics for coarse correlated equilibria with theoretical state-of-the-art dependence on the size of the imperfect-information game.
• We give fundamental results about the geometry of correlated strategies, identifying new important classes of games where optimal (e.g., welfare-maximizing) correlated solution concepts can be computed in polynomial time, yielding positive complexity results for extensive-form correlation.
• We give the first learning algorithm with guaranteed convergence to welfare-maximizing correlated solution concepts, and show their state-of-the-art empirical performance.
• We give state-of-the-art algorithms that enable, for the first time, finding exact trembling-hand refinements of Nash equilibrium in large games with up to half a billion terminal states.
• We study the problem of computing optimal team strategies in zero-sum adversarial team games, and give state-of-the-art algorithms and positive complexity results for that setting.
• We give learning dynamics that can incorporate a model of the player to produce strong, human-compatible strategies. These dynamics were a key component in training artificial intelligence for the game of Diplomacy, a 7-player game involving both cooperation and competition with humans.

Thesis Committee:
Tuomas Sandholm (Chair)
Vincent Conitzer
Geoffrey Gordon
J. Zico Kolter
Avrim Blum (Toyota Technological Institute at Chicago)
Constantinos Daskalakis (Massachusetts Institute of Technology)

Srinivasan Seshan, Head, Computer Science Department
Martial Hebert, Dean, School of Computer Science

Keywords:
Computational game theory, extensive-form games, learning dynamics, equilibrium computation