Publications

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 - \varepsilon$ for some absolute constant $\varepsilon > 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.

We study Weaver’s discrepancy for \(n\) independent and identically distributed Gaussian random vectors in \(d\) dimensions. Weaver’s discrepancy for a list of vectors is defined as the minimum operator norm of the signed sum of the vectors’ outer products among all possible sign choices. First, we establish that when \(d = O(1)\), with probability at least \(0.99\), Weaver’s discrepancy is \(\Theta (\sqrt {n} 2^{-\frac {2n}{d(d+1)}})\). Second, we demonstrate that for \(\Omega (n^{2/3}) = d=O(n)\), Weaver’s discrepancy is \(\Omega (d)\), and for \(\Omega (n^{0.01}) = d=O(n)\), the discrepancy is \(O(\sqrt {dn})\), both with high probability; these two bounds match when \(d = \Theta (n)\). Our proofs mainly utilize the first- and second-moment methods. One exception is that for the upper bound when \(d = O(n)\), we show that independently and uniformly chosen signs achieve this upper bound with high probability.