Research map / Learning theory and algorithms / Submodular and game algorithms
Communication, Distortion, and Randomness in Metric Voting
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Restrict deterministic reports to candidates at k ranking positions | Deterministic k-entry voting rules · Metric voting (n candidates) | worst-case distortion: distortion at least \frac{2n-k}{k} | Hurt |
| Restrict each voter's report to b bits | Deterministic communication-bounded voting rules · Metric voting (n candidates) | worst-case distortion: distortion at least \frac{2n-4}{b} - 1 | Hurt |
| Use the proposed top-k Copeland-style comparison-graph rule | Deterministic top-k voting · Metric voting (n candidates) | worst-case distortion: distortion at most \frac{79n}{k} | Helped |
| Mix Proportional to Squares with Random Dictatorship at the stated probabilities | Randomized first-choice voting · Metric voting (n candidates) | expected distortion: 3-\frac{2}{n} | Helped |
Closest papers by meaning
- An Analysis Framework for Metric Voting based on LP Duality (AAAI 2020 · similarity 0.94)
- Tight Bounds on the Distortion of Randomized and Deterministic Distributed Voting (NeurIPS 2025 · similarity 0.92)
- Metric Distortion of Line-up Elections: The Right Person for the Right Job (AAAI 2025 · similarity 0.91)
- On the Distortion of Committee Election with 1-Euclidean Preferences and Few Distance Queries (AAAI 2025 · similarity 0.91)
- Improved Metric Distortion via Threshold Approvals (AAAI 2024 · similarity 0.90)
- Constant-Factor Distortion Mechanisms for k-Committee Election (AAAI 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.