A Simple Adaptive Procedure Leading to Correlated Equilibrium

Abstract

We propose a simple adaptive procedure for playing a game. In this\nprocedure, players depart from their current play with probabilities that\nare proportional to measures of regret for not having used other strategies\n(these measures are updated every period). It is shown that our adaptive\nprocedure guaranties that with probability one, the sample distributions\nof play converge to the set of correlated equilibria of the game. To\ncompute these regret measures, a player needs to know his payoff function\nand the history of play. We also offer a variation where every player\nknows only his own realized payoff history (but not his payoff function).