# Proportional Representation in Metric Spaces and Low-Distortion Committee Selection

arXiv: https://arxiv.org/abs/2312.10369 · HTML: https://mlsanity.com/paper/2312.10369/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 50 references that are in the map.
- First posted on arXiv 16 Dec 2023.

## Builds on (most cited first, 24 of 24)

- [Proportionally Fair Clustering](https://mlsanity.com/paper/1905.03674/) (2019)
- [Individual Fairness for k-Clustering](https://mlsanity.com/paper/2002.06742/) (2020)
- [Justified Representation in Approval-Based Committee Voting](https://mlsanity.com/paper/1407.8269/) (2014)
- [Proportional Participatory Budgeting with Additive Utilities](https://mlsanity.com/paper/2008.13276/) (2020)
- [Improved Approximation Algorithms for Individually Fair Clustering](https://mlsanity.com/paper/2106.14043/) (2021)
- [A Center in Your Neighborhood: Fairness in Facility Location](https://mlsanity.com/paper/1908.09041/) (2019)
- [Proportional Justified Representation](https://mlsanity.com/paper/1611.09928/) (2016)
- [Robust and Verifiable Proportionality Axioms for Multiwinner Voting](https://mlsanity.com/paper/2302.01989/) (2023)
- [A New Notion of Individually Fair Clustering: α-Equitable k-Center](https://mlsanity.com/paper/2106.05423/) (2021)
- [Distortion in Social Choice Problems: The First 15 Years and Beyond](https://mlsanity.com/paper/2103.00911/) (2021)
- [Proportional Fairness in Clustering: A Social Choice Perspective](https://mlsanity.com/paper/2310.18162/) (2023)
- [Optimized Distortion and Proportional Fairness in Voting](https://mlsanity.com/paper/2205.15760/) (2022)
- [Group Fairness in Committee Selection](https://mlsanity.com/paper/1905.04438/) (2019)
- [Resolving the Optimal Metric Distortion Conjecture](https://mlsanity.com/paper/2004.07447/) (2020)
- [Achieving Fully Proportional Representation: Approximability Results](https://mlsanity.com/paper/1312.4026/) (2013)
- [Proportionality Degree of Multiwinner Rules](https://mlsanity.com/paper/1810.08799/) (2018)
- [Approximately Stable Committee Selection](https://mlsanity.com/paper/1910.14008/) (2019)
- [The Metric Distortion of Multiwinner Voting](https://mlsanity.com/paper/2201.13332/) (2022)
- [Approximate Group Fairness for Clustering](https://mlsanity.com/paper/2203.17146/) (2022)
- [Improved Metric Distortion for Deterministic Social Choice Rules](https://mlsanity.com/paper/1905.01401/) (2019)
- [Relating Metric Distortion and Fairness of Social Choice Rules](https://mlsanity.com/paper/1810.01092/) (2018)
- [Ordinal Approximation for Social Choice, Matching, and Facility Location Problems given Candidate Positions](https://mlsanity.com/paper/1805.03103/) (2018)
- [Best of Both Distortion Worlds](https://mlsanity.com/paper/2305.19453/) (2023)
- [Distortion in metric matching with ordinal preferences](https://mlsanity.com/paper/2305.12119/) (2023)

## Built on by (most cited first, 3 of 3)

- [Full Proportional Justified Representation](https://mlsanity.com/paper/2501.12015/) (2025)
- [Fairness in Ranking: Robustness through Randomization without the Protected Attribute](https://mlsanity.com/paper/2403.19419/) (2024)
- [Temporal Panel Selection in Ongoing Citizens' Assemblies](https://mlsanity.com/paper/2602.16194/) (2026)

## Abstract (arXiv)

We introduce a novel definition for a small set R of k points being "representative" of a larger set in a metric space. Given a set V (e.g., documents or voters) to represent, and a set C of possible representatives, our criterion requires that for any subset S comprising a theta fraction of V, the average distance of S to their best theta*k points in R should not be more than a factor gamma compared to their average distance to the best theta*k points among all of C. This definition is a strengthening of proportional fairness and core fairness, but - different from those notions - requires that large cohesive clusters be represented proportionally to their size. Since there are instances for which - unless gamma is polynomially large - no solutions exist, we study this notion in a resource augmentation framework, implicitly stating the constraints for a set R of size k as though its size were only k/alpha, for alpha > 1. Furthermore, motivated by the application to elections, we mostly focus on the "ordinal" model, where the algorithm does not learn the actual distances; instead, it learns only for each point v in V and each candidate pairs c, c' which of c, c' is closer to v. Our main result is that the Expanding Approvals Rule (EAR) of Aziz and Lee is (alpha, gamma) representative with gamma <= 1 + 6.71 * (alpha)/(alpha-1). Our results lead to three notable byproducts. First, we show that the EAR achieves constant proportional fairness in the ordinal model, giving the first positive result on metric proportional fairness with ordinal information. Second, we show that for the core fairness objective, the EAR achieves the same asymptotic tradeoff between resource augmentation and approximation as the recent results of Li et al., which used full knowledge of the metric. Finally, our results imply a very simple single-winner voting rule with metric distortion at most 44.