# Introducing the Expohedron for Efficient Pareto-optimal Fairness-Utility Amortizations in Repeated Rankings

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 48 references that are in the map.
- First posted on arXiv 7 Feb 2022.

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

- [Fairness of Exposure in Rankings](https://mlsanity.com/paper/1802.07281/) (2018)
- [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)
- [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)
- [Fairness in Rankings and Recommendations: An Overview](https://mlsanity.com/paper/2104.05994/) (2021)
- [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)
- [Fairness of Exposure in Stochastic Bandits](https://mlsanity.com/paper/2103.02735/) (2021)
- [Computationally Efficient Optimization of Plackett-Luce Ranking Models for Relevance and Fairness](https://mlsanity.com/paper/2105.00855/) (2021)
- [Reducing Disparate Exposure in Ranking: A Learning To Rank Approach](https://mlsanity.com/paper/1805.08716/) (2018)
- [TFROM: A Two-sided Fairness-Aware Recommendation Model for Both Customers and Providers](https://mlsanity.com/paper/2104.09024/) (2021)
- [Fairness in Ranking under Uncertainty](https://mlsanity.com/paper/2107.06720/) (2021)
- [User Fairness, Item Fairness, and Diversity for Rankings in Two-Sided Markets](https://mlsanity.com/paper/2010.01470/) (2020)
- [Online certification of preference-based fairness for personalized recommender systems](https://mlsanity.com/paper/2104.14527/) (2021)
- [Optimizing Rankings for Recommendation in Matching Markets](https://mlsanity.com/paper/2106.01941/) (2021)
- [Overview of the TREC 2020 Fair Ranking Track](https://mlsanity.com/paper/2108.05135/) (2021)

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

- [Optimizing generalized Gini indices for fairness in rankings](https://mlsanity.com/paper/2204.06521/) (2022)
- [Uncertainty Quantification for Fairness in Two-Stage Recommender Systems](https://mlsanity.com/paper/2205.15436/) (2022)
- [Fairness in Matching under Uncertainty](https://mlsanity.com/paper/2302.03810/) (2023)
- [Geometric Algorithms for Neural Combinatorial Optimization with Constraints](https://mlsanity.com/paper/2510.24039/) (2025)
- [Contextual bandits with concave rewards, and an application to fair ranking](https://mlsanity.com/paper/2210.09957/) (2022)
- [Sampling Individually-Fair Rankings that are Always Group Fair](https://mlsanity.com/paper/2306.11964/) (2023)
- [Debiasing Machine Learning Models by Using Weakly Supervised Learning](https://mlsanity.com/paper/2402.15477/) (2024)
- [Sampling Ex-Post Group-Fair Rankings](https://mlsanity.com/paper/2203.00887/) (2022)
- [Individual Fairness under Varied Notions of Group Fairness in Bipartite Matching - One Framework to Approximate Them All](https://mlsanity.com/paper/2208.09951/) (2022)
- [Learning to Re-rank with Constrained Meta-Optimal Transport](https://mlsanity.com/paper/2305.00319/) (2023)
- [Towards Efficient Pareto-optimal Utility-Fairness between Groups in Repeated Rankings](https://mlsanity.com/paper/2402.14305/) (2024)

## Abstract (arXiv)

We consider the problem of computing a sequence of rankings that maximizes consumer-side utility while minimizing producer-side individual unfairness of exposure. While prior work has addressed this problem using linear or quadratic programs on bistochastic matrices, such approaches, relying on Birkhoff-von Neumann (BvN) decompositions, are too slow to be implemented at large scale. In this paper we introduce a geometrical object, a polytope that we call expohedron, whose points represent all achievable exposures of items for a Position Based Model (PBM). We exhibit some of its properties and lay out a Carath'eodory decomposition algorithm with complexity O(n2log(n)) able to express any point inside the expohedron as a convex sum of at most n vertices, where n is the number of items to rank. Such a decomposition makes it possible to express any feasible target exposure as a distribution over at most n rankings. Furthermore we show that we can use this polytope to recover the whole Pareto frontier of the multi-objective fairness-utility optimization problem, using a simple geometrical procedure with complexity O(n2log(n)). Our approach compares favorably to linear or quadratic programming baselines in terms of algorithmic complexity and empirical runtime and is applicable to any merit that is a non-decreasing function of item relevance. Furthermore our solution can be expressed as a distribution over only n permutations, instead of the (n-1)2 + 1 achieved with BvN decompositions. We perform experiments on synthetic and real-world datasets, confirming our theoretical results.