Research map / Learning theory and algorithms / Sample complexity
Random Dictators with a Random Referee: Constant Sample Complexity Mechanisms for Social Choice
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 |
|---|---|---|---|
| Use a random voter to compare two other random voters’ favorite alternatives | Random Referee · General metric spaces | Squared Distortion: 21; top-k only mechanisms have Ω(|𝒮|) | Helped |
| Use a random voter to compare two other random voters’ favorite alternatives | Random Referee · Euclidean plane, d(u, pᵤ) = 0 | Distortion: 2 -> 1.97 | Helped |
| Use three favorite queries and select a repeated favorite when one occurs; otherwise choose among the three reported favorites | Random Oligarchy · General metric spaces | Distortion: ≤3 | Helped |
| Use Random Oligarchy instead of Random Dictatorship | Favorite-only mechanisms · Small |𝒮| | Distortion | Helped |
| Use Random Oligarchy instead of 2-Agree | Favorite-only mechanisms · Large |𝒮| | Distortion | Helped |
| Restrict queries to top-k preferences rather than allowing comparisons | Social choice mechanisms · General metric spaces | Squared Distortion: Ω(|𝒮|) | Hurt |
| Use only top-k queries instead of Random Referee’s comparison query | Social choice mechanisms · Euclidean plane, d(u, pᵤ) = 0 | Distortion: 2 vs. <1.97 | Hurt |
Closest papers by meaning
- Improved Metric Distortion via Threshold Approvals (AAAI 2024 · similarity 0.90)
- Can a Few Decide for Many? The Metric Distortion of Sortition (ICML 2024 · similarity 0.89)
- Weak Strategyproofness in Randomized Social Choice (AAAI 2025 · similarity 0.89)
- Independence of Irrelevant Alternatives under the Lens of Pairwise Distortion (AAAI 2024 · similarity 0.88)
- Constant-Factor Distortion Mechanisms for k-Committee Election (AAAI 2025 · similarity 0.88)
- Reducing Leximin Fairness to Utilitarian Optimization (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.