Metric-distortion bounds under limited information

DOI10.1007/978-3-030-85947-3_20MaRDI QIDQ2670934zbMATH OpenOpenAlexFDO

Authors Ioannis Anagnostides, Dimitris Fotakis, Panagiotis Patsilinakos

Publication date 1 June 2022

Full work available at URL https://arxiv.org/abs/2107.02489

zbMATH Keywords

incomplete rankingsmetric distortionpairwise comparisonssamplingsocial choice

Mathematics Subject Classification ID

Voting theory (91B12) Social choice (91B14)

Abstract: 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 $mathcalO(logm)$ while eliciting only $m-1$ out of $Theta(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 cite{DBLP:conf/aaai/000120a}. 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 $6m/k+1$ on the distortion, for any $kin1,2,dots,m$. Thus, we substantially improve over the previous bound of $12m/k$ recently established by Kempe cite{DBLP:conf/aaai/000120a,DBLP:conf/aaai/000120b}, 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 $Theta(m/epsilo{n}^2)$ voters suffices to guarantee distortion $3+epsilon$ with high probability, for any sufficiently small $epsilon>0$. This result is based on analyzing the sensitivity of the deterministic mechanism introduced by Gkatzelis, Halpern, and Shah cite{DBLP:conf/focs/Gkatzelis0020}. Importantly, all of our sample-complexity bounds are distribution-independent.

Recommendations

• Awareness of voter passion greatly improves the distortion of metric social choice
• Approximating optimal social choice under metric preferences
• The distortion of distributed voting
• The distortion of distributed voting
• Peeking behind the ordinal curtain: improving distortion via cardinal queries

Cites work

• Approximating optimal social choice under metric preferences
• scientific article; zbMATH DE number 3106184 (Why is no real title available?)
• Lower bounds for sampling algorithms for estimating the average
• Optimal social choice functions: a utilitarian view
• Ordinal approximation for social choice, matching, and facility location problems given candidate positions
• Peeking behind the ordinal curtain: improving distortion via cardinal queries
• Randomized social choice functions under metric preferences
• Social welfare in one-sided matchings: random priority and beyond
• Subset selection via implicit utilitarian voting
• The Copeland method. I: Relationships and the dictionary
• The distortion of distributed voting
• Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship

Cited in

(7)

• Peeking behind the ordinal curtain: improving distortion via cardinal queries
• Metric-Distortion Bounds under Limited Information
• The distortion of distributed metric social choice
• The distortion of distributed metric social choice
• Tight distortion bounds for distributed metric voting on a line
• Approximating optimal social choice under metric preferences
• Awareness of voter passion greatly improves the distortion of metric social choice

This page was built for publication: Metric-distortion bounds under limited information

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2670934)