A Reinforcement Procedure Leading to Correlated Equilibrium

Sergiu Hart and Andreu Mas-Colell

(Acrobat PDF files)

We consider repeated games where at any period each player knows only his set of actions and the stream of payoffs that he has received in the past. He knows neither his own payoff function, nor the characteristics of the other players (how many there are, their strategies and payoffs). In this context, we present an adaptive procedure for play — called “modified-regret-matching” — which is interpretable as a stimulus-response or reinforcement procedure, and which has the property that any limit point of the empirical distribution of play is a correlated equilibrium of the stage game.

Keywords: adaptive strategies, approachability, correlated equilibrium, regret, regret-matching, reinforcement, stimulus-response, unknown game.

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