Learning by trial and error

A person learns by trial and error if he occasionally tries out new strategies, rejecting choices that are “erroneous” in the sense that they do not lead to higher payoffs. In a game, however, strategies can become erroneous due to a change of behavior by someone else. Such passive errors may also trigger a search for new and better strategies, but the nature of the search is different than when a player is actively engaged in experimentation. This paper introduces a simple version of this idea, called interactive trial and error learning, which has the property that it implements Nash equilibrium behavior in any game with generic payoffs and at least one pure Nash equilibrium. Unlike regret testing (Foster and Young, 2006), the method requires no statistical estimation. Unlike a learning procedure proposed by Hart and Mas-Colell (2006), it requires no knowledge of the other players' actions: learning proceeds purely by responding to one's own payoff history. The approach shows that there exist simple and intuitive rules for discovering equilibria in decentralized settings where players have no knowledge of the system in which they are embedded.