A big congratulations and thank you to all my co-authors. Especially @ncollina.bsky.social with whom I've worked in this area for over 4 years, and Jon, who took us under his wing and reoriented us to a geometric view of algorithms

*simplices

We prove minimizing profile swap-regret is necessary & sufficient for non-manipulability and gets NR +PO. Bonus: if all agents minimize it, the dynamics can reach profiles that cannot be realized as Correlated Equilibria by traditional mediators—unlike normal-form games!

Our fix? Profile Swap-Regret, a further coarsening of polytope swap-regret, leveraging a geometric view of algorithms (link). Admits an efficient algorithm with O(√T) convergence! arxiv.org/abs/2402.09549

Another idea: Polytope Swap-Regret—a coarser notion based on favorable decompositions of the learner’s action - with non-manipulability + √T convergence but no known efficient algorithms
arxiv.org/abs/2205.08562

One approach treats polytope games (for eg: Bayesian games, extensive form games) as high-dimensional normal-form games → exponential blowup resulting in a tradeoff between per-round efficiency and convergence rate (O(T/log T) convergence for efficient algorithms)

In normal-form games, No-Swap-Regret (NSR) algorithms ensure no-regret, non-manipulability, & Pareto-optimality. But extending these guarantees to polytopes (instead of simplexes) is tricky

Punchline: We design an efficient no-regret algorithm for games with arbitrary polytopal actions—that is simultaneously non-manipulable, Pareto-optimal, and converging at O(√T·Poly(d)), where d is the action space dimension