Swap Regret and Correlated Equilibria Beyond Normal-Form Games

Eshwar Ram Arunachaleswaran, Natalie Collina, Yishay Mansour, Mehryar Mohri, Jon Schneider, Balasubramanian Sivan

In the field of multi-agent learning, a primary objective is to design algorithms capable of navigating complex strategic environments without being exploited by opponents. While the concept of "swap regret" has long provided a gold standard for non-manipulability in simple, normal-form games, extending these guarantees to more complex scenarios—such as auctions (Bayesian games) or Poker (extensive-form games)—has remained a significant challenge. This research, authored by a team from the University of Pennsylvania, Tel Aviv University, and Google Research, introduces a new framework to bridge this gap.

The Challenge of Polytope Games

Most real-world strategic interactions are categorized as "polytope games," where players choose actions from a convex set. In these settings, the traditional definitions of swap regret used in simple games (like Rock-Paper-Scissors) do not easily apply. Previous attempts to define swap regret for polytope games faced a binary failure: they were either too weak to guarantee that a learner couldn't be "led" into bad outcomes by a strategic opponent, or they were so mathematically demanding that they were believed to be computationally impossible to minimize.

Introducing Profile Swap Regret

The authors propose a novel metric called profile swap regret. Unlike previous round-by-round definitions, this notion is defined over the Correlated Strategy Profile (CSP)—the time-averaged joint distribution of all players' actions.

To make this metric functional, the authors utilized several key technical approaches:

  • Convex Decomposition: They define the regret by identifying the optimal way to break down the average history of play into a combination of independent strategies.
  • Blackwell Approachability: The problem of minimizing regret is framed as a geometric task—reaching a specific target set within a high-dimensional space.
  • Semi-Separation Oracles: Because calculating profile swap regret is NP-hard, the authors adapted "optimization via semi-separation oracles." This allows an algorithm to move toward a no-regret state even when it cannot perfectly calculate its exact distance from that state at any given moment.

Key Insights: Non-Manipulability and the Mediator Gap

A central contribution of the paper is the "Non-Manipulability Equivalence." The authors prove that incurring sublinear profile swap regret is exactly equivalent to being non-manipulable in polytope games. This resolves an open question in the field from 2022, establishing profile swap regret as the "minimal core" of robust learning.

Furthermore, the paper identifies a "Mediator Gap." In simple games, the outcomes of decentralized learning are generally the same as those a third-party mediator could suggest. However, in polytope games, the authors show that decentralized learning can result in "Profile Correlated Equilibria"—outcomes that actually cannot be implemented by a traditional mediator.

Results and Complexity

The research provides the first computationally efficient algorithm for this problem, achieving $O(\sqrt{T})$ profile swap regret over $T$ rounds with polynomial time complexity per iteration. This is particularly notable because the authors also formally prove (Theorem 17) that computing the profile swap distance for a Bayesian game is NP-hard. Their work demonstrates that a regret metric can be efficiently minimized even if it is computationally hard to calculate for a specific transcript of play.

Limitations and Future Directions

While the paper marks a significant theoretical leap, several areas remain for future exploration:

  • Multi-Player Scaling: The current results are restricted to two-player games. Extending these guarantees to multi-player polytope games remains an open challenge.
  • Full-Rank Constraints: Certain connections between game-agnostic learning and profile swap regret require the game to be "optimizer full-rank," meaning the optimizer's actions must be fully recoverable from the rewards they generate.
  • Implementation: The use of semi-separation oracles and Blackwell approachability involves sophisticated optimization machinery that may be difficult to implement for very large-scale, real-world applications.

By providing the first efficient algorithm to minimize a non-manipulable regret notion in polytope games, this work sets a new foundation for robust multi-agent learning in complex environments.

Summary updated

BibTeX
@inproceedings{arunachaleswaran2025swap,
  author = {Eshwar Ram Arunachaleswaran and Natalie Collina and Yishay Mansour and Mehryar Mohri and Jon Schneider and Balasubramanian Sivan},
  title = {{Swap Regret and Correlated Equilibria Beyond Normal-Form Games}},
  booktitle = {EC},
  year = {2025},
  doi = {10.1145/3736252.3742511},
}
Figure