# Ranking with Fairness Constraints

arXiv: https://arxiv.org/abs/1704.06840 · HTML: https://mlsanity.com/paper/1704.06840/

## Key facts

- Cited by 78 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Apr 2017.

## Built on by (most cited first, 30 of 78)

- [User-oriented Fairness in Recommendation](https://mlsanity.com/paper/2104.10671/) (2021)
- [Personalized Counterfactual Fairness in Recommendation](https://mlsanity.com/paper/2105.09829/) (2021)
- [Societal Biases in Retrieved Contents: Measurement Framework and Adversarial Mitigation for BERT Rankers](https://mlsanity.com/paper/2104.13640/) (2021)
- [Evaluating Fairness of Machine Learning Models Under Uncertain and Incomplete Information](https://mlsanity.com/paper/2102.08410/) (2021)
- [Human-Centric Multimodal Machine Learning: Recent Advances and Testbed on AI-based Recruitment](https://mlsanity.com/paper/2302.10908/) (2023)
- [Better Algorithms for Individually Fair k-Clustering](https://mlsanity.com/paper/2106.12150/) (2021)
- [Two-sided fairness in rankings via Lorenz dominance](https://mlsanity.com/paper/2110.15781/) (2021)
- [Fairness in Ranking under Uncertainty](https://mlsanity.com/paper/2107.06720/) (2021)
- [Fairness in Recommendation: Foundations, Methods and Applications](https://mlsanity.com/paper/2205.13619/) (2022)
- [Online certification of preference-based fairness for personalized recommender systems](https://mlsanity.com/paper/2104.14527/) (2021)
- [When Fair Ranking Meets Uncertain Inference](https://mlsanity.com/paper/2105.02091/) (2021)
- [Fair ranking: a critical review, challenges, and future directions](https://mlsanity.com/paper/2201.12662/) (2022)
- [Maxmin-Fair Ranking: Individual Fairness under Group-Fairness Constraints](https://mlsanity.com/paper/2106.08652/) (2021)
- [End-to-end Learning for Fair Ranking Systems](https://mlsanity.com/paper/2111.10723/) (2021)
- [Fair Ranking with Noisy Protected Attributes](https://mlsanity.com/paper/2211.17067/) (2022)
- [Do Large Language Models Rank Fairly? An Empirical Study on the Fairness of LLMs as Rankers](https://mlsanity.com/paper/2404.03192/) (2024)
- [Vote'n'Rank: Revision of Benchmarking with Social Choice Theory](https://mlsanity.com/paper/2210.05769/) (2022)
- [Estimation of Fair Ranking Metrics with Incomplete Judgments](https://mlsanity.com/paper/2108.05152/) (2021)
- [Fair Enough: Searching for Sufficient Measures of Fairness](https://mlsanity.com/paper/2110.13029/) (2021)
- [Experiments on Generalizability of User-Oriented Fairness in Recommender Systems](https://mlsanity.com/paper/2205.08289/) (2022)
- [Fair Ranking as Fair Division: Impact-Based Individual Fairness in Ranking](https://mlsanity.com/paper/2206.07247/) (2022)
- [FairCanary: Rapid Continuous Explainable Fairness](https://mlsanity.com/paper/2106.07057/) (2021)
- [Algorithmic Fairness and Vertical Equity: Income Fairness with IRS Tax Audit Models](https://mlsanity.com/paper/2206.09875/) (2022)
- [Uncertainty Quantification for Fairness in Two-Stage Recommender Systems](https://mlsanity.com/paper/2205.15436/) (2022)
- [CatRAG: Functor-Guided Structural Debiasing with Retrieval Augmentation for Fair LLMs](https://mlsanity.com/paper/2603.21524/) (2026)
- [Fairness Through Regularization for Learning to Rank](https://mlsanity.com/paper/2102.05996/) (2021)
- [Individually Fair Ranking](https://mlsanity.com/paper/2103.11023/) (2021)
- [Pairwise Fairness for Ordinal Regression](https://mlsanity.com/paper/2105.03153/) (2021)
- [Identifying Biased Subgroups in Ranking and Classification](https://mlsanity.com/paper/2108.07450/) (2021)
- [Fairness for Robust Learning to Rank](https://mlsanity.com/paper/2112.06288/) (2021)

## Abstract (arXiv)

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.