Swap Regret and Correlated Equilibria Beyond Normal-Form Games
This work addresses an open problem in game theory for researchers studying learning algorithms in complex game settings, though it is incremental as it extends existing swap regret concepts to more general games.
The paper tackles the problem of defining and minimizing swap regret in polytope games beyond normal-form games, such as Bayesian and extensive-form games, by introducing a new variant called profile swap regret, and shows that achieving sublinear profile swap regret is necessary and sufficient for non-manipulability, with an efficient algorithm guaranteeing O(√T) regret.
Swap regret is a notion that has proven itself to be central to the study of general-sum normal-form games, with swap-regret minimization leading to convergence to the set of correlated equilibria and guaranteeing non-manipulability against a self-interested opponent. However, the situation for more general classes of games -- such as Bayesian games and extensive-form games -- is less clear-cut, with multiple candidate definitions for swap-regret but no known efficiently minimizable variant of swap regret that implies analogous non-manipulability guarantees. In this paper, we present a new variant of swap regret for polytope games that we call ``profile swap regret'', with the property that obtaining sublinear profile swap regret is both necessary and sufficient for any learning algorithm to be non-manipulable by an opponent (resolving an open problem of Mansour et al., 2022). Although we show profile swap regret is NP-hard to compute given a transcript of play, we show it is nonetheless possible to design efficient learning algorithms that guarantee at most $O(\sqrt{T})$ profile swap regret. Finally, we explore the correlated equilibrium notion induced by low-profile-swap-regret play, and demonstrate a gap between the set of outcomes that can be implemented by this learning process and the set of outcomes that can be implemented by a third-party mediator (in contrast to the situation in normal-form games).