SCORING IS NOT ENOUGH: ADDRESSING GAPS IN UTILITY-FAIRNESS TRADE-OFFS FOR RANKING

The Limitations of Scoring

Modern information retrieval and recommendation systems typically follow a two-step paradigm: first, learn a scoring function that assigns a numerical value to each document, and second, rank documents by sorting them according to these scores. While this approach is highly effective for maximizing utility, this paper demonstrates that it is fundamentally limited when the goal is to balance utility with fairness. Because fairness metrics—such as group-based interaction disparity—are often non-decomposable (they depend on the collective arrangement of documents in a query), a simple document-level score cannot capture the complex dependencies required to reach the Pareto frontier of utility-fairness trade-offs.

Analytical and Empirical Evidence

The authors provide formal proofs showing that for a wide class of utility and fairness functions, no scoring function can achieve the optimal trade-off. They construct adversarial query distributions where any fixed scoring function—whether deterministic or randomized (such as the Plackett-Luce model)—fails to reach the optimal ranking. Numerical simulations confirm that even when using sophisticated gradient-based optimization for randomized scoring, the resulting trade-off curves remain significantly below the theoretical optimum achievable through exhaustive post-processing.

Moving Beyond Scoring

To address these gaps, the paper explores "ex-post" ranking, or post-processing, where the system learns relevances independently and then optimizes the ranking order at inference time. While exhaustive search for the optimal ranking is computationally intractable for large sets, the authors demonstrate that semi-greedy approaches, such as beam search, can effectively bridge the gap. These methods allow for a more flexible exploration of the ranking space, enabling the system to achieve trade-offs that are unreachable by traditional scoring-based models.

This work challenges the dominant "learn-to-rank" paradigm in algorithmic fairness. By proving that scoring is inherently suboptimal for non-decomposable objectives, the authors provide a theoretical foundation for why current fairness-aware ranking models may be underperforming. It suggests that researchers and practitioners should shift their focus toward post-processing or hybrid architectures that can account for the global structure of a ranking rather than relying solely on individual document scores.