[talks] Divyarthi Mohan General Exam Presentation Wednesday, May 23, 2018 at 11:00 am CS302

[Barbara A. Mooring]

Divyarthi Mohan will present her General Exam Presentation on Wednesday, May 23, 2018 at 11:00 am in CS302.

Committee: 

Matt Weinberg (Adviser)
Bernard Chazelle
Ran Raz

Title: Information Aggregation via non-Bayesian Asynchronous Learning
in Trees

Abstract:

We consider a social network where each person or node has to make a binary decision in a
world with a ground truth that one of the two choices is better. For example, each node has
to choose red or blue, and the correct choice is red. Each node v has a private signal X(v) 2
fred, blueg that denotes its belief about the world and these signals are drawn independently
from a distribution that is biased towards the truth. Initially all nodes are unannounced and
information propagates in the graph through a stochastic process. At each time step, we pick
a node uniformly at random to announce its opinion and nodes can update their opinions over
time when picked again. Each node can only see its neighbours' latest announcements (and not
their private signals). We study how information aggregates when the social network is a tree
and the nodes conform to the majority of their neighbours (that have announced).
Previously, Feldman et al. showed that when the graph is sparse and expansive, with high
probability, the correct consensus is reached. They prove this by showing that in a bounded
degree graph, a correct majority is reached in near linear steps; if the graph is an expander, this
majority opinion propagates to the whole graph.
We show that in any tree, with high probability, after near linear steps the majority of nodes
have the correct opinion. We will also further discuss approaches to show that the process
stabilizes in a correct majority.


Barbara A. Mooring
Interim Graduate Coordinator
Computer Science Department
Princeton University