Research map / Learning theory and algorithms / Submodular and game algorithms
Proportional Representation in Metric Spaces and Low-Distortion Committee Selection
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.
Defines a proportional-representation criterion for committees in metric spaces and shows the Expanding Approvals Rule achieves (α, 1+6.71·α/(α−1))-representation even with only ordinal rankings.
Problem
Selecting a small representative committee from a larger set in a metric space so that large cohesive groups are represented proportionally to their size, with ordinal (ranking-only) information in election settings.
Approach
A strengthened core-style definition requiring proportional representation for all coalitions of size at least t·α·p (with t best representatives), analyzed for the Expanding Approvals Rule under the ordinal model with resource augmentation; a truncated Greedy Capture variant gives better constants with known distances.
Key results
- Expanding Approvals Rule is (α, 1+((7+√41)/2)·α/(α−1)) ≈ (α, 1+6.71·α/(α−1))-proportionally representative under ordinal information.
- Expanding Approvals Rule is 5.71-proportionally fair under ordinal information, the first such constant-factor result with metric costs in that model.
- A single-winner voting rule derived from the analysis has metric distortion at most 44.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Expanding Approvals Rule with ordinal rankings and resource augmentation α > 1 | Committee selection in metric spaces · Metric spaces (ordinal) | representativeness approximation factor γ: 1 + 7+√41/2 · α/(α−1) ≈ 1 + 6.71 · α/(α−1) | Helped |
| Use Expanding Approvals Rule without resource augmentation | Committee selection in metric spaces · Metric spaces (ordinal), α = 1 | representativeness approximation factor γ: O(n/k) | Helped |
| Use ordinal rankings with Expanding Approvals Rule | Proportionally fair clustering · Metric spaces (ordinal) | proportional fairness factor: 5+√41/2 ≈ 5.71 | Helped |
| Use ordinal information rather than full metric knowledge | Proportionally fair clustering · Metric spaces | proportional fairness factor: 1 + √2 ≈ 2.41; 5+√41/2 ≈ 5.71 | Hurt |
| Use Truncated Greedy Capture with known distances and α > 1 | Committee selection in metric spaces · Metric spaces (cardinal) | representativeness approximation factor γ: 1 + (2 + √2) · α/(α−1) ≈ 1 + 3.42 · α/(α−1) | Helped |
| Use the two-stage voting rule based on expanding approvals and majority choice | Single-winner elections · Single-winner elections (ordinal) | metric distortion: 44 | Helped |
| Limit the committee’s stability guarantee to a smaller size k/α | Proportional representation in metric spaces · Metric spaces | representativeness approximation factor γ: α > 1; 1 + 7+√41/2 · α/(α−1) | Mixed |
Surprising findings
- For α close to 1, a large blowup in γ (about 1/(4(α−1))) is unavoidable, so some resource augmentation is necessary.
- Under ordinal information, no deterministic algorithm can beat proportional fairness 2+√5 ≈ 4.23, showing a gap with the cardinal model.
Limitations
- Exact representativeness without resource augmentation is impossible in general; guarantees hold only for alpha > 1 or with an O(n/k) factor at alpha = 1.
- Constants in upper and lower bounds do not match.
- Single-winner distortion of 44 is worse than the optimal distortion of 3.
Experimental setup
Metrics: resource augmentation alpha representativeness approximation gamma proportional fairness constant metric distortion
Baselines: Greedy Capture approximate core of Li et al. 2021 Copeland Plurality-Matching Plurality-Veto
Builds on: Expanding Approvals Rule Greedy Capture approximate core (Li et al. 2021) proportionally fair clustering (Chen et al. 2019)
Closest papers by meaning
- Proportional Fairness in Clustering: A Social Choice Perspective (NeurIPS 2024 · similarity 0.87)
- Metric Distortion of Line-up Elections: The Right Person for the Right Job (AAAI 2025 · similarity 0.87)
- Proportional Aggregation of Preferences for Sequential Decision Making (AAAI 2024 · similarity 0.86)
- Unifying Proportional Fairness in Centroid and Non-Centroid Clustering (NeurIPS 2025 · similarity 0.85)
- Proportional Representation in Practice: Quantifying Proportionality in Ordinal Elections (AAAI 2025 · similarity 0.85)
- Verifying Proportionality in Temporal Voting (AAAI 2025 · similarity 0.85)
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.