Ranking with Fairness Constraints

By L. Elisa Celis, Damian Straszak, Nisheeth K. Vishnoi. 2017

359 citations recorded by the source corpus.

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.

Subfields: Computational Theory and Mathematics, Computer Networks and Communications, Economics and Econometrics, AI Ethics, Fairness & Society

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Computer Networks and Communications

In Economics and Econometrics

In AI Ethics, Fairness & Society

Citations in the corpus

Beyond Individual and Group Fairness (2020, methodology): “There has also been work, however, studying fairness criteria and algorithms for ranking [Celis et al., 2018, Beutel et al., 2019, Narasimhan et al., 2019] and clustering problems [Chierichetti et al., 2017, Schmidt et al., 2018, Backurs et al., 2019] with requirement of a proportional…”
Stable and Fair Classification (2019, background): “, ranking [18, 76], summarization [17], personalization [19, 16], multiwinner voting [15], and online advertising [13].”
50 Years of Test (Un)fairness: Lessons for Machine Learning (2018, background): “There are conceptual similarities between Jones’ criteria and the constrained ranking problem described by [8], and also between Einhorn’s criterion and concerns about infra-marginality [60].”
The Frontiers of Fairness in Machine Learning (2018, background): “There is also some work on fairness in machine learning in other settings — for example, ranking [YS17, CSV17], selection [KRW17, KR18], personalization [CV17], bandit learning [JKM + 18, LRD + 17], human-classiﬁer hybrid decision systems [MPZ17], and reinforcement learning [JJK + 17, DTB17].”
Calibration for the (Computationally-Identifiable) Masses (2017, background): “Calibration for multiple protected sets vs. multicalibration The literature on fairness commonly considers more than a single protected set (cf. [CSV17] which studies fairness in ranking algorithms, with protected groups being deﬁned by each attribute of interest).”
Algorithmic Fairness (2020, background): “Several studies are investigating the user’s perspective [33, 47, 49, 140], where fairness is considered as recommending items equitably to different user groups (referred to as C-fairness ), such as recommending high-paying jobs to both men and women.”
Fair Algorithms for Clustering (2019, background): “The DI doctrine is indeed a law [1,22] in the United States, and consequently many works on algorithmic fairness [13, 14, 18, 23, 37, 43] have focused on this.”
User-oriented Fairness in Recommendation (2021, background): “As concluded in [32], the metrics include the supervised criteria which control the average exposure of groups to be proportional to the average relevance of the results of groups to a query [8, 39], and the unsupervised criteria which require that the average exposure at the top of the ranking list”
Fairness-Aware Ranking in Search & Recommendation Systems with Application to LinkedIn Talent Search (2019, methodology): “ithms for ranking in the presence of fairness constraints, specified as the maximum (or minimum) number of elements of each class that can appear at any position in the ranking, have been proposed in [15, 42]. Zehlike et al. [42] propose a fair top-k ranking algorithm focusing on a required represen”
Designing Fair Ranking Schemes (2017, background): “mographic groups and (2) their ranked outcome. While fairness in algorithmic systems is an active area of research [17], our work is among a small handful of studies that focus on fairness in ranking [5,15,16]. While others considered mitigating bias in the output of a ranker [5,16], or incorporatin”
Diversity and Inclusion Metrics in Subset Selection (2020, background): “Our formulation bears some re-semblance to that of [9], who discuss ranking objects subject to upper and lower bounds.”
Optimizing Long-term Social Welfare in Recommender Systems: A Constrained Matching Approach (2020, background): “Celis et al. (2017) propose a matching algo-rithm for ranking a set of items efﬁciently under a fairness constraint that encourages demographic diversity of items in the top-ranked position.”
Using Image Fairness Representations in Diversity-Based Re-ranking for Recommendations (2018, background): “In Celis et al. [6], the authors presented fast exact and approximation algorithms and hardness results for a constrained ranking maximization problem where fairness notions are incorporated in their constraints.”
Pairwise Fairness for Ranking and Regression (2019, methodology): “Of these, some provide post-processing algorithms for re-ranking a given ranking [Biega et al., 2018, Celis et al., 2018, Singh and Joachims, 2018, 2019], while others, like us, learn a ranking model from scratch [Zehlike and Castillo, 2018, Singh and Joachims, 2019].”
Classification with Fairness Constraints: A Meta-Algorithm with Provable Guarantees (2018, neutral): “y,theconstraintsofˆ-Fairarenon-convexingeneral. Tohandlethisproblem, weconsiderlinearfairnessconstraints,whichhavebeenconsideredinotherfundamentalalgorithmicproblemsincludingsampling[11,10,13],ranking[14],voting[12],andpersonalization [15]. Weintroducethefollowingprogramasasubroutineforsolvingˆ-Fair”
FA*IR: A Fair Top-k Ranking Algorithm (2017, methodology): “generated multiple rankings of different lengths k using the algo-rithm Example results are shown on Figure 2 for some combinations of k and α c .”
Toward Controlling Discrimination in Online Ad Auctions (2019, neutral): “ing [10,24] who control polarization in social-networks and personalized feeds, [42] who diversify personal feeds, and [12] who create a diverse and balanced summary of a set of results. In addition, [6,13,44] study fair ranking algorithms; these could be used to generate a balanced list of results ”