Payoff-based dynamics for multi-player weakly acyclic games

This chapter focusses on the class of n-person games that are weakly acyclic in better replies, that is, from any initial combination of stage-game strategies there is a sequence of better replies that lead to a pure Nash equilibrium. An adaptive process is payoff-based or completely uncoupled if the process depends only on a player's own actions and own payoffs from previous play; it does not depend on the actions taken by other players or their realized payoffs. The chapter analyses simple payoff-based learning processes in which players occasionally experiment with alternative actions and retain them if they yield higher payoffs. In a weakly acyclic game this type of decentralized learning process leads to equilibrium play with probability one. An important application is to multi-agent distributed control problems. The methodology is illustrated with simulations of distributed routing over a network.