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.
No new references this week, just worked on my own contributions while occasionally referencing papers I read in previous weeks.
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.
Prepared and gave a final presentation on my research during this program. Attended the final presentations of fellow REU participants. Began writing my final report on my research, and explored options for submitting a version of it as a paper for this year's AAMAS conference. Bid farewell to the friends I made in this program who went to Prague.
Completed my Final Report of my research this summer, incorporating feedback from my mentor, and submitted it to the DIMACS REU program coordinators. Began exploring a promising approach towards finding the expected learning rate of butterfly networks with a randomly placed, constant proportion of adversarial agents. Attended a meeting with all my mentor's Ph.D. students and Postdocs to discuss resarch problems. Submitted a reflection on my REU experience to the DIMACS REU coordinators. Returned to Minnesota.
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
Session 6: I went back with friends from the REU program to play actual games again. In the first game I played, I felt like my shooting practice paid off (I got three baskets, one of which was the game winner). I also felt like I generally played solid defense in the first game. The second game, however, was a bit of a different story, as I didn't score any points and I felt like my defense came up short regularly. I think it was mostly a stamina issue, as the gym was very hot, but one of the main things I need to work on now is consistency and hussle. Baskets scored: 3, Rating of Offensive Performance: 6.5, Rating of Defensive Performance: 6.5
Session 7: Went with friends from the REU program. Started off by shooting hoops for a while, and then played a couple 5-on-5 games. I felt much improved while shooting hoops, I even made quite a few 3-pointers, which felt very nice. During the games we played, I was matched up defensively on a guy who was quite good, but I felt like I held my own very well against him on defense. I made a couple of baskets and felt like I did a good job passing the ball around as well. I felt I again performed a bit worse in the second game due to getting tired, but I felt like I pushed myself pretty hard and did a better job of hussling. Baskets scored: 2, Rating of Offensive Performance: 6.5, Rating of Defensive Performance: 7.5
Overall, I felt like I improved quite a bit at baskeball over the summer. Most importantly, it had a fun, somewhat regular source of exercise, which I hope to keep up with once I go back home.
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
Over the course of the REU, I became a regular at a sandwich shop called RU Hungry. I tried many of the so-called fat sandwiches on their menu, and love every one. Their shakes are also amazing. When I learned that they offer an challenge to eat 5 of their fat sandwiches in under 45 minutes, where winners earn the right to create a new sandwich named after them, I felt that even though the challenge seemed insane, I had to try. My friend Todor and I entered the challenge one evening, after having given our final presentations that day and playing basketball in the gym. Going into the challenge, while we each thought that we likely wouldn't win, we thought we would at least finish 3 sandwiches in the time limit. We even brought along a sizeable group of spectators (fellow REU participants) to witness our glory.
By the time we had ordered our sandwiches, we began to realize our hubris. The sandwiches they made for the challenge were much larger than the (already sizeable) sandwiches on their normal menu, stuffed with many more fries than they normally are. The large quantity of fries made it quite difficult and slow just to finish the first sandwich, which took me 8 minutes and 30 seconds. I though at the time that, even though I was already much fuller than I expected after one sandwich, I would need to keep my pace up to have a chance at finishing in time. The second sandwich quickly crushed my dream of having a chance at finishing the challenge. It became very hard just to swallow bites of the french-fry stuffed sandwich. About halfway through it, I began to gag periodically, and worry that I would throw up. Now fully aware that my claim of being able to finish even three of these sandwich behemoths was but a pipe dream, I set my sights on just finishing my second sandwich, and to take my time to avoid throwing up. Even so, there were many times I told Todor I wanted to quit, but he pushed me to continue on to salvage some dignity by at least finishing my second sandwich. Todor was having struggles of his own, but we tried to encourage each other to keep fighting.
Unfortunately for me, the sandwiches in my stomach kept on fighting me. I tried to stop myself from gagging by taking sips of sprite. It seemed to help in the short term, but in the long term only filled the little remaining room in my stomach with gas. Afraid I would throw up, I headed to the bathroom, only to find that it was occupied! Luckily, in that moment of panic I let out a burp, which relieved my stomach somewhat, luckily without making me throw up. After sitting down for a few moments, I tried again to finish the last few bites of my second sandwich, already over halfway through my allotted time to eat 5 of them. Between each bite, I took several moments to vent with Todor about our hubris and our failure. Slowly but surely, I managed to triumphantly take my last bite of my second sandwich. For a brief moment, as spectators cheered me on, I felt that I had reclaimed my dignity. So what if I didn't get nearly as far as I thought I would? The sandwiches were stuffed with much more fries than I had ever experienced with their sandwiches, so how could I be expected to know my limits for this challenge? I felt somewhat proud of how far I'd come, considering the challenge was considerably harder than I expected it to be. That moment quickly faded as I finished chewing the last bite. When I tried to swallow it, I began to gag. At first I thought I might've gotten it under control, but before I knew it I had thrown up all over the table in front of me. What little dignity I had reclaimed left as the cashier handed me a bag and a buch of napkins to clean myself with, and I began apologizing profusely to the staff. To make matters worse, it had started to thunderstorm outside, and we had to get back on a bus that wouldn't arrive for another half hour. While my friends helped to cheer me up, I realized that this experience would be a foundational memory of how I was punished for my hubris.
To any future DIMACS REU participant, or anyone else living in the Rutgers area, heed my advice: go to RU Hungry, enjoy their wonderful sandwiches and delicious shakes, but never, ever think that you have a chance to win the challenge. You might feel brave, you might think you can eat a lot, but such thoughts are seen by the sandwich gods as the worst form of hubris. Your punishment for this hubris will be self-imposed, when you decide to buy 5 enormous sandwiches and attempt to eat them all just for a chance at sandwich immortality. You will immediately be humbled by the sandwiches, which will remind you that your body is mortal, and cannot possibly ingest so many so quickly. Even when you think you can salvage some of your pride, the sandwiches will take their revenge on you.