Regret in Markets | Turing's Invisible Hand
How do markets and other games reach equilibrium? Or at least, how can they do so? A nice answer will have each participant in the market or game repeatedly performing some simple update step that only depends on information available to him and that makes sense from his local point of view, with the whole system then magically converging to equilibrium. The meanings of “simple”, “update”, “information available”, “makes sense”, and “converging” may vary, but the idea is to capture the basic phenomena of a global equilibrium arising from simple local optimizations.
In this post I will describe some recent work that shows this kind of phenomena where local “regret-minimization” optimizations lead to global convergence in a natural market model.
Related: The stability of Lonely Vickrey, or One's Choice of Neighbourhood