ACM EC’26 tutorial

Learning and Computation of \(\Phi\)-Equilibria

No-regret learning in games sits at the intersection of game theory and online learning. This tutorial focuses on \(\Phi\)-regret and its connection to \(\Phi\)-equilibria, from the Gordon-Greenwald-Marks reduction to newer tools such as semi-separation, expected fixed points, multicalibration, and TreeSwap-style reductions.

Ioannis AnagnostidesCarnegie Mellon Universitywebpage

Gabriele FarinaMassachusetts Institute of Technology webpage

Brian Hu ZhangMassachusetts Institute of Technologywebpage

Start Reading GitHub Join Zoom

Tutorial Notes

  1. 1IntroductionRegret, equilibrium notions, \(\Phi\)-regret, and the Gordon-Greenwald-Marks perspective.
  2. 2Beyond Normal FormNo-\(\Phi\)-regret learning with more complex strategy spaces and deviation sets.
  3. 3Ellipsoid Against Hope\(\log(1/\epsilon)\)-time algorithms for \(\Phi\)-equilibrium computation via the ellipsoid algorithm.
  4. 4\(\Phi\)-Regret and MulticalibrationA forecasting route from multicalibration to \(\Phi\)-regret minimization.
  5. 5TreeSwap: Efficient Swap Regret MinimizationWeakly sublinear swap-regret minimization for large action spaces.
  6. 6Profile Swap Regret, Manipulability, and Response-Based ApproachabilityProfile swap regret, non-manipulability, and response-based approachability.

These tutorial notes are draft material prepared for the EC’26 tutorial that has not undergone formal peer review. Feedback and typo reports are welcome. You can report typos or suggest edits directly on the GitHub repository of these notes.