The problem of ranking a set of items is a fundamental algorithmic task in today's data-driven world, and has received significant attention in computer science. Ranking algorithms lie at the core of applications such as search engines, news feeds and recommendation systems. However, several recent events have pointed to the fact that algorithmic bias in rankings, which results in decreased fairness or diversity in the type of content presented, can promote stereotypes and propagate injustices. Motivated by such real-world applications, in this paper we initiate the study of the traditional ranking problem with additional fairness constraints. Given a collection of items along with 1) the value of placing an item at a particular position, 2) the collection of possibly non-disjoint attributes (e.g., gender, age, race) of each item and 3) a collection of fairness constraints that upper bound the number of items with each attribute that are allowed to appear in the top positions of the ranking, the goal is to output a ranking that maximizes value 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 exact and approximation algorithms along with complementary hardness results that, together, come close to settling the approximability of the constrained ranking maximization problem. We identify a parameter ∆ -the maximum number of properties any item has -and show that on the one hand when ∆ = 1, there is a fast algorithm to solve the problem exactly, but on the other hand when ∆ ≥ 3, the problem is hard to approximate, and we present a near-optimal O(∆)-approximation algorithm for the problem under mild assumptions. Unlike prior work on the approximability of constrained matching problems, our algorithm is polynomial time, even when the number of constraints is large (polynomially many), its approximation does not depend on the number of constraints, and it produces solutions with small constraint violations. Technically, our main results rely on novel insights about the standard linear programming relaxation for the constrained matching problem when the objective function satisfies certain properties that appear in common ranking metrics such as discounted cumulative gain (DCG), Spearman's rho or Bradley-Terry, along with the nested structure of fairness constraints. Overall, our results contribute to the growing set of algorithms that can counter algorithmic bias, and the structural insights obtained may find use in other algorithmic contexts related to ranking problems.
Celis et al. REF present a theoretical investigation of fair ranking computation with constraints on the maximum and the minimum number of elements possessing an attribute value that can be present at each rank.
Ranking with Fairness Constraints
ArXiv
ArXiv
Computer Science Mathematics