论文标题
群集的近似群体公平性
Approximate Group Fairness for Clustering
论文作者
论文摘要
我们将群体公平性纳入算法中心聚类问题中，其中$ k $中心的位置可为$ n $ n $ n $ a的代理提供在公制空间中。我们将[Chen等人，ICML 2019]中提出的比例公平的概念提高为{\ em核心公平}，并且如果没有至少包含$ N/K $代理的$ N/K $代理的联盟可以严格降低其总距离，则可以通过偏离新中心。我们的解决方案概念是由代理能够协调和公用事业可转移的情况所激发的。提供了一串存在，硬度和近似性结果。特别是，我们提出了两个维度来放松核心要求的维度：一个是在距离的程度上，另一个是偏离联盟的大小。对于放松及其组合，我们研究了在包括线路，树和一般度量空间在内的度量空间中满足放松的核心公平性的程度，并相应地设计近似算法。
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 {\em 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.
