REU Participant Details

This week, I focused on familiarizing myself with the mathematical foundations of intransitive dice and their role in generating cyclic preference structures within voting systems. I explored how these structures can be used to model and analyze instability in committee selection rules. Much of my time was spent reconciling these abstract concepts with examples, while also balancing academic responsibilities as my academic quarter at Stanford was still ongoing.

This week, we explored multiple probabilistic frameworks for modeling voter preferences induced by intransitive dice. One approach assumes a large number of voters, where the empirical distribution over rankings corresponds exactly to the theoretical distribution of pairwise dice outcomes. Another assumes a finite voter population, where each voter represents an independent sample from the underlying dice distribution. In this case, we would aim to make probabilistic guarantees that hold with high probability. We have chosen to initially focus on analyzing approximate core outcomes in committee selection under these models, particularly investigating whether the assumption of intransitivity can help tighten existing approximation bounds.

This week marked the end of the academic quarter at Stanford, so I balanced my time between final exams and continuing REU work. We decided to pivot from studying approximate core outcomes to focusing on the distortion of randomized voting rules. Distortion, in this context, is defined as the ratio between the optimal achievable social welfare and the welfare achieved by a given (usually randomized) distribution over candidates. I spent the week studying the paper Optimized Distortion and Proportional Fairness in Voting by Ebadian et al. and wrote a detailed summary. A key takeaway from the paper is that the authors obtain a distortion of $\Theta(\sqrt{m})$ for unit-sum utility functions and $\Theta(\log m) for Nash social welfare, where m is the number of candidates. For us, the results serve as a benchmark as we explore distortion guarantees under dice-induced preference models.

This was my first week attending the REU in person, and I'm incredibly grateful for the warm welcome from the other students and faculty despite arriving later than most. This week, we explored a variety of promising research directions for our project. We discussed the possibility of tightening distortion bounds not just in the general setting, but specifically for notions like proportional fairness and Nash social welfare. Additionally, we began thinking about foundational barriers: we reviewed Arrow’s Impossibility Theorem and speculated whether similar impossibility results could emerge when preferences are generated from dice models. We've decided to simplify the assumption of intransitive dice models to normal dice and use this model as a starting point. There are many exciting paths forward, and my goal is to identify the direction that most aligns with my interests and dive deeper there in the coming weeks.

This week, we derived a new upper bound on distortion by analyzing utility magnitude rather than the number of candidates, diverging from the standard approach in prior literature. Specifically, we showed that in the general choice setting, if $d$ denotes the maximum utility assigned to any candidate, then the distortion of an arbitrary distribution is at most $O(\sqrt{d})$. Moreover, we demonstrated that the distortion of the uniform distribution over candidates can be as large as $\Omega(\sqrt{d})$, indicating that our upper bound is asymptotically tight. Now we're exploring two complementary axes of generalization: one varies whether bounds depend on utility magnitudes or the number of candidates; the other considers whether preferences arise from standard utility profiles or from dice-induced rankings. We're also beginning to reexamine our earlier goals of analyzing proportional fairness, Nash social welfare, and approximate core outcomes under these new lenses.

This week, we narrowed our focus to two specific lower bound problems related to distortion under dice-induced utility models. The first goal is to establish a lower bound of $\Omega(m)$ on distortion in the dice-induced social welfare setting. Our strategy involves demonstrating that dice-induced preferences can still yield a nearly uniform distribution over rankings, implying that even under structured randomness, worst-case distortions remain linear in the number of candidates. The second goal is to show a lower bound of $\Omega(\log m)$ for distortion with respect to Nash social welfare. We aim to construct specific dice-based election instances that exhibit this logarithmic gap, drawing parallels to classical constructions in the literature. Both directions look promising, but still difficult nonetheless.

This week, I made progress on both of our targeted lower bound problems, though not without challenges. The first objective—constructing dice-induced preferences that yield a nearly uniform distribution over rankings—proved more difficult than anticipated. Despite experimenting with several configurations, I have yet to find a setup that exhibits the desired uniformity. I plan to continue iterating on more creative constructions next week. On the second front, I’ve made more promising headway: I developed a general idea for a dice-based construction that could lead to a logarithmic distortion gap for Nash social welfare. I’ve written up the core intuition behind the approach and begun verifying the details; the next step will be to rigorously formalize the argument and confirm the underlying calculations.

I continued exploring dice-induced utility constructions in an effort to produce a uniform distribution over rankings. Although many attempts have not yet yielded the desired behavior, I remain committed to the problem and motivated by its potential significance. Moreover, I prepared and delivered a presentation summarizing our progress, and began drafting my final research report. Outside of research, I’ve been getting ready for the upcoming trip to Prague with the other REU students which I'm very much looking forward to!

This is the final week of the REU and I'm currently in Prague attending lectures at Charles University. The topics of the lectures ranged from random graphs, space-complexity theory, and max-flow. The problem solving sessions were very fun and a nice opportunity to work together with the other REU students. I've been exploring Prague, which I really love. I finished up my final report, but still plan on continuing the research.