Metric-Distortion Bounds under Limited Information
share
In this work we study the metric distortion problem in voting theory under a limited amount of ordinal information. Our primary contribution is threefold. First, we consider mechanisms which perform a sequence of pairwise comparisons between candidates. We show that a widely-popular deterministic mechanism employed in most knockout phases yields distortion 𝒪(log m) while eliciting only m-1 out of Θ(m^2) possible pairwise comparisons, where m represents the number of candidates. Our analysis for this mechanism leverages a powerful technical lemma recently developed by Kempe <cit.>. We also provide a matching lower bound on its distortion. In contrast, we prove that any mechanism which performs fewer than m-1 pairwise comparisons is destined to have unbounded distortion. Moreover, we study the power of deterministic mechanisms under incomplete rankings. Most notably, when every agent provides her k-top preferences we show an upper bound of 6 m/k + 1 on the distortion, for any k ∈{1, 2, …, m}. Thus, we substantially improve over the previous bound of 12 m/k recently established by Kempe <cit.>, and we come closer to matching the best-known lower bound. Finally, we are concerned with the sample complexity required to ensure near-optimal distortion with high probability. Our main contribution is to show that a random sample of Θ(m/ϵ^2) voters suffices to guarantee distortion 3 + ϵ with high probability, for any sufficiently small ϵ > 0. This result is based on analyzing the sensitivity of the deterministic mechanism introduced by Gkatzelis, Halpern, and Shah <cit.>. Importantly, all of our sample-complexity bounds are distribution-independent.
READ FULL TEXT