Proportional Fairness in Clustering: A Social Choice Perspective

We study the proportional clustering problem of Chen et al. [2019, 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 [2023, EC'23] simultaneously obtains the best known approximations to the proportional fairness notion of Chen et al. [2019], but also to individual fairness [Jung et al., 2020, FORC'20] and the "core" [Li et al., 2021, 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 [2023] imply approximations to these stronger guarantees. Fair decision-making is a crucial research area in artificial intelligence. To ensure fairness, a plethora of different fairness notions, algorithms and settings have been introduced, studied, and implemented. One area in which fairness has been applied extensively is clustering. In centroid clustering, we are given a set ofndata points which we want to partition intok clusters by choosing k "centers" and assigning each point to a center by which it is represented well. Fairness now comes into play when the data points correspond to human individuals. Fairness notions in clustering usually depend on one important decision: whether demographic information (such as gender, income, etc.) is taken into account or whether one is agnostic to it. A large part of work on fair clustering has focused on incorporating such demographic information, starting with the seminal work of Chierichetti et al. [2017] who aimed to proportionally balance the number of people of a certain type in each cluster center.