General Information

---

Project Description

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 settings where agents are fully rational, as well as those 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. We show that it is in fact NP-hard to answer this question for a general network for both full and bounded rationality of agents. Another natural question in this field is that of the resilience of a network to adversarial agents. We show the robustness of the widely-studied Celebrity graph.

Research Log

Week 1: 28.5. - 2.6.

• This week I was mainly familiarizing myself with the project I will be working on for the next two months. I attended several introductory seminars, including a session on website creation and an orientation talk, which provided valuable insights into the internship program. Upon arrival, I met with my mentor, who gave me an introductory explanation of the project and provided essential papers to dive deeper into the topic.

• Throughout the week, I took the opportunity to get to know my colleagues, Filip, Rhett, and Amanda, as well as other team members working on different projects.

• Towards the end of the week, I began collaborating with my group on an introductory presentation about our project. Overall, it was a productive and engaging start to the internship.

Week 2: 3.6. - 9.6.

• During the second week I continued reading the papers provided by my mentor and started working on the project. I also attended a workshop on Modelling randomenss in neural networks, which was very interesting and provided me with new insights in the area of machine learning.

• While reading the papers, I made a few observations about possible relation of our problem and the field of statistical physics that I plan to focus on during the following days.

• We also had a group meeting where we discussed the progress of our projects and shared our ideas. We started working on the question of complexity of truth learning in a social and adversarial setting.

Week 3: 10.6 - 16.6.

• This week I attented the 5 day long workshop called "Current Trends in Mathematics: Beyond the Freshmen Horizons".

Week 4: 17.6. - 23.6.

• I continued working on the project and reading the literature related to the dynamics of the truth learning. I tried to find out more about the relation of dynamics in the truth learning setting compared to the dynamics from statistical physics.

• We had another group meeting with the mentor where we weere presented with new paper related to our project. We discussed the paper and the possible implications of the results on our project. The paper asks the question of how to find the truth when majority vote does not give the right answer (the crowd is wrong). The title of the publication was "A solution to the single-question crowd wisdom problem".

Week 5: 24.6 - 30.6.

• We continued dicussing the paper from the last week and tried to come up with the solution to the problem presented in the paper.

Week 6: 1.7. - 7.7.

• Met with students from NYC REU program and discussed our projects.

• Also attended the lecture about Complexity of combinatorial log-concave inequalities given by Prof. Swee Hong Chan.

Week 7: 8.7. - 14.7.

• This week we had a meeting with our mentor, where we discussed the progress of our project and the next steps. We were talking mainly about the open problem regarding the effectiveness of the Bayesian truth learning algorithm compared to the one of majority vote.

• I also had the chance to participate on the trip to Nokia Bell Laboratories, organized by the DIMACS REU program. We had a tour of the labs and listened to the talks given by the researchers working there.

• At the end of the week, there was a graduate school panel discussion, where we had the opportunity to ask questions to the professors and current graduate students, learn more about the application process and the lifestyle of a PhD student.

• I've slowly started working on the write up of the project.

Week 8: 15.7 - 21.7.

• This week was the last week of REU in the US, that's why I've been mainly ofcusing on completing the research project and preparing the final presentation.

• On wednesday I presented the results of our research project to the other participants and mentors. The presentation went well and I received valuable feedback from the audience.

Week 9: 22.7 - 28.7.

• After working on the research project for the past weeks, I finally moved back to Prague, where the REU program continued.

• Each day of the week I attended series of lectures on various topics in discrete mathematics, mainly focusing on graph theory and combinatorics. In the afternoons, we worked on the problem sets and discussed the solutions.

• I attended the following lectures:
  • Spectral graph theory with applications - Martin Černý
  • Annoying (but beautiful) visibility problems - Martin Balko
  • Mathematics of Perfect Graphs - Irena Penev
  • Removal lemma and its applications - Jan Volec

• Apart of this spent the week working on the final writeup and the reports.

Week 10: 29.7 - 2.8.

• I attended the Midsummer Combinatorial Workshop XXIX organized by the Charles University in Prague. The workshop focused on problems of all fields of graph theory, combinatorics and discrete geometry.

---

Resources

• A solution to the single-question crowd wisdom problem 2017 - Dražen Prelec, H. Sebastian Seung & John McCoy
• Bayesian Decision Making in Groups is Hard 2017 - Jan Hazla, Ali Jadbabaie, Elchanan Mossel, M. Amin Rahimian
• A Random Dictator Is All You Need 2023 - Itai Arieli, Yakov Babichenko, Inbal Talgam-Cohen, Konstantin Zabarnyi
• Dynamical Phase Transitions in Graph Cellular Automata 2023 - Freya Behrens, Barbora Hudcová, Lenka Zdeborová

Acknowledgements

This work was carried out while the author Júlia Križanová was a participant in the 2024 DIMACS REU program, supported by CoSP, a project funded by European Union’s Horizon 2020 research and innovation programme, grant agreement No. 823748.