Full Text forthcoming, Games and Economic Behavior
Drew Fudenberg and David K. Levine
June 30, 1995
revised: August 13, 1997
Abstract:
Each period, a player must choose an action without knowing the outcome that will be chosen by "Nature," according to an unknown and possibly history-dependent stochastic rule. We discuss have a class of procedures that assign observations to categories, and prescribe a simple randomized variation of fictitious play within each category. These procedures are "conditionally consistent," in the sense of yielding almost as high a time-average payoff as could be obtained if the player chose knowing the conditional distributions of actions given categories. Moreover given any alternative procedure, there is a conditionally consistent procedure whose performance is no more than epsilon worse regardless of the discount factor. Cycles can persist if all players classify histories in the same way; however in an example, where players classify histories differently, the system converges to a Nash equilibrium. We also argue that in the long run the time-average of play should resemble a correlated equilibrium.Source code for the fictitious play and conditional learning simulations can be downloaded here. These are in the form of Excel 7.0 spreadsheets.