A General Class of Adaptive Strategies

Sergiu Hart and Andreu Mas-Colell

(Acrobat PDF files)

We exhibit and characterize an entire class of simple adaptive strategies, in the repeated play of a game, having the Hannan-consistency property: in the long-run, the player is guaranteed an average payoff as large as the best-reply payoff to the empirical distribution of play of the other players; i.e., there is no "regret." Smooth fictitious play (Fudenberg and Levine [1995, J. Econ. Dynam. Control 19, 1065-1090]) and regret-matching (Hart and Mas-Colell [2000, Econometrica 68, 1127-1150]) are particular cases. The motivation and application of the current paper come from the study of procedures whose empirical distribution of play is, in the long-run, (almost) a correlated equilibrium. For the analysis we first develop a generalization of Blackwell's (1956, Pacific J. Math. 6, 1-8) approachability strategy for games with vector payoffs.

Keywords: adaptive strategies; approachability; correlated equilibrium; fictitious play; regret; regret-matching; smooth fictitious play.

Journal of Economic Literature Classification Numbers: C7, D7, C6.