Proportional Fairness in Clustering: A Social Choice Perspective
This work addresses fairness in clustering for machine learning applications, providing theoretical connections and approximations, but it is incremental as it builds on existing notions from prior research.
The paper tackles the problem of achieving proportional fairness in clustering by relating it to multiwinner voting in social choice, showing that a weak proportionality notion yields the best known approximations for proportional fairness, individual fairness, and the core, and also extends to stronger representation notions with multiple candidate centers.
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.