Proportional Fairness in Clustering: A Social Choice Perspective
Leon Kellerhals Jannik Peters
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.