# Probabilistic Permutation Graph Search: Black-Box Optimization for Fairness in Ranking

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 59 references that are in the map.
- First posted on arXiv 28 Apr 2022.

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

- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Inherent Trade-Offs in the Fair Determination of Risk Scores](https://mlsanity.com/paper/1609.05807/) (2016)
- [Fairness of Exposure in Rankings](https://mlsanity.com/paper/1802.07281/) (2018)
- [Unbiased Learning-to-Rank with Biased Feedback](https://mlsanity.com/paper/1608.04468/) (2016)
- [A* Sampling](https://mlsanity.com/paper/1411.0030/) (2014)
- [Fairness-Aware Ranking in Search & Recommendation Systems with Application to LinkedIn Talent Search](https://mlsanity.com/paper/1905.01989/) (2019)
- [Equity of Attention: Amortizing Individual Fairness in Rankings](https://mlsanity.com/paper/1805.01788/) (2018)
- [Introducing LETOR 4.0 Datasets](https://mlsanity.com/paper/1306.2597/) (2013)
- [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)
- [Policy Learning for Fairness in Ranking](https://mlsanity.com/paper/1902.04056/) (2019)
- [Controlling Fairness and Bias in Dynamic Learning-to-Rank](https://mlsanity.com/paper/2005.14713/) (2020)
- [Evaluating Stochastic Rankings with Expected Exposure](https://mlsanity.com/paper/2004.13157/) (2020)
- [Designing Fair Ranking Schemes](https://mlsanity.com/paper/1712.09752/) (2017)
- [Computationally Efficient Optimization of Plackett-Luce Ranking Models for Relevance and Fairness](https://mlsanity.com/paper/2105.00855/) (2021)
- [Fairness in Ranking: A Survey](https://mlsanity.com/paper/2103.14000/) (2021)
- [Multiple-Play Bandits in the Position-Based Model](https://mlsanity.com/paper/1606.02448/) (2016)
- [Interventions for Ranking in the Presence of Implicit Bias](https://mlsanity.com/paper/2001.08767/) (2020)
- [Quantifying the Impact of User Attention on Fair Group Representation in Ranked Lists](https://mlsanity.com/paper/1901.10437/) (2019)
- [DCM Bandits: Learning to Rank with Multiple Clicks](https://mlsanity.com/paper/1602.03146/) (2016)
- [Policy-Gradient Training of Fair and Unbiased Ranking Functions](https://mlsanity.com/paper/1911.08054/) (2019)
- [Estimation of Fair Ranking Metrics with Incomplete Judgments](https://mlsanity.com/paper/2108.05152/) (2021)
- [Low-variance Black-box Gradient Estimates for the Plackett-Luce Distribution](https://mlsanity.com/paper/1911.10036/) (2019)
- [Comparing Fair Ranking Metrics](https://mlsanity.com/paper/2009.01311/) (2020)
- [Robust Generalization and Safe Query-Specialization in Counterfactual Learning to Rank](https://mlsanity.com/paper/2102.05990/) (2021)
- [Understanding and Mitigating the Effect of Outliers in Fair Ranking](https://mlsanity.com/paper/2112.11251/) (2021)
- [Mixture-Based Correction for Position and Trust Bias in Counterfactual Learning to Rank](https://mlsanity.com/paper/2108.08538/) (2021)

## Built on by (most cited first, 4 of 4)

- [Recent Advances in the Foundations and Applications of Unbiased Learning to Rank](https://mlsanity.com/paper/2305.02914/) (2023)
- [Towards Better Fairness-Utility Trade-off: A Comprehensive Measurement-Based Reinforcement Learning Framework](https://mlsanity.com/paper/2307.11379/) (2023)
- [ExCalibR: Expected Calibration of Recommendations](https://mlsanity.com/paper/2304.12311/) (2023)
- [Scoring Is Not Enough: Addressing Gaps in Utility-fairness Trade-offs for Ranking](https://mlsanity.com/paper/2606.26369/) (2026)

## Abstract (arXiv)

There are several measures for fairness in ranking, based on different underlying assumptions and perspectives. PL optimization with the REINFORCE algorithm can be used for optimizing black-box objective functions over permutations. In particular, it can be used for optimizing fairness measures. However, though effective for queries with a moderate number of repeating sessions, PL optimization has room for improvement for queries with a small number of repeating sessions. In this paper, we present a novel way of representing permutation distributions, based on the notion of permutation graphs. Similar to PL, our distribution representation, called PPG, can be used for black-box optimization of fairness. Different from PL, where pointwise logits are used as the distribution parameters, in PPG pairwise inversion probabilities together with a reference permutation construct the distribution. As such, the reference permutation can be set to the best sampled permutation regarding the objective function, making PPG suitable for both deterministic and stochastic rankings. Our experiments show that PPG, while comparable to PL for larger session repetitions (i.e., stochastic ranking), improves over PL for optimizing fairness metrics for queries with one session (i.e., deterministic ranking). Additionally, when accurate utility estimations are available, e.g., in tabular models, the performance of PPG in fairness optimization is significantly boosted compared to lower quality utility estimations from a learning to rank model, leading to a large performance gap with PL. Finally, the pairwise probabilities make it possible to impose pairwise constraints such as "item d1 should always be ranked higher than item d2." Such constraints can be used to simultaneously optimize the fairness metric and control another objective such as ranking performance.