Research map / Learning theory and algorithms / Clustering
Proportional Fairness in Clustering: A Social Choice Perspective
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.
Shows that clusterings satisfying a metric version of justified representation (mJR) simultaneously achieve the best known approximations to proportional fairness, individual fairness and the transferable core, and that mPJR yields a 5-q-core guarantee.
Problem
Proportional fairness, individual fairness, and the transferable core are studied separately in fair clustering; their formal relations and a unifying social-choice framework are missing.
Approach
Lift approval-based multiwinner proportionality axioms (JR and PJR) to metric spaces via balls of radius y (metric JR/PJR). Show that any outcome satisfying mJR gives the best known bounds for proportional fairness, individual fairness and the transferable core; proportional and individual fairness approximations are shown to transfer to each other up to small factors.
Key results
- Any alpha-proportional fair outcome is (1+alpha)-individually fair, and any beta-individually fair outcome is 2beta-proportionally fair; these bounds are tight.
- mJR outcomes are (1+sqrt2)-proportionally fair, 2-individually fair, and in the (gamma, 2gamma/(gamma-1))-transferable core.
- Any mPJR outcome lies in the 5-q-core for every q<=k; fair greedy capture is in the (3+sqrt17)/2-q-core.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| require mJR instead of only proportional fairness | clustering outcomes · Proportional fairness | approximation factor: (1 + \sqrt{2}) | Helped |
| require mJR | clustering outcomes with N ⊆ C · Individual fairness | approximation factor: 2 | Helped |
| require mJR | clustering outcomes · Transferable core | approximation factor: \frac{2\gamma}{\gamma-1} | Helped |
| require mPJR | clustering outcomes · q-core, all q ≤ k | approximation factor: 5 | Helped |
| use Fair Greedy Capture parameterized by q | sortition outcomes · q-core | approximation factor: \frac{5 + \sqrt{41}}{2} \approx 5.7 -> \frac{3 + \sqrt{17}}{2} | Helped |
| restrict the candidate set to N ∪ W and require mJR | clustering with unbounded candidate spaces · Proportional fairness | approximation factor: 3 | Helped |
| restrict the candidate set to N ∪ W and require mPJR | clustering with unbounded candidate spaces · q-core | approximation factor: 4 | Helped |
| derive proportional fairness from individual fairness | outcomes satisfying β-individual fairness with N ⊆ C · Proportional fairness | approximation factor: 2\beta -> 1 + \beta | Helped |
| use mPJR instead of the prior sortition guarantee | clustering outcomes · q-core | approximation factor: \frac{5 + \sqrt{41}}{2} -> 5 | Helped |
| use UPRF instead of mPJR | clustering outcomes with N ⊆ C · q-core | approximation factor: 5 -> 4 | Hurt |
Surprising findings
- Proportional fairness and individual fairness approximations transfer to each other up to small factors, so an instance-level lower bound for one notion also implies one for the other.
- UPRF does not imply mPJR in general, and there are outcomes satisfying UPRF but not mJR.
Limitations
- Approximation factors for proportional fairness and the q-core are not known to be optimal.
- Results for unbounded candidate sets rely on restricting centers to agents or on mJR in an augmented instance.
Experimental setup
Metrics: approximation factor
Baselines: greedy capture fair greedy capture expanding approvals
Builds on: Chen et al. 2019 proportional fairness clustering Jung et al. 2020 individual fairness Brill and Peters 2023 proportionality axioms greedy capture
Closest papers by meaning
- Maintaining Proportional Committees with Dynamic Candidate Sets (ICML 2025 · similarity 0.90)
- Proportional Fairness in Non-Centroid Clustering (NeurIPS 2024 · similarity 0.90)
- Unifying Proportional Fairness in Centroid and Non-Centroid Clustering (NeurIPS 2025 · similarity 0.89)
- Proportional Aggregation of Preferences for Sequential Decision Making (AAAI 2024 · similarity 0.88)
- Proportional Representation in Metric Spaces and Low-Distortion Committee Selection (AAAI 2024 · similarity 0.87)
- On Hierarchies of Fairness Notions in Cake Cutting: From Proportionality to Super Envy-Freeness (NeurIPS 2025 · similarity 0.87)
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.