Jasdeep Sidhu

About Me

Hello! I'm Jasdeep Sidhu, a mathematics major at Stanford. My academic interests include theoretical computer science, cryptography, and combinatorics. During this summer, I hope to develop both theoretical insights and practical algorithms that contribute to our understanding of fairness and efficiency in decision-making processes.Outside of academics, I enjoy playing basketball, watching movies, dancing, drinking chai, and exploring clever puzzles.

Weekly Log

• Week 1 (05/27 - 05/30): 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.
• Week 2 (06/02 - 06/06): 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.
• Week 3 (06/09 - 06/13): 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.
• Week 4 (06/16 - 06/20): 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.
• Week 5 (06/23 - 06/27): 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.
• Week 6 (06/30 - 07/04): 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.
• Week 7 (07/07 - 07/11): 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.

Acknowledgements

This research is supported by the DIMACS REU program and the NSF. Thanks to my mentor Professor Kangning Wang and the DIMACS staff for their guidance and support.