Rhett Olson
Rutgers University DIMACS REU 2024 Participant
Home Institution: University of Minnesota
Personal Email, Personal website, Github
Project Title: Truth Learning in a Social and Adversarial Setting
Mentor: Professor Jie Gao
Rutgers University DIMACS REU 2024 Participant
Home Institution: University of Minnesota
Personal Email, Personal website, Github
Project Title: Truth Learning in a Social and Adversarial Setting
Mentor: Professor Jie Gao
In today's world, we have easy access to extensive information, from many sources. Intuitively we feel that incorporating many sources of information can lead us to take informed actions. However, we need to be intelligent about how we the information we see to avoid becoming biased towards opinions that initially seem popular. This project aims to improve our understanding of how social networks aggregate information. We focus on how to avoid problems like "herding", where the agents make decisions based solely on what a few earlier agents' opinions, ignoring their own observations. Even if agents in a network undergoing herding are still choosing an opinion that is more likely than not to be correct, once they start ignoring their own observations, they stop sharing their individual observations, which prevents the group from further reducing uncertainty. We also aim to study how to aggregate information in a way that is robust against adversarial agents, who might try to deliberately spread false information to the network.
Principal Investigator
DIMACS REU Undergraduate Collaborators
Easley, D., & Kleinberg, J. (2010). Networks, crowds, and markets: Reasoning about a highly connected world (Vol. 1). Cambridge: Cambridge university press.
Proskurnikov, A. V., & Tempo, R. (2017). A tutorial on modeling and analysis of dynamic social networks. Part I. Annual Reviews in Control, 43, 65-79.
Proskurnikov, A. V., & Tempo, R. (2018). A tutorial on modeling and analysis of dynamic social networks. Part II. Annual Reviews in Control, 45, 166-190.
Golub, B., & Sadler, E. (2017). Learning in social networks. Available at SSRN 2919146.
Bahar, G., Arieli, I., Smorodinsky, R., & Tennenholtz, M. (2020). Multi-issue social learning. Mathematical Social Sciences, 104, 29-39.
Arieli, I., Babichenko, Y., Talgam-Cohen, I., & Zabarnyi, K. (2023). A Random Dictator Is All You Need. arXiv preprint arXiv:2302.03667.
Hązła, J., Jadbabaie, A., Mossel, E., & Rahimian, M. A. (2021). Bayesian decision making in groups is hard. Operations Research, 69(2), 632-654.
Hązła, J., Jadbabaie, A., Mossel, E., & Rahimian, M. A. (2019, June). Reasoning in Bayesian opinion exchange networks is PSPACE-hard. In Conference on Learning Theory (pp. 1614-1648). PMLR.
Gehrlein, W. V. (2006). Condorcet’s paradox (pp. 31-58). Springer Berlin Heidelberg.
Emerson, P. (2013). The original Borda count and partial voting. Social Choice and Welfare, 40(2), 353-358.
Nurmi, H., & Palha, R. P. (2021). A theoretical examination of the ranked choice voting procedure. In Transactions on Computational Collective Intelligence XXXVI (pp. 1-16). Berlin, Heidelberg: Springer Berlin Heidelberg.
Did not read any new material this week, just worked on my own proofs, occasionally referencing materials from previous weeks.
Prelec, D., Seung, H. S., & McCoy, J. (2017). A solution to the single-question crowd wisdom problem. Nature, 541(7638), 532-535.
Behrens, F., Hudcová, B., & Zdeborová, L. (2023). Backtracking dynamical cavity method. Physical Review X, 13(3), 031021.
Franzke, M., Emrich, T., Züfle, A., & Renz, M. (2018). Pattern search in temporal social networks. In Proceedings of the 21st International Conference on Extending Database Technology.
No new references this week, just worked on my own contributions while occasionally referencing papers I read in previous weeks.
Arrived at Rutgers Busch Campus and moved into appartment. Met an amazing cast of fellow REU participants, and socialized through pizza party and orientation events. Had first in-person meeting with Prof. Gao to and her Ph.D. student, Kevin Lu to discuss an overview of the problem setting, their existing work, and future directions for us to explore. Began to read up on relevant literature on social networks, graph theory, and opinion dynamics. This reading included several papers and a textbook, which will be linked in the references section. Set up this website to keep track of the project.
Gave a slide show presentation on our problem setting and goals to DIMACS REU coordinators and fellow participants. Continued to review literature on research related to learning in social networks (see References for list of papers). Began to focus with collaborators on studying the computational complexity of determining whether a decision order exists for that allows asymptotic truth learning for a given family of graphs. Also began to theorize about how to possibly extend the theory on binary truth learning problems to truth learning problems with several alternatives (choices for each agent to make). Attended several talks at the DIMACS Workshop on Modeling Randomness in Neural Network Training. Chatted with several Ph.D. students from other universities who were also attending the workshop.
Attended many math talks held at Current Trends in Mathematics: Beyond the Freshmen Horizons workshop hosted by DIMACS. Learned about research in topics ranging from the density of prime numbers to sharp Fourier restriction theory. Created a formal definition of the network learning problem which our group intends to prove is NP-hard. Tried (largely unsuccessfully) to find relevant literature on voting theory. Began to make progress on studying the impact of adversarial "commoners" on the ability of a celebrity network to learn the truth.
Extended progress made last week on celebrity network to settings with O(N) adversaries, making progress towards showing that all non-adversarial agents can learn the truth in such settings. Began to study the impacts of adversarial agents on the Butterfly network. Prepared and gave a presentation about my home state of Minnesota for the REU program's Culture Day event, where participants gave presentations about cultures they belong to (see Presentations and Papers section for the slides). Had an ice cream social and a potluck with other REU participants.
Continued to work on proof that the celebrity network can have arbitrarily high efficiency for non-adversarial agents, when O(N) of the commoners are adversaries. Found some useful lower bounds on learning rates of agents influenced by adversaries in the binary Butterfly network. Wrote python scrips to model the Butterfly Network. Read up on other related work, particularly on truth learning in settings where private signals are most likely incorrect. Attended a talk on game theory by Professor Martin Loebl, and a workshop on scientific writing.
Found a surprising property of the butterfly network that seems to give insights into what arrangements of adversaries can have the most impact on network learning. Prepared and gave a brief presentation on research progress for visiting researchers from the NYC Discrete Math REU NYC Discrete Math REU. Dealt with an illness during this week, but also got to visit Philidelphia with family who visited.
Finished writing up my proof that the celebrity network is robust against O(N) adversaries, and shared it with my collaborators for feedback. Investigated relaxations of the butterfly network I've been investigating, one in which the edges are randomly matched, and one in which the adversaries do not know the ground truth, instead reporting whichever option is less likely to be true. Visited Nokia Bell Labs on a field trip with the DIMACS REU. I learned a lot about what research looks like in industry labs from this trip, and got to go inside an anechoic chamber, a very unique experience.
This work made possible by the Rutgers DIMACS REU program. Thank you to faculty and staff who work to keep the program running. Thank you as well to the National Science Foundation for funding this project through the grant CNS-2150186 and the REU supplement to NSF 2208663 -Collaborative Research: AF: Small: Promoting Social Learning Amid Interference in the Age of Social Media. Thank you as well to Professor Jie Gao for her help and leadership on this project.
In this section I will talk about random stuff I did/thought about while living in and exploring the area around Piscataway, NJ
I have played very little basketball in the last 7 years, but I've started playing with other REU participants and other people in the College Avenue Gym. Here is where I plan to keep track of my improvement
Session 1: Felt very rusty, especially in terms of shooting, but I hussled better than I expected. Baskets made: 1; Rating of Offensive Performance: 4/10, Rating of Defensive Performance: 5/10
Session 2: Started to feel more confident, especially with defense and rebounds. Baskets made: 3; Rating of Offensive Performance: 5.5/10, Rating of Defensive Performance: 6.5/10
Session 3: I felt like I was playing with a more competitive group this time. I didn't get the ball much on offense, but I feel like that's partly because I should've hussled more. I got a lot of rebounds, which felt good. Baskets made: 1, Rating of Offensive Performance: 4.5/10, Rating of Defensive Performance: 5.5/10
Session 4 (shooting hoops only): This time I went alone just to practice shooting. I felt like I got a lot better at shooting from various distances and angles from these reps. It felt like I made a lot more of my shots than I have in past sessions, but curiously it also felt like I missed by wide margins quite often. Baskets made: a lot? (didn't count), Rating of Offensive Performance: 6/10, Rating of Defensive Performance: N/A
Session 5 (shooting hoops only): I went alone again just to practice shooting hoops. My aim felt kinda off, but I felt like I had a lot more near misses compared to last time, when most of my misses weren't very close. I feel now that I'll need to work on my form in order to improve much more at shooting. I felt kinda like I wasn't using my left hand properly to guide my shots. That being said, shooting hoops has started to feel very calming and therapeutic, which is nice. Baskets made: a lot? (didn't count), Rating of Offensive Performance: 5.8/10, Rating of Defensive Performance: N/A
I've started going somewhat regularly to a sports pub in New Brunswick called Destination Dogs. Here I am going to keep track of my opinions on various menu items I've tried.
Paul Bunyan (MSP): This dog is basically a full breakfast on a hotdog bun. The sausage is great, I kinda wish the egg was less runny, the breakfast potatos were nice and crispy.
Rating (with Minnesota Bias) 10/10. Rating (more objectively) 8.8/10
Brat Favre (GRB): This brat has a lot going on, and while it was great, I think that the saurkraut overpowered the cheese curds too much. I love saurkraut, but to effectively capture the spirit of Green Bay, they should've made the cheese curds the star of the show.
Rating (with Minnesota Bias) 1.0/10. Rating (more objectively) 8.5/10
Andouille Armstrong (MSY): The fried shrip pairs heavenly well with the sauces and toppings on this dog. The alligator-shrip sausage itself was good, but not quite as spicy as I expected from something with Andouille in the title.
Rating: 8.7/10
Cyclone Detroit (DTW): This is the first menu item I had that included a regular hot dog. The hot dog itself was surprisingly good, but the star of this show was the chili, which is paired well with the many scallions they top it with. I can imagine Sonic the Hedgehog loving this. I also like a good chili dog, and this is a good chili dog, but I tend to prefer their other menu items which are more original and creative.
Rating: 8.1/10
Fried Cheese Curds: They did well on these, better even than a lot of places in the midwest. I would rank them above Culvers but below the Minnesota State Fair cheese curds.
Rating: 8.2/10
Nachos: Decent Nachos, but could've been layered better so that the toppings were more evenly distributed. Would've benefitted from meat options other than ground beef (such as shredded chicken).
Rating: 7.0/10
Fries: Agressively salty, in the best possible way, while also being quite thin and crispy. Exactly the sort of fries I would want to pair with their other items. Eat them while they're hot.
Rating: 8.9/10
Truffle Fries: Ridiculously good, surprisingly robust truffle flavor brought out by plenty of salt. I thought the regular fries were good, but after trying the truffle fries I don't plan on going back.
Rating: 9.7/10