Carnegie Mellon University
Browse

Game-Theoretic Decision Making in Imperfect-Information Games

Download (2.71 MB)
thesis
posted on 2023-06-08, 20:49 authored by Gabriele Farina

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 imperfectinformation 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 OT (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 tremblinghand 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. 

History

Date

2023-05-14

Degree Type

  • Dissertation

Department

  • Computer Science

Degree Name

  • Doctor of Philosophy (PhD)

Advisor(s)

Tuomas Sandholm

Usage metrics

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC