Distortion of Metric Voting with Bounded Randomness
Speaker
Ziyi Cai, Rutgers University
Time
2026-05-11 10:00:00 ~ 2026-05-11 11:30:00
Location
软件学院专家楼 1319室
Host
张宇昊
Abstract
We study the design of voting rules in the metric distortion framework. It is known that any deterministic rule suffers distortion of at least 3, and that randomized rules can achieve distortion strictly less than 3, often at the cost of reduced transparency and interpretability. In this work, we explore the trade-off between these paradigms by asking whether it is possible to break the distortion barrier of 3 using only "bounded" randomness. We answer in the affirmative by presenting a voting rule that (1) achieves distortion of at most 3−ε for some absolute constant ε>0, and (2) selects a winner uniformly at random from a deterministically identified list of constant size. Our analysis builds on new structural results for the distortion and approximation of Maximal Lotteries and Stable Lotteries.
Bio
Ziyi Cai is a third-year Ph.D. candidate in Computer Science at Rutgers University, where he is fortunate to be advised by Prof. Peng Zhang. Previously, he obtained a bachelor’s degree in Computer Science from Shanghai Jiao Tong University, ACM class. His research focuses on computational social choice.