# Towards Efficient Pareto-optimal Utility-Fairness between Groups in Repeated Rankings

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 18 of its 51 references that are in the map.
- First posted on arXiv 22 Feb 2024.

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

- [DCN V2: Improved Deep & Cross Network and Practical Lessons for Web-scale Learning to Rank Systems](https://mlsanity.com/paper/2008.13535/) (2020)
- [Fairness of Exposure in Rankings](https://mlsanity.com/paper/1802.07281/) (2018)
- [A Rewriting System for Convex Optimization Problems](https://mlsanity.com/paper/1709.04494/) (2017)
- [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)
- [Towards Long-term Fairness in Recommendation](https://mlsanity.com/paper/2101.03584/) (2021)
- [Evaluating Stochastic Rankings with Expected Exposure](https://mlsanity.com/paper/2004.13157/) (2020)
- [Toward Pareto Efficient Fairness-Utility Trade-off inRecommendation through Reinforcement Learning](https://mlsanity.com/paper/2201.00140/) (2022)
- [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)
- [The Unfairness of Popularity Bias in Book Recommendation](https://mlsanity.com/paper/2202.13446/) (2022)
- [Optimizing Rankings for Recommendation in Matching Markets](https://mlsanity.com/paper/2106.01941/) (2021)
- [Introducing the Expohedron for Efficient Pareto-optimal Fairness-Utility Amortizations in Repeated Rankings](https://mlsanity.com/paper/2202.03237/) (2022)
- [Pareto-based Multi-Objective Recommender System with Forgetting Curve](https://mlsanity.com/paper/2312.16868/) (2023)
- [Capuchin: Causal Database Repair for Algorithmic Fairness](https://mlsanity.com/paper/1902.08283/) (2019)
- [Provider Fairness and Beyond-Accuracy Trade-offs in Recommender Systems](https://mlsanity.com/paper/2309.04250/) (2023)
- [Overview of the TREC 2020 Fair Ranking Track](https://mlsanity.com/paper/2108.05135/) (2021)

## Abstract (arXiv)

In this paper, we tackle the problem of computing a sequence of rankings with the guarantee of the Pareto-optimal balance between (1) maximizing the utility of the consumers and (2) minimizing unfairness between producers of the items. Such a multi-objective optimization problem is typically solved using a combination of a scalarization method and linear programming on bi-stochastic matrices, representing the distribution of possible rankings of items. However, the above-mentioned approach relies on Birkhoff-von Neumann (BvN) decomposition, of which the computational complexity is O(n5) with n being the number of items, making it impractical for large-scale systems. To address this drawback, we introduce a novel approach to the above problem by using the Expohedron - a permutahedron whose points represent all achievable exposures of items. On the Expohedron, we profile the Pareto curve which captures the trade-off between group fairness and user utility by identifying a finite number of Pareto optimal solutions. We further propose an efficient method by relaxing our optimization problem on the Expohedron's circumscribed n-sphere, which significantly improve the running time. Moreover, the approximate Pareto curve is asymptotically close to the real Pareto optimal curve as the number of substantial solutions increases. Our methods are applicable with different ranking merits that are non-decreasing functions of item relevance. The effectiveness of our methods are validated through experiments on both synthetic and real-world datasets.