# Sampling Ex-Post Group-Fair Rankings

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 61 references that are in the map.
- First posted on arXiv 2 Mar 2022.

## Builds on (most cited first, 17 of 17)

- [Fairness of Exposure in Rankings](https://mlsanity.com/paper/1802.07281/) (2018)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fairness-Aware Ranking in Search & Recommendation Systems with Application to LinkedIn Talent Search](https://mlsanity.com/paper/1905.01989/) (2019)
- [Fairness in Recommendation Ranking through Pairwise Comparisons](https://mlsanity.com/paper/1903.00780/) (2019)
- [Equity of Attention: Amortizing Individual Fairness in Rankings](https://mlsanity.com/paper/1805.01788/) (2018)
- [FA*IR: A Fair Top-k Ranking Algorithm](https://mlsanity.com/paper/1706.06368/) (2017)
- [Measuring Fairness in Ranked Outputs](https://mlsanity.com/paper/1610.08559/) (2016)
- [Ranking with Fairness Constraints](https://mlsanity.com/paper/1704.06840/) (2017)
- [Pairwise Fairness for Ranking and Regression](https://mlsanity.com/paper/1906.05330/) (2019)
- [Evaluating Stochastic Rankings with Expected Exposure](https://mlsanity.com/paper/2004.13157/) (2020)
- [Fair and Diverse DPP-based Data Summarization](https://mlsanity.com/paper/1802.04023/) (2018)
- [Sampling with Riemannian Hamiltonian Monte Carlo in a Constrained Space](https://mlsanity.com/paper/2202.01908/) (2022)
- [Interventions for Ranking in the Presence of Implicit Bias](https://mlsanity.com/paper/2001.08767/) (2020)
- [Fairness in Ranking under Uncertainty](https://mlsanity.com/paper/2107.06720/) (2021)
- [On Discrimination Discovery and Removal in Ranked Data using Causal Graph](https://mlsanity.com/paper/1803.01901/) (2018)
- [Introducing the Expohedron for Efficient Pareto-optimal Fairness-Utility Amortizations in Repeated Rankings](https://mlsanity.com/paper/2202.03237/) (2022)
- [Fairness for Robust Learning to Rank](https://mlsanity.com/paper/2112.06288/) (2021)

## Abstract (arXiv)

Randomized rankings have been of recent interest to achieve ex-ante fairer exposure and better robustness than deterministic rankings. We propose a set of natural axioms for randomized group-fair rankings and prove that there exists a unique distribution D that satisfies our axioms and is supported only over ex-post group-fair rankings, i.e., rankings that satisfy given lower and upper bounds on group-wise representation in the top-k ranks. Our problem formulation works even when there is implicit bias, incomplete relevance information, or only ordinal ranking is available instead of relevance scores or utility values. We propose two algorithms to sample a random group-fair ranking from the distribution D mentioned above. Our first dynamic programming-based algorithm samples ex-post group-fair rankings uniformly at random in time O(k2ℓ), where ℓ is the number of groups. Our second random walk-based algorithm samples ex-post group-fair rankings from a distribution δ-close to D in total variation distance and has expected running time O^*(k2ℓ2), when there is a sufficient gap between the given upper and lower bounds on the group-wise representation. The former does exact sampling, but the latter runs significantly faster on real-world data sets for larger values of k. We give empirical evidence that our algorithms compare favorably against recent baselines for fairness and ranking utility on real-world data sets.