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

Ecstatic and deeply honored by this award. I've had great fun thinking about algorithms as strategies for repeated games over the past few years and hope that this highlight will push more researchers to come up with exciting directions in this field! Come to our talk on Monday to learn more!

*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

What should swap-regret mean beyond normal-form games? We have a new paper (@ncollina.bsky.social, Mehryar Mohri, Yishay Mansour, Jon Schneider, Balu Sivan) tackling this question and providing a definitive answer! (thread)

arxiv.org/abs/2502.20229

Check out our new paper, on optimal algorithmic commitments against a distribution of opponents!