General Information
Project Description
Truth Learning in a Social Setting:
Individuals gather information by both independent observations and communication with others in a social environment. Social Learning studies how dispersed and selfinterested agents aggregate information. In this project we study whether social learning can enable truth learning. It is well known that learning can fail due to herding, where agents collectively focus on an early false consensus and ignore subsequent observations. Therefore a general goal in social learning is to characterize when truth learning is guaranteed. In this project we study the computational problem of social learning with different observation models, the environment of learning and social processes such as peer pressure, social influence and network effect. (From DIMACS REU Website)
Weekly Log
 Week 1:

 Week 2:


We built a basic simulation of social networks and information cascades and ran a few test cases
using some graphs (Bipartite "Celebrity," ncliques, WattsStrogatz small world, trees, etc) on a random ordering of agents.
We were able to reproduce some expected results that aligned with previous work in the field

I continued to do literature review reading select chapters from "Networks, Crowds, and Markets" by Easley and Kleinberg
and "Algorithm Design" by Kleinberg et al.

I also read more papers relating to social networks including "Multi Issue Social Learning" by Bahar et al.

We are beginning to formulate more focused research questions on finding the best ordering of agents and local learning requirements as defined by Arieli et al.
 Week 3:


Attended a few talks in the Modern Techniques in Graph Algorithms Workshop hosted by DIMACS

Read "Maximizing the Spread of Influence through a Social Network" by Kleinberg et al
which prompted some ideas about algorithms for optimal ordering and proving the hardness of our problem

Read about oriented graphs and the GallaiHasseRoyVitaver Theorem
which proves equality between the minimal longest path of all orientations of a graph and valid coloring of a graph

We continued to update our simulation model to reflect our new ideas and began to see positive results with preferential attachment networks
 Week 4:

 Week 5:


Attended a workshop on Ramsey Theory which covered the basic results of Erdos and Szekeres

Attended a workshop on proof by example which discussed a way of using computers to help prove theorems related to sequences, series, and patterns

Read
"How to Schedule a Cascade in an Arbitrary Graph"
by Kleinberg et al and "Optimizing Information in the Herd: Guinea Pigs, Profits, and Welfare" by Daniel Sgroi

Continued to work on our simulation model algorithm on preferential attachment networks and also in more general cases

We are beginning to shift our focus towards learning more about the way graph topology affects learning rate, specifically focusing on graphs in which
all ordering of agents will fail to reach asymptotic learning and ones in which random ordering performs poorly but a forced ordering leads to successful learning

We began to see some interesting observations regarding clustering, the WattsStrogatz model, and the Connected Cave Man model

We are also interesed in looking into the importance of high value nodes in starting positive or negative cascades to reach successful learning
 Week 6:


I continued to look more closely into the Connected Cave Man model. It has interesting properties with its variance compared to a complete graph on the same number of nodes

We are beginning to try to look into bounds of learning rates given a specific graph or family of graphs and private signal rates. We want to bound the learning rate using a random ordering and the learning rate given an optimal ordering of agents

I calculated an upper bound for a sequential ordering of the Connected Cave Man graph which can serve as a lower bound of the optimal ordering

I attended a graduate school panel where we had the chance to ask some graduate students and heads of departments about graduate school applications and what we can do to prepare for them
 Week 7:


I was able to calculate an expected network learning rate of the Connected Cave Man graph on my ordering

I am trying to prove the success rate of the Connected Cave Man graph is monotonically increasing learning rate in our ordering in order to bound the optimal and random ordering on it

In showing monotonicity within CCM, I believe I will be able to show that I have optimal ordering for CCM

We visited the IBM Watson Research Labs and got to see some quantum computers and hear from researchers about their work at IBM
 Week 8:


We were able to prove the success rate of the Connected Cave Man graph is monotonically increasing and converges, bounded away from 1

We continued to work on proving optimality for our ordering in CCM

We created our final presentation showcasing our work and results from the summer and presented it to DIMACS
 Week 9:


We wrote up our final report, summarizing our findings and work from the summer
Presentations
Additional Information
 My Mentors
 This work was carried out while the authors Jordan Chong and Matt Lu were participants in the 2023 DIMACS REU program at Rutgers University, supported by NSF HDR TRIPODS award CCF1934924