Asynchronous majority dynamics in preferential attachment trees

Maryam Bahrani, Nicole Immorlica, Divyarthi Mohan, S. Matthew Weinberg

Research output: Chapter in Book/Report/Conference proceedingConference contribution

4 Scopus citations

Abstract

We study information aggregation in networks where agents make binary decisions (labeled incorrect or correct). Agents initially form independent private beliefs about the better decision, which is correct with probability 1/2 + δ. The dynamics we consider are asynchronous (each round, a single agent updates their announced decision) and non-Bayesian (agents simply copy the majority announcements among their neighbors, tie-breaking in favor of their private signal). Our main result proves that when the network is a tree formed according to the preferential attachment model [5], with high probability, the process stabilizes in a correct majority within O(nlog n/log log n) rounds. We extend our results to other tree structures, including balanced M-ary trees for any M.

Original languageEnglish (US)
Title of host publication47th International Colloquium on Automata, Languages, and Programming, ICALP 2020
EditorsArtur Czumaj, Anuj Dawar, Emanuela Merelli
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771382
DOIs
StatePublished - Jun 1 2020
Event47th International Colloquium on Automata, Languages, and Programming, ICALP 2020 - Virtual, Online, Germany
Duration: Jul 8 2020Jul 11 2020

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume168
ISSN (Print)1868-8969

Conference

Conference47th International Colloquium on Automata, Languages, and Programming, ICALP 2020
Country/TerritoryGermany
CityVirtual, Online
Period7/8/207/11/20

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • Information Cascades
  • Majority Dynamics
  • Non-Bayesian Asynchronous Learning
  • Opinion Dynamics
  • Preferential Attachment
  • Stochastic Processes

Fingerprint

Dive into the research topics of 'Asynchronous majority dynamics in preferential attachment trees'. Together they form a unique fingerprint.

Cite this