Research map / Learning theory and algorithms / Sample complexity
Vote Until Two of You Agree: Mechanisms with Small Distortion and Sample Complexity
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 2-Agree instead of random dictatorship (m=3) | tops-only voting mechanism · Distortion upper bound, m=3 | worst-case distortion: 3 -> 2.33491 | Helped |
| use 2-Agree instead of random dictatorship (m=7) | tops-only voting mechanism · Distortion upper bound, m=7 | worst-case distortion: 3 -> 3.04310 | Hurt |
| increase number of alternatives m from 3 to 8 | 2-Agree · Distortion upper bound | worst-case distortion: 2.33491 -> 3.17817 | Hurt |
Closest papers by meaning
- Weak Strategyproofness in Randomized Social Choice (AAAI 2025 · similarity 0.88)
- Can a Few Decide for Many? The Metric Distortion of Sortition (ICML 2024 · similarity 0.86)
- Proportional Aggregation of Preferences for Sequential Decision Making (AAAI 2024 · similarity 0.86)
- Welfare Maximization in Perpetual Voting (Student Abstract) (AAAI 2024 · similarity 0.86)
- Unravelling Expressive Delegations: Complexity and Normative Analysis (AAAI 2024 · similarity 0.86)
- Computing Voting Rules with Improvement Feedback (ICML 2025 · similarity 0.86)
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.