Skip navigation
Please use this identifier to cite or link to this item:
Title: Time-Independent Correct Majorities for Asynchronous Informative Processes in Balanced Binary Trees
Authors: Lin, Kevin
Advisors: Weinberg, Matthew
Department: Mathematics
Class Year: 2020
Abstract: We study the dynamics of information flow in social networks. In our model, individuals gather and share information about a binary decision, for which there is a correct and incorrect choice. Individuals start by holding independent private beliefs that are biased toward the correct choice and no publicly announced belief. Over time, they spread information locally to their connections in the social network. The dynamics of this model are asynchronous, where at each time step, exactly one random individual announces a public belief, and non-Bayesian, where individuals who announce simply copy the majority belief of their neighbors in the social network, tie-breaking with their own private belief. Our main technical innovation uses time-independent analysis to study the independence of announcements of vertex pairs, which allows us to entirely bypass reasoning in prior work about forming an initial majority through time-dependent arguments. We also prove that in balanced binary trees, a correct majority of public beliefs exists with high probability at every time after more than half of the vertices have publicly announced a belief, which implies a correct majority at stabilization.
Type of Material: Princeton University Senior Theses
Language: en
Appears in Collections:Mathematics, 1934-2020

Files in This Item:
File Description SizeFormat 
LIN-KEVIN-THESIS.pdf287.79 kBAdobe PDF    Request a copy

Items in Dataspace are protected by copyright, with all rights reserved, unless otherwise indicated.