Synchronous and asynchronous learning by responsive learning automata

We consider the ability of economic agents to learn in a decentralized envi-ronment in which agents do not know the (stochastic) payo matrix and can not observe their opponents ' actions; they merely know, at each stage of the game, their own action and the resulting payo. We discuss the requirements for learning in such an environment, and show that a simple probabilistic learning algorithm satis es two important optimizing properties: i) When placed in an unknown but eventually stationary random environment, they converge in bounded time, in a sense we make precise, to strategies that maximize average payo. ii) They satisfy a monotonicity property (related to the \law of the eect") in which increasing the payos for a given strategy increases the probability of that strategy being played in the future. We then study how groups of such learners interact in a general game. We show that synchronous groups of these learners converge to the serially undominated set. In contrast, asynchronous groups do not necessarily converge to the serially undominated set, highlighting the importance of timing in decentralized learning. However, these asynchronous learners do converge to the serially unoverwhelmed set, which we dene. Thus, the serially unoverwhelmed set can be viewed as an appropriate solution concept in decentralized settings. 1