CDS Seminar: The Best Offense is a Good Defense: a fast, constructive minimax theorem
Speaker: Gabriele Farina (MIT)
Location:
60 Fifth Avenue, Room 150
Date:
Friday, November 6, 2026
Abstract: Von Neumann’s minimax theorem and its generalizations assert that defense implies offense: if you can guarantee value v whenever you get to see your opponent’s (randomized) strategy before responding, then you can guarantee v without seeing it, by committing to a single strategy in advance. The theorem is a fundamental (and almost hard to believe) existence result in economics, but it promises a strategy without saying how to find one. I will describe efficient constructive versions of the theorem, and propose one exponentially faster than the classical route through no-regret learning. For equilibria, it gives efficient algorithms for broad relaxations of correlated equilibrium beyond normal-form games. For forecasting, it leads to a faster algorithm for calibration in high-dimensional settings. For optimization, it yields the first polynomial-time algorithm for ℓ_p contraction fixed points when p is an even integer, and suggests a tractable solution concept for variational inequalities. For performative prediction, where a model is retrained on data with its own predictions shaped, it shows that a randomized stable (i.e., self-consistent) model always exists and that it can be found with few deployments.
Based on joint work with Charilaos Pipis, Ioannis Anagnostides, Brian Hu Zhang, Juan Carlos Perdomo, and others.
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.