General Procedures Leading to Correlated Equilibria

Amotz Cahn

Hart and Mas-Colell (2000) show that if all players play "regret matching" strategies, i.e. they play with probabilities proportional to the regrets, then the empirical distributions of play converge to the set of correlated equilibria, and the regrets of each player converge to zero. Here we show that if only one player, say player i , plays according to these probabilities, while the other players are "not too sophisticated", then the result that player i's regrets converge to zero continues to hold. The condition of "not too sophisticated" essentially says that the effect of one change of action of player i on the future actions of the other players decreases to zero as the horizon goes to infinity. Furthermore, we generalize all these results to a whole class of "regret based" strategies. In particular, these include the "smooth fictitious play" of Fudenberg and Levine (1998).

May, 2000
Published in: 
International Journal of Game Theory 33 (2004), 21-40