# Proportionally Representative Clustering

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 74 references that are in the map.
- First posted on arXiv 27 Apr 2023.

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

- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fair Algorithms for Clustering](https://mlsanity.com/paper/1901.02393/) (2019)
- [Scalable Fair Clustering](https://mlsanity.com/paper/1902.03519/) (2019)
- [Guarantees for Spectral Clustering with Fairness Constraints](https://mlsanity.com/paper/1901.08668/) (2019)
- [Proportionally Fair Clustering](https://mlsanity.com/paper/1905.03674/) (2019)
- [Clustering without Over-Representation](https://mlsanity.com/paper/1905.12753/) (2019)
- [Fair clustering via equitable group representations](https://mlsanity.com/paper/2006.11009/) (2020)
- [Justified Representation in Approval-Based Committee Voting](https://mlsanity.com/paper/1407.8269/) (2014)
- [Multi-Winner Voting with Approval Preferences](https://mlsanity.com/paper/2007.01795/) (2020)
- [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)
- [Probabilistic Fair Clustering](https://mlsanity.com/paper/2006.10916/) (2020)
- [Better Algorithms for Individually Fair k-Clustering](https://mlsanity.com/paper/2106.12150/) (2021)
- [A Pairwise Fair and Community-preserving Approach to k-Center Clustering](https://mlsanity.com/paper/2007.07384/) (2020)
- [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)
- [Fair Clustering Under a Bounded Cost](https://mlsanity.com/paper/2106.07239/) (2021)
- [Mechanism Design for Facility Location Problems: A Survey](https://mlsanity.com/paper/2106.03457/) (2021)
- [Fair mixing: the case of dichotomous preferences](https://mlsanity.com/paper/1712.02542/) (2017)
- [How to Solve Fair k-Center in Massive Data Models](https://mlsanity.com/paper/2002.07682/) (2020)
- [Proportionally Representative Participatory Budgeting with Ordinal Preferences](https://mlsanity.com/paper/1911.00864/) (2019)
- [Approval-Based Apportionment](https://mlsanity.com/paper/1911.08365/) (2019)
- [Approximate Group Fairness for Clustering](https://mlsanity.com/paper/2203.17146/) (2022)
- [Almost Group Envy-free Allocation of Indivisible Goods and Chores](https://mlsanity.com/paper/1907.09279/) (2019)
- [Whither Fair Clustering?](https://mlsanity.com/paper/2007.07838/) (2020)
- [Rank Maximal Equal Contribution: a Probabilistic Social Choice Function](https://mlsanity.com/paper/1705.00544/) (2017)
- [Core-Stable Committees under Restricted Domains](https://mlsanity.com/paper/2108.01987/) (2021)
- [A characterization of proportionally representative committees](https://mlsanity.com/paper/2002.09598/) (2020)
- [Proportionality and Strategyproofness in Multiwinner Elections](https://mlsanity.com/paper/2104.08594/) (2021)

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

- [Proportional Fairness in Clustering: A Social Choice Perspective](https://mlsanity.com/paper/2310.18162/) (2023)
- [Proportional Fairness in Non-Centroid Clustering](https://mlsanity.com/paper/2410.23273/) (2024)
- [Question the Questions: Auditing Representation in Online Deliberative Processes](https://mlsanity.com/paper/2511.04588/) (2025)
- [Proportional Selection in Networks](https://mlsanity.com/paper/2502.03545/) (2025)
- [Fair Transit Stop Placement: A Clustering Perspective and Beyond](https://mlsanity.com/paper/2602.06776/) (2026)
- [Temporal Panel Selection in Ongoing Citizens' Assemblies](https://mlsanity.com/paper/2602.16194/) (2026)
- [Optimally Selecting Representative Agents from a Metric Space](https://mlsanity.com/paper/2608.29097/) (2026)
- [Social Choice Foundations for Simulation-Augmented Generation](https://mlsanity.com/paper/2609.38287/) (2026)

## Abstract (arXiv)

In recent years, there has been a surge in effort to formalize notions of fairness in machine learning. We focus on centroid clustering--one of the fundamental tasks in unsupervised machine learning. We propose a new axiom ``proportionally representative fairness'' (PRF) that is designed for clustering problems where the selection of centroids reflects the distribution of data points and how tightly they are clustered together. Our fairness concept is not satisfied by existing fair clustering algorithms. We design efficient algorithms to achieve PRF both for unconstrained and discrete clustering problems. Our algorithm for the unconstrained setting is also the first known polynomial-time approximation algorithm for the well-studied Proportional Fairness (PF) axiom. Our algorithm for the discrete setting also matches the best known approximation factor for PF.