Gabriele Farina – Scalable equilibrium computation and learning dynamics for multi-step imperfect-information games

Abstract: 
Computational game theory studies optimal decision making in multi-agent interactions (“games”) under imperfect information and strategic behavior. While much work has focused on solving decision-making problems in which all agents act once and simultaneously, I will focus on the more realistic case in which each agent faces a tree-form decision problem with potentially multiple acting points and partial observability (“extensive-form games”). 

In the first part of the talk, I will give new learning algorithms for agents in extensive-form games. Specifically, I will introduce the current theoretical and practical state-of-the-art algorithms for Nash equilibrium in large two-player zero-sum games. Furthermore, I will discuss the first efficient uncoupled no-regret learning dynamics for extensive-form correlated equilibrium in games with any number of players, closing a long-standing open question. 

In the second part of the talk, I will move away from uncoupled learning dynamics to focus on settings in which the agents can explicitly correlate their strategies. I will give the first positive and parameterized complexity results for the problems of learning team-correlated equilibria and computing social-welfare-maximizing correlated equilibria in games with any number of players, as well as the theoretical and practical state-of-the-art algorithms for both problems. 

Finally, in the third part of the talk I will relax the assumption of perfect rationality of the agents, and study the computation of classic subsets of Nash equilibria, called “trembling-hand refinements”, which are robust to mistakes of the players. I will establish positive complexity results in two-player games, and give state-of-the-art algorithms that, for the first time, enable the computation of exact trembling-hand refinements at scale.

Bio: 
Gabriele Farina is a Ph.D. candidate in the Computer Science Department at Carnegie Mellon University. His primary research interests focus on learning and optimization methods for sequential decision making and convex-concave saddle point problems, with applications to equilibrium finding in games. In the past, he has also worked on optimization algorithms for kidney exchange and ad allocation. He is a recipient of a NeurIPS best paper award, and is a Facebook Fellow in the area of economics and computer science.

Details

• Date: Wednesday, March 30
• Time: 2:00 pm - 3:00 pm
• Category: Special Seminar
• Location: Grier A (34-401A)

Host

• Costis Daskalakis
• Email: fern@csail.mit.edu