Ranking with Fairness Constraints
Ranking with Fairness Constraints
复制标题
DOI：
10.4230/lipics.icalp.2018.28
复制
发表时间：
2017-04
期刊：
影响因子：
--
通讯作者：
L. E. Celis;D. Straszak;Nisheeth K. Vishnoi
中科院分区：
文献类型：
--
作者：
L. E. Celis;D. Straszak;Nisheeth K. Vishnoi
在搜索引擎、新闻提要和推荐系统等应用程序中，广泛部署了排序算法来对一组项目进行排序。然而，最近的研究表明，如果不加以控制，排名算法的输出可能会导致所呈现内容类型的多样性降低，助长刻板印象，并使意见两极分化。为了解决这些问题，我们研究了当存在公平性或多样性约束时，传统排名问题的以下变体。给定条目集合以及1)将条目放置在排名中的特定位置的值，2)每个条目的敏感属性(诸如性别、种族、政治观点)的集合，以及3)对于每个k，将允许出现在排名的前k个位置的条目的数量与每个属性绑定的约束集合，目标是输出相对于原始排名质量度量最大化该值的排名，同时尊重这些约束。这个问题将与二部图和超图匹配相关的各种研究得很好的问题封装为特例，即使有简单的约束也很难逼近。我们的主要技术贡献是快速的精确和近似算法以及互补的硬度结果，这些结果结合在一起，接近于解决这个约束排序最大化问题的可逼近性。与以往关于约束匹配问题的工作不同，该算法在线性时间内运行，即使在约束个数较大的情况下，其近似比也不依赖于约束个数，并且它产生的解的约束违反量很小。我们的结果依赖于对约束匹配问题的见解，当目标满足常见排名指标中出现的属性时，如折扣累积收益、Spearman的Rho或Bradley-Terry。
Ranking algorithms are deployed widely to order a set of items in applications such as search engines, news feeds, and recommendation systems. Recent studies, however, have shown that, left unchecked, the output of ranking algorithms can result in decreased diversity in the type of content presented, promote stereotypes, and polarize opinions. In order to address such issues, we study the following variant of the traditional ranking problem when, in addition, there are fairness or diversity constraints. Given a collection of items along with 1) the value of placing an item in a particular position in the ranking, 2) the collection of sensitive attributes (such as gender, race, political opinion) of each item and 3) a collection of constraints that, for each k, bound the number of items with each attribute that are allowed to appear in the top k positions of the ranking, the goal is to output a ranking that maximizes the value with respect to the original rank quality metric while respecting the constraints. This problem encapsulates various well-studied problems related to bipartite and hypergraph matching as special cases and turns out to be hard to approximate even with simple constraints. Our main technical contributions are fast exact and approximation algorithms along with complementary hardness results that, together, come close to settling the approximability of this constrained ranking maximization problem. Unlike prior work on the constrained matching problems, our algorithm runs in linear time, even when the number of constraints is large, its approximation ratio does not depend on the number of constraints, and it produces solutions with small constraint violations. Our results rely on insights about the constrained matching problem when the objective satisfies properties that appear in common ranking metrics such as Discounted Cumulative Gain, Spearman's rho or Bradley-Terry.