EECS Special Seminar: Gabriele Farina "Scalable equilibrium computation and learning dynamics for multi-step imperfect-information games"

Speaker: Gabriele Farina , Carnegie Mellon University (CMU)

Date: Wednesday, March 30, 2022

Time: 2:00 PM to 3:00 PM Note: all times are in the Eastern Time Zone

Public: Yes

Location: Grier A

Event Type:

Room Description:

Host: Costis Daskalakis, EECS & CSAIL

Contact: Fern D Keniston, fern@csail.mit.edu

Relevant URL:

Speaker URL: None

Speaker Photo:
Gabriele farina headshot

Reminders to: fern@csail.mit.edu

Reminder Subject: TALK: EECS Special Seminar: 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.

Research Areas:

Impact Areas:

This event is not part of a series.

Created by Fern D Keniston Email at Tuesday, March 29, 2022 at 9:39 AM.