Scoring Is Not Enough: Addressing Gaps in Utility-fairness Trade-offs for Ranking

In ranking systems like search engines or recommendation feeds, we usually assign scores to items to rank them. This paper shows that simply using scores is not enough to balance usefulness and fairness perfectly. Instead, using "post-processing" (adjusting the list after scores are assigned) methods like beam search can achieve much better results.

The failure of document-level scoring

Modern ranking systems typically follow a standard paradigm. They learn a scoring function that assigns a numerical value to each document based on its features. Then, they simply sort those documents in descending order. This approach works well when the goal is utility (the total relevance or engagement of a list). However, the authors argue that this paradigm breaks down when we introduce fairness as a secondary objective.

The core issue is a structural mismatch. Utility is "decomposable," meaning the total value of a list is the sum of its parts. Fairness, conversely, is often "non-decomposable." As illustrated in, fairness metrics like interaction disparity (the difference in how groups are treated) depend on the relationship between groups within the entire query.

Because a scoring function operates on documents in isolation, it cannot "see" the global composition of the list. Consequently, the authors prove that scoring-based methods are inherently incapable of reaching the optimal trade-off between utility and fairness. This holds true whether the scoring is deterministic (fixed) or randomized (probabilistic).

Navigating the trade-off via beam search

To overcome these limitations, the authors suggest shifting from in-processing (learning scores) to ex-post processing (re-ranking the results). A purely "greedy" re-ranking approach picks the best document for the current position. However, it is often myopic (shortsighted). Much like a driver who only looks at the next ten feet of road, it can miss a better path ahead. This myopia leads to local minima where the system fails to achieve a balanced trade-off.

The authors introduce "Beam Trade-off Search" to solve this. Instead of committing to one document at each step, the algorithm maintains a "beam" of $B$ candidate rankings. The process works as follows:

1. The algorithm sorts documents within their respective groups by relevance.
2. It initializes the beam with the most relevant documents from each group.
3. For each subsequent position, the algorithm expands the beam. It considers the next available document from each group for every candidate.
4. It calculates the potential utility-fairness trade-off for these new combinations.
5. Finally, it prunes the beam. It keeps only the top-$B$ candidates that yield the best trade-off values.

This approach allows the system to explore multiple "parallel universes" of possible rankings. It enables the system to make short-term sacrifices in utility to achieve much greater long-term gains in fairness.

Empirical evidence of the optimality gap

The authors demonstrate the superiority of their method through testing on synthetic and real-world datasets. In a controlled synthetic environment, the paper finds that the Plackett-Luce (PL) model—a widely used randomized scoring method—is significantly outperformed by both greedy and beam search [Figure 2a].

On the real-world COMPAS dataset, which involves predicting recidivism (the tendency of a convicted criminal to reoffend), the authors report that beam search achieves high utility while maintaining low unfairness [Figure 2b]. The results are echoed in the German Credit and MovieLens 100K datasets. In the MovieLens 100K study, the authors note that even with weak relevance models, beam search and greedy approaches provide competitive trade-off curves .

For example, using a linear regression model with an $R^2$ of only 0.09 (indicating very low explanatory power), the methods still performed well. This suggests the advantage of re-ranking is robust even when relevance predictions are imperfect.

Constraints and missing dimensions

The authors identify several boundaries to their findings. First, these ex-post methods rely on knowing or learning document relevances. In production, these must be learned via regression (predicting a continuous value). This introduces its own layer of approximation error.

Second, the paper does not explore fairness notions defined as direct properties of the score function itself. If fairness is built into the score, scoring might be sufficient. Third, the framework does not directly accommodate certain utility metrics like Mean Average Precision (MAP). While the authors suggest the optimality gap would likely persist for such metrics, they do not provide a formal proof for them in this study.

The verdict: move beyond the score

If you are building a ranking system where fairness is critical, the verdict is clear. Stop trying to solve the problem solely through better scoring functions. The authors have demonstrated that scoring is mathematically insufficient to navigate the tension between utility and group fairness.

For engineers, the practical takeaway is to decouple relevance modeling from ranking logic. Instead of training one complex model to handle both, use a high-quality regressor to estimate relevance. Then, apply a beam search re-ranker to tune the fairness dial. This modular approach is more effective at hitting the Pareto frontier (the set of optimal trade-offs). It also allows you to adjust your fairness constraints ($\alpha$) dynamically without retraining your entire model architecture.

Figures from the paper