Emergence of fast agreement in an overhearing population: The case of the naming game

¹ Department of Computer Science and Engineering, Indian Institute of Technology Kharagpur, India - 721302
² Institute for Scientific Interchange (ISI) - Viale Settimio Severo 65, 10133 Torino, Italy, EU
³ Physics Department, Sapienza University - Piazzale Aldo Moro 5, 00185 Rome, Italy, EU

Received: 22 November 2012
Accepted: 8 March 2013

Abstract

The naming game (NG) describes the agreement dynamics of a population of N agents interacting locally in pairs leading to the emergence of a shared vocabulary. This model has its relevance in the novel fields of semiotic dynamics and specifically to opinion formation and language evolution. The application of this model ranges from wireless sensor networks as spreading algorithms, leader election algorithms to user-based social tagging systems. In this paper, we introduce the concept of overhearing (i.e., at every time step of the game, a random set of N^δ individuals are chosen from the population who overhear the transmitted word from the speaker and accordingly reshape their inventories). When δ = 0 one recovers the behavior of the original NG. As one increases δ, the population of agents reaches a faster agreement with a significantly low-memory requirement. The convergence time to reach global consensus scales as logN as δ approaches 1.