Spotlight
Fair Clustering Through Fairlets
Flavio Chierichetti · Ravi Kumar · Silvio Lattanzi · Sergei Vassilvitskii

Wed Dec 6th 05:50 -- 05:55 PM @ Hall A
in Reinforcement Learning, Algorithms, Applications »
We study the question of fair clustering under the {\em disparate impact} doctrine, where each protected class must have approximately equal representation in every cluster. We formulate the fair clustering problem under both the $k$-center and the $k$-median objectives, and show that even with two protected classes the problem is challenging, as the optimum solution violates common conventions---for instance a point may no longer be assigned to its nearest cluster center! En route we introduce the concept of fairlets, which are minimal sets that satisfy fair representation while approximately preserving the clustering objective. We show that any fair clustering problem can be decomposed into first finding appropriate fairlets, and then using existing machinery for traditional clustering algorithms. While finding good fairlets can be NP-hard, we proceed to obtain efficient approximation algorithms based on minimum cost flow. We empirically demonstrate the \emph{price of fairness} by comparing the value of fair clustering on real-world datasets with sensitive attributes.

Author Information

Flavio Chierichetti (Sapienza University)
Ravi Kumar (Google)
Silvio Lattanzi (Google)
Sergei Vassilvitskii (Google)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors