Working Paper 99-04
Department of Economics
University of North Carolina, Chapel Hill
http://www.unc.edu/depts/econ

Abstract

Learning in Games by Random Sampling

We study repeated interactions among a fixed set of low rationality'' players. Each player has a status quo action. Occasionally, he randomly samples other actions and changes his status quo if the sampled action yields a higher payoff. This behavior generates a random process, the \emph{% better-reply dynamics}. In the long run the behavior we describe leads to Nash equilibrium in games with the \emph{weak finite improvement property}. We show that finite, supermodular games and generic, continuous, two-player, quasi-concave games, have this property. If players occasionally change strategies when sampling does not improve payoff (i.e., make mistakes) and if several players can sample at the same time, the resulting \emph{% better-reply dynamics with simultaneous sampling} converges to the Pareto optimal Nash equilibrium in common interest games. In general games, convergence to Nash equilibrium need not occur.

James Friedman
Department of Economics, CB# 3305
University of North Carolina
Chapel Hill, NC 27599-3305
Jim_Friedman@unc.edu
voice (919) 966-3669
fax (919) 966-4986