- Truth learning in Social Networks under Random Decision Orderings
- Project Year:
2025
- REU Student (s):
William Guo | University of Pennsylvania PA
| Edward Xiong | Massachusetts Institute of Technology MA
- Student 1 Institution:
University of Pennsylvania
- Student 2 Institution:
Massachusetts Institute of Technology
- Project Mentor:
Jie Gao
- Project Mentor Area:
Computer Science
- Project Abstract:
In the sequential learning problem, a network of agents make decisions, informed by a noisy private signal and the predictions of neighboring agents before them. We explore the properties of networks where agents make decisions in a uniformly random order. We characterize necessary conditions for such networks to achieve asymptotic truth learning and introduce various graph constructions that learn in different ways. We also develop an algorithm to transform arbitrary graphs into random-order learning networks using few edge/vertex modifications, with provable approximation guarantees. Finally, we analyze the robustness of learning networks, demonstrating that those achieving asymptotic truth learning under random orderings are resilient to a bounded number of adversarial modifications. Our findings reveal structural properties in networks that achieve random learning and offer algorithmic tools for engineering strong social networks.
