A New Notion of Individually Fair Clustering: $\alpha$-Equitable $k$-Center

Abstract

Clustering is a fundamental problem in unsupervised machine learning, and fair variants of it have recently received significant attention due to its societal implications. In this work we introduce a novel definition of individual fairness for clustering problems. Specifically, in our model, each point $j$ has a set of other points ${\mathcal{S}}_j$ that it perceives as similar to itself, and it feels that it is fairly treated if the quality of service it receives in the solution is $\alpha$-close (in a multiplicative sense, for a given $\alpha \ge 1$) to that of the points in ${\mathcal{S}}_j$. We begin our study by answering questions regarding the structure of the problem, namely for what values of $\alpha$ the problem is well-defined, and what the behavior of the \emph{Price of Fairness (PoF)} for it is. For the well-defined region of $\alpha$, we provide efficient and easily-implementable approximation algorithms for the $k$-center objective, which in certain cases enjoy bounded-PoF guarantees. We finally complement our analysis by an extensive suite of experiments that validates the effectiveness of our theoretical results.

To appear at AISTATS 2022

References in corpus (7)

• Clustering without Over-Representation
• Automated Experiments on Ad Privacy Settings: A Tale of Opacity, Choice, and Discrimination
• Scalable Fair Clustering
• Individual Fairness for $k$-Clustering
• A Notion of Individual Fairness for Clustering
• Distributional Individual Fairness in Clustering
• A Pairwise Fair and Community-preserving Approach to k-Center Clustering