Joint Evaluation of Fairness and Relevance in Recommender Systems with Pareto Frontier

Theresia Veronika Rampisela, Tuukka Ruotsalo, Maria Maistro, Christina Lioma

Abstract

Fairness and relevance are two critical, yet often conflicting, dimensions of recommender systems (RS). Traditionally, these aspects are evaluated either separately—leading to a "two-best-models" dilemma—or through ad-hoc joint metrics that lack theoretical grounding and consistency with standard relevance measures like NDCG. This paper introduces Distance to Pareto Frontier (DPFR), a modular framework for the joint evaluation of fairness and relevance. By computing the empirical Pareto frontier for any pair of existing measures, DPFR quantifies a model's performance based on its distance to the optimal trade-off boundary. Experiments across six datasets and multiple re-ranking strategies demonstrate that DPFR provides a more robust, theoretically well-founded, and computationally efficient assessment compared to existing joint metrics.

Introduction

In modern recommender systems, the goal is no longer just to maximize user relevance (how much a user likes an item) but also to ensure item fairness (e.g., equitable exposure for different providers). However, these objectives are frequently at odds: increasing the visibility of niche items often comes at the cost of aggregate user satisfaction.

Currently, researchers typically navigate this trade-off using two flawed approaches. The first is separate evaluation, where relevance and fairness are reported as independent scores. This often results in no clear winner, as one model may excel in relevance while another dominates in fairness. The second is the use of joint metrics, which combine both aspects into a single score using arbitrary formulas. These metrics are often unstable, difficult to interpret, and fail to align with traditional relevance benchmarks. To bridge this gap, we propose DPFR, a method that evaluates models based on what is empirically achievable on a specific dataset.

The DPFR Framework

The core of our approach is the Distance to Pareto Frontier (DPFR). The framework operates in three distinct phases:

  1. Generating the Pareto Frontier (PF): We utilize an algorithm termed Oracle2Fair. Starting from a "maximally relevant" recommendation list (the Oracle), the algorithm iteratively replaces items to enhance fairness while minimizing the resulting loss in relevance. This process maps the boundary where fairness cannot be improved without a corresponding sacrifice in relevance.
  2. Defining a Reference Point: A target point on this frontier is identified using a tunable parameter $\alpha$. For instance, $\alpha=0.5$ represents a balanced weighting between the two objectives.
  3. Measuring Distance: A model’s "goodness" is determined by its Euclidean distance to this reference point. A smaller distance indicates that the model is closer to the optimal empirical trade-off.

To ensure the method is practical for large-scale systems, we also introduced an efficient approximation technique. We found that calculating as few as 6 to 12 points on the frontier provides a highly accurate estimation of the full boundary, significantly reducing computational overhead.

Experimental Setup

We evaluated DPFR across six diverse real-world datasets, varying in size and sparsity:

  • Lastfm: Music recommendations.
  • Amazon-lb: Luxury beauty e-commerce.
  • QK-video: Short video interactions.
  • Jester: Joke ratings.
  • ML-10M & ML-20M: Large-scale movie recommendations (MovieLens).

We tested four RS models and three re-ranking strategies to observe how different algorithmic approaches navigate the fairness-relevance trade-off.

Key Insights

The "Averaging" Trap

Our analysis reveals that simply averaging relevance and fairness scores can be highly deceptive. A model might achieve a high average score yet remain significantly distant from the Pareto Frontier. This indicates that the model is performing sub-optimally in both dimensions relative to what is theoretically possible on that dataset.

Metric Inconsistency and Modularity

Existing joint measures, such as IBO or Mean Max Envy (MME), frequently disagree on which model is superior. These metrics often show weak or negative correlations with Pareto-optimal solutions. In contrast, DPFR is a meta-metric. Its modular design allows researchers to plug in any relevance measure (e.g., NDCG, MAP) and any fairness measure (e.g., Gini Index, Entropy), providing a consistent evaluation framework regardless of the specific metrics chosen.

Efficiency and Performance

The approximation method proved remarkably effective. Using only 12 points to estimate the frontier resulted in a Kendall’s $\tau$ correlation of $\ge 0.95$ compared to the full frontier across nearly all datasets. Furthermore, on the ML-20M dataset, DPFR estimation was up to 35 times faster than computing complex joint measures like MME.

Conclusion

DPFR offers a robust alternative to ad-hoc joint metrics by grounding evaluation in the concept of Pareto optimality. Our results show that the "best" model according to DPFR differed from the best relevance-only model 100% of the time, highlighting its ability to identify balanced, high-performing systems that traditional metrics overlook.

Future work will explore extending this framework from individual item fairness to group fairness (e.g., demographic parity) and investigating the long-term impact of Pareto-optimal recommendations on user retention in live environments.

Summary updated

Abstract

Fairness and relevance are two important aspects of recommender systems (RSs). Typically, they are evaluated either (i) separately by individual measures of fairness and relevance, or (ii) jointly using a single measure that accounts for fairness with respect to relevance. However, approach (i) often does not provide a reliable joint estimate of the goodness of the models, as it has two different best models: one for fairness and another for relevance. Approach (ii) is also problematic because these measures tend to be ad-hoc and do not relate well to traditional relevance measures, like NDCG. Motivated by this, we present a new approach for jointly evaluating fairness and relevance in RSs: Distance to Pareto Frontier (DPFR). Given some user-item interaction data, we compute their Pareto frontier for a pair of existing relevance and fairness measures, and then use the distance from the frontier as a measure of the jointly achievable fairness and relevance. Our approach is modular and intuitive as it can be computed with existing measures. Experiments with 4 RS models, 3 re-ranking strategies, and 6 datasets show that existing metrics have inconsistent associations with our Pareto-optimal solution, making DPFR a more robust and theoretically well-founded joint measure for assessing fairness and relevance. Our code: https://github.com/theresiavr/DPFR-recsys-evaluation
BibTeX
@inproceedings{rampisela2025joint,
  author = {Theresia Veronika Rampisela and Tuukka Ruotsalo and Maria Maistro and Christina Lioma},
  title = {{Joint Evaluation of Fairness and Relevance in Recommender Systems with Pareto Frontier}},
  booktitle = {The Web Conference},
  year = {2025},
  doi = {10.1145/3696410.3714589},
}
Figure