How Much Should Agents Remember? The Role of Memory Size on Convention Emergence Efficiency

One way of coordinating actions is by the adoption of norms: social conventions and lexicons are good examples of coordinating systems. This paper deals with the efficiency of the emergence of norms (adopted from a given initial set), inside a population of artificial agents that interact in pairs. Agents interact according to some well defined behavior each one implements. In order to conduct our work, we used a bench-mark agent behavior: the external majority, where agents keep a memory of its latest interactions, adopting the most observed choice occurring in the last m interactions, where m (memory size) is a given parameter. We present an empirical study in which we determine the best choices regarding the memory size that should be made in order to guarantee an efficient uniform decision emergence. In this context, a more efficient choice is one that leads to a smaller number of needed pair wise interactions. We performed a series of experiments with population sizes ranging from 50 to 5,000, memory ranging from 2 to 10, and for five network topologies (fully connected, regular, random, scale-free and small-world). Besides we also analyzed the impact on consensus emergence efficiency of the number of available initial choices (from 2, to the number of agents) together with different memory sizes.