The Naming Game on the complete graph

2017/03/06 by Eric Foxall, Foxall, Eric · 1 citation
Decision Sciences · Physics and Astronomy · #60G99 #Complex Network Analysis Techniques #FOS: Mathematics #Game Theory and Applications #Opinion Dynamics and Social Influence #Probability (math.PR)

paper · pdf · doi:10.48550/arxiv.1703.02088

openalex publication_date 2017/03/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider a model of language development, known as the naming game, in which agents invent, share and then select descriptive words for a single object, in such a way as to promote local consensus. When formulated on a finite and connected graph, a global consensus eventually emerges in which all agents use a common unique word. Previous numerical studies of the model on the complete graph with n agents suggest that when no words initially exist, the time to consensus is of order n^1/2, assuming each agent speaks at a constant rate. We show rigorously that the time to consensus is at least n^1/2-o(1), and that it is at most constant times log n when only two words remain. In order to do so we develop sample path estimates for quasi-left continuous semimartingales with bounded jumps.

Citations

• Statistical physics of social dynamics

Cited by

• Time of appearance of a large gap in a dynamic Poisson point process

Related

• The naming game in language dynamics revisited
• Consensus Dynamics in a non-deterministic Naming Game with Shared Memory
• Divide-and-rule policy in the Naming Game
• Naming game with learning errors in communications
• Knowledge Consensus in complex networks: the role of learning