Engineering Agreement: The Naming Game with Asymmetric and Heterogeneous Agents

Authors

  • Jie Gao Stony Brook University
  • Bo Li University of Michigan
  • Grant Schoenebeck University of Michgan
  • Fang-Yi Yu University of Michigan

DOI:

https://doi.org/10.1609/aaai.v31i1.10621

Keywords:

dynamic system, consensus, naming game

Abstract

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.

Downloads

Published

2017-02-10

How to Cite

Gao, J., Li, B., Schoenebeck, G., & Yu, F.-Y. (2017). Engineering Agreement: The Naming Game with Asymmetric and Heterogeneous Agents. Proceedings of the AAAI Conference on Artificial Intelligence, 31(1). https://doi.org/10.1609/aaai.v31i1.10621

Issue

Section

AAAI Technical Track: Game Theory and Economic Paradigms