Doctoral Thesis Proposal - Brian Zhang

— 4:30pm

Location:
In Person - Gates Hillman 8102

Speaker:
BRIAN ZHANG, Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://brianhzhang.github.io/

New Solution Concepts, Algorithms, and Applications for Extensive-Form Games: Learning, Correlation, Communication, and Common Knowledge

Computational game theory has led to significant breakthroughs in AI dating back to the start of AI as a discipline. These include the strongest AI agents for both recreational and practical applications. It has been instrumental in enabling superhuman AI from recreational games such as two-player zero-sum games chess, go, and heads-up poker to multiplayer games such as six-player poker and Hanabi, and even in games involving human language such as Diplomacy. It has also empowered a growing range of non-recreational applications, such as trading, machine learning robustness and safety, negotiation, conflict resolution, mechanism design, information design, security, political campaigning, and self-driving cars. 

This thesis pushes the boundary on computational game theory, especially in imperfect-information sequential (extensive-form) games, which are most prevalent in practical applications both in zero-sum games and beyond. We present new theoretical concepts and frameworks, state-of-the-art and often provably optimal algorithms for computing and learning equilibria, and new ways to apply such algorithms to real-world problems, including problems in economics such as mechanism and information design.

The thesis contains four parts.

I)  We develop new solution concepts and state-of-the-art complexity results for adversarial team games. Among other results, we compute exact solutions to several variants of the popular game The Resistance: Avalon with up to six players.

II)  We develop an algorithmic framework for generalized mechanism design that covers sequential mechanism design, sequential information design, optimal correlated equilibria and more for the first time, and reduces them to zero-sum games. This enables computation using any zero-sum game solving technique, including deep reinforcement learning.

III)  We develop the fastest learning algorithms for minimizing regret against linear and low-degree deviations, which are the tightest solution concepts known to be efficiently learnable in games.

IV)  We develop new techniques for subgame solving that work even when the common-knowledge set is too large to work with, and use these techniques to build the first strong bot—and, to our knowledge, currently the best bot—for the game of dark chess. 

Thesis Committee

Tuomas Sandholm (Chair)
Vincent Conitzer
Zico Kolter
Kevin Leyton-Brown (University of British Columbia)

Additional Information

Event Website:
https://csd.cmu.edu/calendar/doctoral-thesis-proposal-brian-zhang