↗ OpenReview ↗ NeurIPS Homepage ↗ Chat
TL;DR#
Fairness in clustering is a critical issue, particularly when data points represent individuals. Existing research explored individual fairness (each individual is close to a cluster center) and proportional fairness (no large group is far from a desirable center). However, these notions were largely studied in isolation, lacking a unified understanding of their relationships and optimal algorithmic approaches. This created a need for unified frameworks and efficient algorithms guaranteeing both types of fairness.
This work addresses these issues by connecting fairness notions in clustering to axioms in multiwinner voting. The authors introduce metric JR (mJR) and metric PJR (mPJR) axioms, demonstrating their connections to existing fairness measures. They prove that algorithms satisfying mJR achieve state-of-the-art approximations for both individual and proportional fairness, and mPJR provides strong guarantees for sortition settings. Importantly, these axioms provide a simple bridge between the different fairness notions and allow for efficient computation of approximately fair clusters.
Key Takeaways#
Why does it matter?#
This paper bridges the gap between seemingly disparate fairness notions in clustering, offering a novel perspective from computational social choice. It provides efficient algorithms with improved approximation guarantees and opens new avenues for research in fair and proportional clustering, particularly relevant to multiwinner voting and sortition.
Visual Insights#
This figure summarizes the relationships between different fairness notions in clustering. The left side shows how different algorithms and fairness properties relate to each other, indicating approximation guarantees. The right side illustrates a sample metric space used in the paper for examples.
Full paper#
