Research map / Learning theory and algorithms / Submodular and game algorithms
Can a Few Decide for Many? The Metric Distortion of Sortition
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Theoretical study of metric distortion for sortition panels: shows uniform selection needs O(ε^-2 ln(m/ε)) agents for near-optimal ex-ante distortion, and Fair Greedy Capture gives ex-ante 1+ε with O(ε^-3 ln(m/ε)) agents plus constant (127) ex-post distortion.
Problem
Whether sortition panels selected from a population reflect the population's aggregate preferences over alternatives embedded in a metric space, measured by distortion, and how large panels must be.
Approach
Extends the representation-metric view of sortition to agents and alternatives in a shared metric space and measures panel decisions via metric distortion; shows fair selection gives distortion at most 3 and that uniform selection and Fair Greedy Capture achieve near-optimal ex-ante distortion with panel size logarithmic in the number of alternatives, with Fair Greedy Capture also bounding ex-post
Key results
- Uniform selection achieves ex-ante distortion 1+ε with panel size O(ε^-2 ln(m/ε)), matched by a lower bound of Ω(ε^-2 ln m) up to constants.
- Fair Greedy Capture guarantees ex-post distortion at most 127 for any panel size k≥3, and ex-ante distortion 1+ε with k in O(ε^-3 ln(m/ε)).
- Any deterministic mechanism has distortion at least 5 - 12k/(n+2k) - ε with two alternatives, while any fair algorithm has ex-ante distortion at most 3 - 2k/n.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use a uniformly random panel of size O(ε^{-2} ln{m/ε}) | Uniform selection · Metric instances with m alternatives | ex-ante distortion: at most 1+ε | Helped |
| Use Fair Greedy Capture with panel size O(ε^{-3} ln{m/ε}) | Fair Greedy Capture · Metric instances with m alternatives | ex-ante distortion: at most 1+ε | Helped |
| Use Fair Greedy Capture with k ≥ 3 | Fair Greedy Capture · Metric instances | ex-post distortion: at most 127 | Helped |
| Use Fair Greedy Capture with k ≤ 2 | Fair Greedy Capture · Metric instances | ex-post distortion: Ω(n) | Hurt |
| Use larger panels | Uniform selection · ESS Round 9 Austria and Adult | average distortion | Helped |
| Use Fair Greedy Capture instead of uniform selection | Sortition panels · ESS Round 9 Austria and Adult | average distortion | Helped |
| Use Fair Greedy Capture instead of uniform selection | Sortition panels · ESS Round 9 Austria and Adult | ex-post distortion | Helped |
Surprising findings
- Uniform selection has Ω(n) ex-post distortion, since it can select an unrepresentative panel with positive probability.
- Experimentally, Fair Greedy Capture consistently achieves lower distortion than uniform selection, though the paper does not prove this ex-ante ordering.
Limitations
- Gap between the constant ex-post distortion upper bound (127) and the deterministic lower bound of 5 remains open.
- Optimal alternative is defined only as the social-cost minimizer; other rules such as minimax or majority are not analyzed.
- Experiments use only two datasets with alternatives constructed from agents as proxies.
Experimental setup
Datasets: Adult ESS Round 9 Austria
Benchmarks: Adult ESS Round 9 Austria
Metrics: ex-ante distortion ex-post distortion
Baselines: uniform selection deterministic selection
Builds on: Fair Greedy Capture metric distortion random dictatorship
Closest papers by meaning
- Every Bit Helps: Achieving the Optimal Distortion with a Few Queries (AAAI 2025 · similarity 0.90)
- Improved Metric Distortion via Threshold Approvals (AAAI 2024 · similarity 0.90)
- The Panel Complexity of Sortition: Is 12 Angry Men Enough? (NeurIPS 2026 · similarity 0.89)
- Constant-Factor Distortion Mechanisms for k-Committee Election (AAAI 2025 · similarity 0.87)
- Weak Strategyproofness in Randomized Social Choice (AAAI 2025 · similarity 0.86)
- Envy-Free House Allocation under Uncertain Preferences (AAAI 2024 · 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.