Proportionally Fair Clustering
This addresses fairness in clustering for machine learning applications without relying on predefined protected groups, though it is incremental in extending existing fair ML literature.
The paper tackles the problem of ensuring proportional fairness in centroid clustering by defining that any group of n/k points can form their own cluster if a closer center exists, and it presents algorithms to compute and optimize such solutions while examining trade-offs with the k-means objective.
We extend the fair machine learning literature by considering the problem of proportional centroid clustering in a metric context. For clustering $n$ points with $k$ centers, we define fairness as proportionality to mean that any $n/k$ points are entitled to form their own cluster if there is another center that is closer in distance for all $n/k$ points. We seek clustering solutions to which there are no such justified complaints from any subsets of agents, without assuming any a priori notion of protected subsets. We present and analyze algorithms to efficiently compute, optimize, and audit proportional solutions. We conclude with an empirical examination of the tradeoff between proportional solutions and the $k$-means objective.