Engineering agreement: The naming game with asymmetric and heterogeneous agents

Jie Gao, Bo Li, Grant Schoenebeck, Fang Yi Yu

Research output: Contribution to conferencePaperpeer-review


Being popular in language evolution, cognitive science, and culture dynamics, the Naming Game has been widely used to analyze how agents reach global consensus via communications in multi-agent systems. Most prior work considered networks that are symmetric and homogeneous (e.g., vertex transitive). In this paper we consider asymmetric or heterogeneous settings that complement the current literature: 1) we show that increasing asymmetry in network topology can improve convergence rates. The star graph empirically converges faster than all previously studied graphs; 2) we consider graph topologies that are particularly challenging for naming game such as disjoint cliques or multi-level trees and ask how much extra homogeneity (random edges) is required to allow convergence or fast convergence. We provided theoretical analysis which was confirmed by simulations; 3) we analyze how consensus can be manipulated when stubborn nodes are introduced at different points of the process. Early introduction of stubborn nodes can easily influence the outcome in certain family of networks while late introduction of stubborn nodes has much less power.

Original languageEnglish (US)
Number of pages7
StatePublished - 2017
Externally publishedYes
Event31st AAAI Conference on Artificial Intelligence, AAAI 2017 - San Francisco, United States
Duration: Feb 4 2017Feb 10 2017


Other31st AAAI Conference on Artificial Intelligence, AAAI 2017
Country/TerritoryUnited States
CitySan Francisco

ASJC Scopus subject areas

  • Artificial Intelligence


Dive into the research topics of 'Engineering agreement: The naming game with asymmetric and heterogeneous agents'. Together they form a unique fingerprint.

Cite this