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

[Barbara A. Mooring]

Divyarthi Mohan will present General Exam Presentation TODAY 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) = red or blue, 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