提出兼顾多群体公平与评分函数稳定性的新方法,解决复杂场景下的公平选择难题。
Generalizing Fair Top-$k$ Selection: An Integrative Approach
- 设计双路径算法,同时优化多群体公平性与参考评分的差异度
- 证明小规模 $k$ 下问题可解,但群体数增加会引发计算不可行性
- 引入效用损失度量,提升对权重微小变化的鲁棒性,适合实际部署
公平顶-$k$ 选择关注如何在前 $k$ 名候选人中合理体现少数或历史弱势群体的比例。本文研究在多个受保护群体下,寻找一个公平的线性评分函数,同时最小化其与参考评分函数的差异。该设定扩展了以往仅限单一群体且不考虑差异最小化的框架。尽管已有研究认为群体数量对效率影响有限,但实验探索发现这一假设忽略了影响公平结果的关键问题。经修正后,我们的硬度分析表明,即使在二维数据集和较小的 $k$ 值下,问题也可能变得计算上不可行。然而,分析也揭示了硬度边界中的间隙,使得当群体数较小时,小 $k$ 情况仍可高效求解。此外,我们提出一种替代差异度量——效用损失,其在权重微小扰动下能生成更稳定的评分函数。通过权衡实现复杂度、鲁棒性与性能,所提出的增强型双路径方案在真实数据集上表现出色,实验结果也反哺了算法设计与实现决策。
原文摘要 · Abstract (English)
Fair top-$k$ selection, which ensures appropriate proportional representation of members from minority or historically disadvantaged groups among the top-$k$ selected candidates, has drawn significant attention. We study the problem of finding a fair (linear) scoring function with multiple protected groups while also minimizing the disparity from a reference scoring function. This generalizes the prior setup, which was restricted to the single-group setting without disparity minimization. Previous studies imply that the number of protected groups may have a limited impact on the runtime efficiency. However, driven by the need for experimental exploration, we find that this implication overlooks a critical issue that may affect the fairness of the outcome. Once this issue is properly considered, our hardness analysis shows that the problem may become computationally intractable even for a two-dimensional dataset and small values of $k$. However, our analysis also reveals a gap in the hardness barrier, enabling us to recover the efficiency for the case of small $k$ when the number of protected groups is sufficiently small. Furthermore, beyond measuring disparity as the "distance" between the fair and the reference scoring functions, we introduce an alternative disparity measure$\unicode{x2014}$utility loss$\unicode{x2014}$that may yield a more stable scoring function under small weight perturbations. Through careful engineering trade-offs that balance implementation complexity, robustness, and performance, our augmented two-pronged solution demonstrates strong empirical performance on real-world datasets, with experimental observations also informing algorithm design and implementation decisions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。