- Distortion Optimization in Utility and Dice
- Project Year:
2025
- REU Student (s):
Jasdeep Sidhu | Stanford University CA
- Student 1 Institution:
Stanford University
- Project Mentor:
Kangning Wang
- Project Mentor Area:
Computer Science
- Project Abstract:
We studied the distortion of randomized voting rules under mild utility assumptions, focusing on settings where utilities are bounded below by 1 and above by a parameter $d$. We first prove a lower bound showing that the distortion of the uniform distribution over candidates can be as large as $Omega(sqrt{d})$, even when preferences are cyclic. We then match this with an upper bound: in the committee selection setting, any $alpha$-approximately stable committee of size $k = lfloor sqrt{d}
floor$, when paired with a uniform lottery over its members, achieves distortion at most $O(sqrt{d})$. Additionally, we explored two extensions based on dice-induced utility models, where one candidate receives utility from a discrete distribution (interpreted as a die roll) and the others receive uniformly random utility. In the first direction, we investigated how to minimize distortion with respect to the Nash social welfare under such dice-generated utilities. In the second, we tried to construct families of dice whose induced utility distributions yield a uniform ranking over the special candidate. Our work hope to open new paths for bounding distortion in probabilistic social choice.
