Narrow Results

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) and regret matching (Hart and Mas-Colell 2000) 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) approachability strategy for games with vector payoffs.

We exhibit a large class of simple rules of behavior, which we call adaptive heuristics, and show that they generate rational behavior in the long run. These adaptive heuristics are based on natural regret measures, and may be viewed as a bridge between rational and behavioral viewpoints. Taken together, the results presented here establish a solid connection between the dynamic approach of adaptive heuristics and the static approach of correlated equilibria.