A General Class of Adaptive Strategies
Sergiu Hart and Andreu Mas-Colell
Abstract
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.