Approximate group fairness for clustering

Abstract

We incorporate group fairness into the algorithmic centroid clustering problem, where k centers are to be located to serve n agents distributed in a metric space. We refine the notion of proportional fairness proposed in [Chen et al., ICML 2019] as core fairness, and k-clustering is in the core if no coalition containing at least n/k agents can strictly decrease their total distance by deviating to a new center together. Our solution concept is motivated by the situation where agents are able to coordinate and utilities are transferable. A string of existence, hardness and approximability results is provided. Particularly, we propose two dimensions to relax core requirements: one is on the degree of distance improvement, and the other is on the size of deviating coalition. For both relaxations and their combination, we study the extent to which relaxed core fairness can be satisfied in metric spaces including line, tree and general metric space, and design approximation algorithms accordingly.