Title: How Strong a Notion of Rationality Can We Learn Efficiently in Multi-Agent Settings?

Speaker: Gabriele Farina, Assistant Professor of Computer Science at MIT

Abstract: A central question in multi-agent learning is: how strong a notion of rational behavior can be guaranteed through efficient no-regret learning? Classical results show that minimizing regret leads to coarse correlated equilibria, and enriching the class of allowed deviations yields progressively stronger equilibrium concepts. But how far can this hierarchy be pushed while retaining efficient algorithms in general convex and extensive-form games?

In this talk, I present recent results that characterize the strongest notions of rationality that can be efficiently learned in this broad setting. We show that linear and low-degree polynomial correlated equilibria—strictly stronger than coarse correlated equilibria and natural relaxations of correlated equilibria—can be computed and learned efficiently even in general convex and extensive-form games.

En route to the result, we will introduce new algorithmic tools with broader applicability. First, the natural deviation sets underlying stronger notions of regret do not admit efficient separation or optimization oracles. To address this, we introduce a new algorithmic primitive, semiseparation, which enables regret minimization over convex sets that lack classical separation oracles. Second, our analysis leverages a fast computational version of von Neumann’s minimax theorem, yielding convergence rates that scale logarithmically in the desired accuracy. This tool has further applications, including to variational inequalities, fixed-point computation, and online multicalibration.
Based on joint work that has appeared at STOC’25 and ACM EC’25.

Speaker Bio: Gabriele Farina is an Assistant Professor in the Department of Electrical Engineering and Computer Science at MIT, with affiliations in LIDS and the Operations Research Center. His research combines techniques and notions of strategic behavior from game theory together with modern tools from machine learning, optimization, and statistics to construct state-of-the-art methods for learning and decision-making in multi-agent systems. He received his Ph.D. in Computer Science from Carnegie Mellon University, and his work has been recognized with several awards, including a Best Paper Award at NeurIPS'20 and an Outstanding Paper Honorable Mention at ICLR'23. His dissertation received the ACM SIGecom Doctoral Dissertation Award and one of the two ACM Dissertation Award Honorable Mentions, among others. He is an AI2050 Early Career Fellow, and the recipient of an NSF CAREER award.

There will be refreshments before the talk at 2:15pm outside of LL2.224