On the emergence of social conventions: modeling, analysis, and simulations

• Published in: Artificial intelligence 1997-07, Vol.94 (1), p.139-166
• Main Authors: Shoham, Yoav, Tennenholtz, Moshe
• Format: Article
• Language: English
• Subjects: Artificial intelligence; Conventions; Convergence rate; Coordination; Decision Models; Emergent behavior; Game Theory; Multiple agents; Norms; Rationality; Simulation; Social conventions
• ISSN: 0004-3702; 1872-7921
• DOI: 10.1016/S0004-3702(97)00028-3

We define the notion of social conventions in a standard game-theoretic framework, and identify various criteria of consistency of such conventions with the principle of individual rationality. We then investigate the emergence of such conventions in a stochastic setting; we do so within a stylized framework currently popular in economic circles, namely that of stochastic games. This framework comes in several forms; in our setting agents interact with each other through a random process, and accumulate information about the system. As they do so, they continually reevaluate their current choice of strategy in light of the accumulated information. We introduce a simple and natural strategy-selection rule, called highest cumulative reward (HCR). We show a class of games in which HCR guarantees eventual convergence to a rationally acceptable social convention. Most importantly, we investigate the efficiency with which such social conventions are achieved. We give an analytic lower bound on this rate, and then present results about how HCR works out in practice. Specifically, we pick one of the most basic games, namely a basic coordination game (as defined by Lewis), and through extensive computer simulations determine not only the effect of applying HCR, but also the subtle effects of various system parameters, such as the amount of memory and the frequency of update performed by all agents.