Always happy to chat about it if you wanna get in the game! 😊

Yeah it’s hard to regulate properties of algorithms, especially as they get increasingly complex! I agree abt market interventions. We have a followup work (should be up in a few days!) about how larger market sizes and a small number of entrants applying simple heuristics helps mitigate collusion.

It’s true!

This is sort of obviously true for how Elon interacts with grok, but I think will be increasingly true more broadly. Next time you get a weird answer from an LLM, ask yourself, would the company that owns this tool like this answer?

Anyway, if you made it all the way to the end of this thread, thank you so much for reading! Come learn more about the paper this Monday at EC! ✨

Specifically, in Bayesian games, there are payoff profiles you can induce via two non-manipulable algorithms playing against each other which are *impossible* to attain via a mediator providing correlated action recommendations that agents best-respond to!

These perspectives are the same in normal-form games, but it turns out they’re meaningfully DIFFERENT even if you move just to Bayesian games!

So in normal form games we can actually define CE in two equivalent ways: one is as any outcome induced by two non-manipulable algorithms playing against each other. One is as the outcome of a mediator model, where a third party sends correlated signals to each agent and each agent best-responds.

This also leads to a really cool result about Correlated Equilibria (CE)! In addition to having many strategic properties, swap regret has a tight connection to CE in normal form games; the set of move pair distributions that can be induced by two swap regret algorithms is exactly the set of all CE

By using cutting-edge tools from approachability, we are able to efficiently approach this non-manipulable set even though deciding membership is hard. And the algorithm that does so is an efficient no-Profile Swap Regret algorithm!

So what’s our trick? Instead of framing the problem as searching for the right “swap” function in these highly complex games, we directly work in menu space, where the property of non-manipulability has a very natural interpretation: the extreme points of the menu are product distributions!

By the way, an algorithm is non-manipulable exactly when the best value the opponent can ever get by playing against it, regardless of their own utility, is their Stackelberg leader value. So, there’s no reason to do fancy time-varying things against a non-manipulable algorithm.

In our paper, we define a new notion of swap regret, Profile Swap Regret. Just like its normal-form counterpart, it’s non-manipulable, forms a “minimal” menu, and is pareto-optimal. We further show that there is an efficient algorithm that guarantees vanishing Profile Swap Regret.

There have been many answers to this, leading to many definitions for swap regret beyond normal-form games. All of them either have no known efficient algorithm to minimize them, or don’t satisfy the nice strategic properties (like non-manipulability) that swap regret does in normal-form games.