Distributed co-ordination is the result of dynamical processes enabling independent agents to co-ordinate their actions without the need of a central co-ordinator. In the past few years, several computational models have illustrated the role played by such dynamics for self-organizing communication systems. In particular, it has been shown that agents could bootstrap shared convention systems based on simple local adaptation rules. Such models have played a pivotal role for our understanding of emergent language processes. However, only few formal or theoretical results have been published about such systems. Deliberately simple computational models are discussed in this paper in order to make progress in understanding the underlying dynamics responsible for distributed co-ordination and the scaling laws of such systems. In particular, the paper focuses on explaining the convergence speed of those models, a largely under-investigated issue. Conjectures obtained through empirical and qualitative studies of these simple models are compared with results of more complex simulations and discussed in relation to theoretical models formalized using Markov chains, game theory and Polya processes.

Words, like genes, are replicators in competition to colonize our brains. Some, by luck or thanks to their intrinsic qualities, manage to spread in entire populations. In this paper we take the approach of cultural selectionism to study the emergence of communication systems in a population of agents. By studying simple models of word competition in noisy environments, we define the basic dynamics of such systems. We then argue for their generality and introduce the notion of semiotic schemata, generic replicators that account for the different competitions that are going on during lexicon formation. Eventually, we present a synthesis of the dynamics using this new formalism.

We report on a case study in the emergence of a lexicon in a group of autonomous distributed agents situated and grounded in an open environment. Because the agents are autonomous, grounded, and situated, the possible words and possible meanings are not fixed but continuously change as the agents autonomously evolve their communication system and adapt it to novel situations.The case study shows that a complex semiotic dynamics unfolds and that generalisations present in the language are due to processes outside the agent.

The paper argues that language change can be explained through the stochasticity observed in real-world natural language use. This thesis is demonstrated by modeling language use through language games played in an evolving population of agents. We show that the artificial languages which the agents spontaneously develop based on self-organisation, do not evolve even if the population is changing. Then we introduce stochasticity in language use and show that this leads to a constant innovation (new forms and new form-meaning associations) and a maintenance of variation in the population, if the agents are tolerant to variation. Some of these variations overtake existing linguistic conventions, particularly in changing populations, thus explaining lexicon change.

Recent work on viewing language as a complex adaptive system has shown that self-organisation can explain how a group of distributed agents can reach a coherent set of linguistic conventions and how such a set can be preserved from one generation to the next based on cultural transmission. The paper continues these investigations by exploring the presence of stochasticity in the various aspects of lexical communication: stochasticity in the non-linguistic communication constraining meaning, the transmission of the message, and the retrieval from memory. We show that there is an upperbound on the amount of stochasticity which can be tolerated and that stochasticity causes and maintains language variation. Results are based on the further exploration of a minimal computational model of language interaction in a group of distributed agents, called the naming game.

Multi-agent models of language evolution usually involve agents giving names to internal independently constructed categories. We present an approach in which the creation of categories is part of the language formation process itself. When an agent does not have a word for a particular object it is allowed to use the existing name of another object, close to the original one as defined by an analogy function. In this way, the names in the shared lexicon that has evolved in a collective way, directly yield the different object classes. We present the results of several simulations using this model showing under what conditions the agents will develop meaningful classes. We also examine the effects of an influx and outflux of agents. Finally we discuss the prospects for models in which the classes would constitute relevant complex taxonomies.