A Simple Adaptive Procedure
Leading to Correlated Equilibrium
Sergiu Hart and Andreu Mas-Colell
Abstract
We propose a new and
simple adaptive procedure for playing a game: "regret-matching."
In this
procedure,
players may depart from their current play with probabilities that are
proportional to measures of regret for not having used other
strategies in the past.
It is shown that our adaptive
procedure
guarantees that, with probability one, the empirical distributions of
play
converge to the set of correlated equilibria of the game.
Journal of Economic Literature Classification Numbers: C72, D83
2020
ACM SIGecom Test of Time Award