- NP-hardness of Finding Optimal Learning Rate in a Sequential Social Network
- Project Year:
2024
- REU Student (s):
Filip Uradnik | Charles University (Prague, Czech Republic)
| Amanda Wang | Princeton University NJ
- Student 1 Institution:
Charles University (Prague, Czech Republic)
- Student 2 Institution:
Princeton University
- Project Mentor:
Jie Gao
- Project Mentor Area:
Computer Science
- Project Abstract:
Sequential learning models situations where agents predict a ground truth in sequence, having access to their private, noisy measurements, and the predictions of agents who came earlier in the sequence. We study a generalization of this model to networks, where agents only see a subset of the previous agents' actions - those in their own neighborhood. We consider a setting where agents' rationality is bounded, only basing their decisions on a simple majority rule. The fraction of agents who predict the ground truth correctly depends heavily on the ordering in which the predictions are made. An important question in this area is whether there exists an ordering, under which the agents predict the ground truth correctly with high probability. In our project, we show that it is in fact NP-hard to answer this question for a general network for agents with bounded rationality.
