mlsanityData to 7 Oct 2026

Proportional Fairness in Clustering: A Social Choice Perspective

arXiv 2310.18162 ↗First posted 27 Oct 2023cs.LG cs.CY cs.GTcited by 12

Not on the map. Why?

Abstract (arXiv)

We study the proportional clustering problem of Chen et al. [ICML'19] and relate it to the area of multiwinner voting in computational social choice. We show that any clustering satisfying a weak proportionality notion of Brill and Peters [EC'23] simultaneously obtains the best known approximations to the proportional fairness notion of Chen et al. [ICML'19], but also to individual fairness [Jung et al., FORC'20] and the "core" [Li et al. ICML'21]. In fact, we show that any approximation to proportional fairness is also an approximation to individual fairness and vice versa. Finally, we also study stronger notions of proportional representation, in which deviations do not only happen to single, but multiple candidate centers, and show that stronger proportionality notions of Brill and Peters [EC'23] imply approximations to these stronger guarantees.

Key facts. Cited by 12 papers in the map (data through 7 Oct 2026). Builds on 21 of its 42 references that are in the map. First posted on arXiv 27 Oct 2023.

Builds on

21 of 42 references.

References · 21

  1. 2018Fair Clustering Through Fairletscited by 176
  2. 2019Proportionally Fair Clusteringcited by 69
  3. 2020Individual Fairness for k-Clusteringcited by 56
  4. 2014Justified Representation in Approval-Based Committee Votingcited by 42
  5. 2020Multi-Winner Voting with Approval Preferencescited by 37
  6. 2020Proportional Participatory Budgeting with Additive Utilitiescited by 37
  7. 2021Improved Approximation Algorithms for Individually Fair Clusteringcited by 33
  8. 2021Better Algorithms for Individually Fair k-Clusteringcited by 28
  9. 2023Robust and Verifiable Proportionality Axioms for Multiwinner Votingcited by 23
  10. 2019Proportionality and the Limits of Welfarismcited by 21
  11. 2021A New Notion of Individually Fair Clustering: α-Equitable k-Centercited by 18
  12. 2019Group Fairness in Committee Selectioncited by 10
9 more
  1. 2019Proportionally Representative Participatory Budgeting with Ordinal Preferencescited by 9
  2. 2023Doubly Constrained Fair Clusteringcited by 9
  3. 2022Individual Preference Stability for Clusteringcited by 8
  4. 2023Proportionally Representative Clusteringcited by 8
  5. 2019Approximately Stable Committee Selectioncited by 7
  6. 2022The Metric Distortion of Multiwinner Votingcited by 7
  7. 2022Approximate Group Fairness for Clusteringcited by 7
  8. 2021Feature-based Individual Fairness in k-Clusteringcited by 4
  9. 2021Individual Representation in Approval-Based Committee Votingcited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 2; 2025: 4; 2026: 5.

12 papers.

  1. 2025Generative Social Choice: The Next Generationcited by 10
  2. 2024Proportional Fairness in Non-Centroid Clusteringcited by 6
  3. 2023Proportional Representation in Metric Spaces and Low-Distortion Committee Selectioncited by 3
  4. 2024Fair Clustering: Critique, Caveats, and Future Directionscited by 1
  5. 2025A Computational Approach to Improving Fairness in K-means Clusteringcited by 1
  6. 2025The Core in Max-Loss Non-Centroid Clustering Can Be Emptycited by 1
  7. 2026Fair Transit Stop Placement: A Clustering Perspective and Beyondcited by 1
  8. 2026Embeddings for Preferences, Not Semanticscited by 1
  9. 2025Fairness in the Multi-Secretary Problemcited by 0
  10. 2026Temporal Panel Selection in Ongoing Citizens' Assembliescited by 0
  11. 2026Optimally Selecting Representative Agents from a Metric Spacecited by 0
  12. 2026Social Choice Foundations for Simulation-Augmented Generationcited by 0