Swap Regret and Strategic Learning
@EC25

This workshop has now concluded. Thank you to all the attendees -- we hope you had a good time! 

There are no recordings, but we are in the process of uploading slides for the talks (you can find them below by the schedule). 

When: 9 AM - 12 PM on Thursday, July 10, 2025.
Where: FISHER A (In person at EC). See the EC workshops page for additional details.

Description: There is a long and rich history of research in the intersection of learning theory and game theory. Modeling economic agents as agents running simple learning algorithms is compelling in light of the computational and informational difficulties of being perfectly rational. More recently, as humans entrust more of their economic decisions to automated agents like auto-bidders and large language models, it has become even more important to understand the consequences of modeling agents as learners. 

Over the past few years, there has been a large amount of new work in this area exploring questions about how to design robust learning algorithms for strategic settings (e.g., learning algorithms that cannot be manipulated by a strategic adversary). Central to this line of work is the identification of swap regret as a uniquely important regret measure to minimize in strategic settings, with many examples where regular no-external-regret learning algorithms are highly manipulable by a strategic adversary, but where no-swap-regret learning algorithms are robust to these same manipulations.  Simultaneously, over the last few years, there have been several breakthrough results in our understanding of how to design learning algorithms which minimize swap-regret or related quantities.

Our goals with this workshop are to provide researchers new to these questions with an introduction to this area, while also serving as a forum for researchers to present recent work in this area. We hope this workshop will bring together researchers from a diverse set of communities (e.g., researchers specializing in game theory, mechanism design, and online learning).

Schedule: 

9:00 - 9:50 AM: Workshop organizers, "Tutorial on swap regret and strategic learning" (Slides Part 1, Slides Part 2)

9:50 - 10:15 AM: Gabriele Farina, "Efficient Learning and Computation of Linear and Low-Degree Correlated Equilibrium in General Convex Games" (Slides)

10:15 - 10:45 AM: Coffee break

10:45 - 11:10 AM: Aviad Rubinstein, "Fast swap regret minimization with applications" (Slides)

11:10 - 11:35 AM: Yoav Kolumbus, "Contracting with a Learning Agent" (Slides)

11:35 - 12:00 PM: Nika Haghtalab, "The Truth About Your Lying Calibrated Forecaster: How to Design Truthful Calibration Measures"

Invited Speakers and Talks:

Gabriele Farina (MIT)
Title: Efficient Learning and Computation of Linear and Low-Degree Correlated Equilibrium in General Convex Games
Abstract: We propose efficient no-regret learning dynamics and ellipsoid-based methods for computing linear and low-degree-polynomial correlated equilibria—relaxations of correlated equilibria and a strengthening of coarse correlated equilibria—in general convex games. These are games where the number of pure strategies is potentially exponential in the natural representation of the game, such as extensive-form games. Our work identifies these relaxations of correlated equilibria as the tightest known notions of equilibrium that are computable in polynomial time and are efficiently learnable for general convex games. Our results are enabled by a generalization of the seminal framework of Gordon et al. [2008] for Φ-regret minimization, providing extensions to this framework that can be used even when the set of deviations Φ is intractable to separate/optimize over. We sidestep the lack of tractability of Φ by means of a new algorithmic routine that we coin semiseparation. We also show nearly matching lower bounds in the online learning setting, thereby obtaining for the first time a family of deviations that captures the learnability of Φ-regret.

This talk discussed work that has appeared as follows:

• G. Farina, C. Pipis. Polynomial-Time Computation of Exact Φ-Equilibria in Polyhedral Games. NeurIPS 2024. https://arxiv.org/abs/2402.16316 

• C. Daskalakis, G. Farina, M. Fishelson, C. Pipis, J. Schneider. Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games. STOC 2025. https://arxiv.org/abs/2412.20291 

• B. H. Zhang, I. Anagnostides, E. Tewolde, R. E. Berker, G. Farina, V. Conitzer, T. Sandholm Learning and Computation of Φ-Equilibria at the Frontier of Tractability. EC 2025. https://arxiv.org/abs/2502.18582 

• C. Daskalakis, G. Farina, N. Golowich, T. Sandholm, B. H. Zhang. A Lower Bound on Swap Regret in Extensive-Form Games. arXiv preprint. https://arxiv.org/abs/2406.13116 

Nika Haghtalab (UC Berkeley)
Title: The Truth About Your Lying Calibrated Forecaster: How to Design Truthful Calibration Measures
Abstract: Truthfulness is an important property of calibration measures, ensuring that the forecaster is not incentivized to exploit the system with deliberately poor forecasts. This makes it an essential desideratum for calibration measures, alongside typical requirements, such as soundness and completeness. This calls for a systematic study of calibration measures that encourage truthfulness. In this talk, I will introduce the concept of truthful calibration measures and conduct a taxonomy of existing calibration measures and their truthfulness. Perhaps surprisingly, we find that all of them are far from being truthful. That is, under existing calibration measures, there are simple distributions on which a polylogarithmic (or even zero) penalty is achievable, while truthful prediction leads to a polynomial penalty. We then introduce a new calibration measure termed the Subsampled Smooth Calibration Error (SSCE) under which truthful prediction is optimal up to a constant multiplicative factor. 

Yoav Kolumbus (Cornell University)
Title: Contracting with a Learning Agent
Abstract: Many real-life contractual relations differ completely from the clean, static model at the heart of principal-agent theory. Typically, they involve repeated strategic interactions of the principal and agent, taking place under uncertainty and over time. While appealing in theory, agents seldom use complex dynamic strategies in practice, often preferring to circumvent complexity and approach uncertainty through learning. We initiate the study of repeated contracts with a learning agent, focusing on agents who achieve no-regret outcomes. Optimizing against a no-regret agent is a known open problem in general games; we achieve an optimal solution to this problem for a canonical contract setting, in which the agent's choice among multiple actions leads to success/failure. The solution has a surprisingly simple structure: for some α>0, initially offer the agent a linear contract with scalar α, then switch to offering a linear contract with scalar 0. This switch causes the agent to "free-fall" through their action space and during this time provides the principal with non-zero reward at zero cost. Despite apparent exploitation of the agent, this dynamic contract can leave both players better off compared to the best static contract. Our results generalize beyond success/failure, to arbitrary non-linear contracts which the principal rescales dynamically. Finally, we quantify the dependence of our results on knowledge of the time horizon, and, to the best of our knowledge, are the first to address this consideration in the study of strategizing against learning agents.

Paper url: https://proceedings.neurips.cc/paper_files/paper/2024/file/8d7c8a3a0ed04006d129b3cebcac7a3e-Paper-Conference.pdf 

Aviad Rubinstein (Stanford University)
Title: Fast swap regret minimization and applications
Abstract: We give a simple and computationally efficient algorithm that, for any constant ε>0, obtains εT-swap regret within only T = \polylog(n) rounds; this is an exponential improvement compared to the super-linear number of rounds required by the state-of-the-art algorithm, and resolves the main open problem of [Blum & Mansour '07]. Our algorithm has an exponential dependence on ε, but we prove a new, matching lower bound.

Our algorithm for swap regret implies faster convergence to  ε-Correlated Equilibrium (ε-CE) in several regimes, resolving open problems from [Von Stengel & Forges '08, Babichenko & Rubinstein '17, Ganor & Karthik '18, Babichenko '20, Fujii '23].

In follow up work our algorithm has already been used to design new learning algorithm for Principal-Agents problems [Collina, Gupta, Roth '24], and a new efficient algorithm for high dimensional calibration [Peng '25] (the latter result resolves open questions by [Abernethy & Mannor '11, Hazan & Kakade '12]).  

Talk is based on joint work with Binghui Peng (also obtained independently by Dagan, Daskalakis, Fishelson, and Golowich).

Accepted Posters (1:30 pm to 2:45 pm):

• Robust Online Learning with Private Information (Kyohei Okumura)

• Persuasive Prediction via Decision Calibration (Jingwu Tang)

• Dimension-Free Decision Calibration for Nonlinear Loss Functions (Jiahao Zhang)

• Learning to Steer Learners in Games (Yizhou Zhang)

• The Value of Costly Signaling in Constant-Regret Alignment with Inconsistent Preferences (Ali Shirali)

• Regulation of Algorithmic Collusion, Refined: Testing Pessimistic Calibrated Regret (Chang Wang)

• Breaking Algorithmic Collusion via Simple Defections (Natallie Collina)

• On Tractable $\Phi$-Equilibrium in Non-Concave Games (Weiqiang Zheng)

• Improved Bounds for Swap Multicalibration and Swap Omniprediction (Spandan Senapati)

Accepted Posters (3:15 pm to 4:30 pm):

• Learning a Stackelberg Leader's Incentives from Optimal Commitments (Jiarui Gan)

• When Are Forecasts Trusted? The Role of Calibration and Visualization (Paula Kayongo)

• Computational Intractability of Strategizing against Online Learners (Nived Rajaraman)

• Perfectly Truthful Calibration Errors (Yifan Wu)

• On the Limitations and Possibilities of Nash Regret Minimization in Zero-Sum Matrix Games under Noisy Feedback (Arnab Maiti)

• Learning to Negotiate via Voluntary Commitment (Shuhui Zhu)

• Two Tickets are Better than One: Fair and Accurate Hiring Under Strategic LLM Manipulations (Lee Cohen)

• Simultaneous Swap Regret Minimization via KL-Calibration (Spandan Senapati)

Poster Size: 36" x 48"

Call for Posters: We invite all researchers to submit any recent / ongoing work on these topics for presentation as a poster at our workshop. This includes (but is not limited to) the following topics:

• Designing learning algorithms robust to strategic manipulation.

• Steering and strategically manipulating learners.

• Game-theoretic and computational properties of swap regret, Φ-regret, and calibration.

• Strategic learning in Bayesian and extensive-form games

• Playing "meta-games" (where the action space is the space of learning algorithms).

• Properties and computation of correlated equilibria / learning-based equilibria in games.

• Applications to specific problems in algorithmic game theory (auctions, contract design, Bayesian persuasion, information design, ...).

Submissions should be made through this form. The deadline for submissions is June 4, 2025. We will notify all submitters of acceptance by June 9, 2025. Please contact ec25-strategic-learning@googlegroups.com if you have any questions.

Organizers:

Jon Schneider, Google Research: Jon is a Senior Research Scientist at Google Research in New York City. His research interests include online learning, game theory, contract design, and convex optimization. Before joining Google Research, Jon completed his Ph.D. in Computer Science at Princeton University under the supervision of Mark Braverman. Email: jschnei@google.com. 

Balasubramanian Sivan, Google Research: Balu, a Senior Staff Research Scientist at Google Research in New York City, earned his Ph.D. in Computer Science from the University of Wisconsin-Madison. His research focuses on algorithmic game theory, online learning, and online algorithms. Balu's doctoral thesis received the 2013 ACM SIGecom Doctoral Dissertation Award and was recognized as the University of Wisconsin-Madison's best Computer Science thesis.
Email: balusivan@google.com. 

Rachitesh Kumar, Amazon → CMU: Rachitesh is an Amazon Postdoctoral Scientist and an incoming Assistant Professor at Carnegie Mellon University’s Tepper School of Business. Before joining Amazon, he earned his Ph.D. in Operations Research from Columbia University. His research interests include data-driven optimization, game theory, and revenue management.
Email: rachitesh@cmu.edu.