PaperlayerView exact revision on arXiv

Source-linked AI summary

Fairness in Rankings and Recommendations: An Overview

Evaggelia Pitoura, Kostas Stefanidis, Georgia Koutrika

arXiv:2104.05994v2cs.DB

TL;DR

Data-driven rankings and recommendations increasingly influence decisions, while fairness remains difficult to define and enforce consistently. The paper provides a structured taxonomy and toolkit of fairness definitions, models, and methods, and identifies open challenges. It highlights trade-offs among enforcement approaches and the difficulty of guaranteeing or verifying fairness in outputs.

  • Problem

    Fairness in rankings and recommendations involves elusive concepts and diverse definitions, while current research often studies fairness tasks in isolation rather than across the whole data pipeline.

  • Method

    The survey systematically organizes fairness models and computational methods for rankings, recommendations, and rank aggregation, including pre-processing, in-processing, and post-processing approaches.

  • Results

    In-processing approaches typically offer better fairness–accuracy trade-offs than post-processing methods, while post-processing provides outputs that are easier to understand but may lose accuracy unpredictably.

  • Takeaways & Limitations

    The taxonomy and structured comparison expose differences and commonalities among fairness approaches and help frame questions about which definitions suit which contexts.

  • Takeaways & Limitations

    Fairness verification is generally more complex for individual fairness than for group fairness and may require difficult-to-explain proofs of unfairness.

Abstract

from arXiv · show

We increasingly depend on a variety of data-driven algorithmic systems to assist us in many aspects of life. Search engines and recommender systems amongst others are used as sources of information and to help us in making all sort of decisions from selecting restaurants and books, to choosing friends and careers. This has given rise to important concerns regarding the fairness of such systems. In this work, we aim at presenting a toolkit of definitions, models and methods used for ensuring fairness in rankings and recommendations. Our objectives are three-fold: (a) to provide a solid framework on a novel, quickly evolving, and impactful domain, (b) to present related methods and put them into perspective, and (c) to highlight open challenges and research paths for future work.

1 Introduction

Data-driven systems increasingly shape decisions and perceptions, creating fairness concerns because algorithms and data can encode or amplify bias. This survey organizes fairness definitions, models, and computational methods for rankings and recommendations while identifying open challenges.

  • Motivation: Studies show algorithmic systems can encode existing biases, introduce new ones, and systematically underrepresent groups.Examples include stereotype exaggeration in image search and nearly twice the false-positive rate for African-American defendants in COMPAS.
  • Motivation: Search and recommendation systems increasingly influence experiences and perceptions across news, media, advertising, and other domains.Their growing role makes fairness a consequential concern.
  • Motivation: Recommendations can amplify existing bias and reduce diversity, as illustrated by gender-skewed music exposure and job-ad delivery.One music study found female artists represented 25 per cent of users’ listening.
  • Research gap: Because fairness has many definitions and models, the field needs clearer guidance on how approaches differ and when each should be used.The survey frames fairness as including bias from algorithms and from misrepresented or biased data.
  • Survey approach: The survey separates fairness models from computational enforcement methods and classifies models by individual or group, consumer or producer, and single or multiple outputs.It organizes enforcement into pre-processing, in-processing, and post-processing approaches.
  • Scope and contribution: The article presents a technical toolkit spanning rankings, recommendations, and rank aggregation, with broader coverage and depth than narrower related surveys.It also discusses open research challenges in the broader context of data management.

2 The Fairness Problem

The section organizes fairness in rankings and recommendations around individual versus group treatment, input and output similarity, and fairness across different outputs and stakeholders. It defines ranking and recommendation settings, then introduces models and cautions that fairness criteria involve trade-offs and limitations.

  • Rankings: Ranking assigns entities to positions according to task utility, while a fair ranking avoids unjustified influence from protected attributes.
  • Recommendations: Recommendation systems estimate user-item relevance scores from profiles and histories, then form lists from items with the highest estimated scores.
  • Levels of fairness: Fairness models distinguish individual fairness, which treats similar entities similarly, from group fairness, which requires similarly treated protected-attribute groups.
  • Similarity: Operationalizing fairness requires defining input similarity through individual distances or group partitions and output similarity through formally specified similar treatment.
  • Output fairness: Output fairness differs by setting: rankings emphasize similar visibility under position bias, while recommendations may be treated as classification or ranked-list problems.
  • Fairness models: Individual fairness can constrain probabilistic classifier mappings through a Lipschitz condition, whereas group-based measures may ignore individual merit and produce self-fulfilling prophecy or reverse tokenism.

3 Models of Fairness

Fairness models for rankings and recommendations address protected-group representation, position-dependent exposure, utility, and satisfaction. The survey contrasts these models using example rankings and formal measures.

  • Representation constraints: Group fairness can constrain protected-group representation in top-k positions using lower and upper bounds.For example, requiring at least two red items in the top four is satisfied by rm and rr but not rl.
  • Discounted cumulative fairness: In the example, DCG@10 is 1.81 for rl, 1.70 for rm, and 1.77 for rr, so utility-only rl has the largest ranking-quality score.The rankings respectively emphasize utility, protected-group representation, and an intermediate trade-off.
  • Discounted cumulative fairness: Discounted cumulative fairness measures protected-group representation across ranking prefixes, weighting higher positions more heavily.The approach builds on DCG, which logarithmically discounts item utility by position.
  • Prefix-based measures: Normalized discounted difference compares protected-group proportions in top-p prefixes with their proportion in the overall population.The related normalized discounted ratio instead compares protected and non-protected group proportions using their group sizes.
  • Fairness of exposure: Exposure fairness accounts for position bias by assigning each ranking position an importance value and comparing group exposure.The motivating example has only a 0.02 average-utility gap but a 25% lower protected-group exposure under DCG.
  • Individual and group satisfaction: Individual equity of attention requires item attention to be proportional to utility, while group disagreement measures the spread between users’ overall satisfaction.Low group disagreement means group members are satisfied to similar degrees.

4 Methods for Achieving Fairness

The survey organizes fairness-enforcement methods across the pipeline into pre-processing, in-processing, and post-processing approaches. These categories differ in where they modify data, models, or outputs and in their accuracy implications.

  • Taxonomy: The taxonomy organizes related work by contrasting traditional ranked outputs with alternatives for generating fair rankings and recommendations.The survey uses this cross-type view to place methods into perspective.
  • Pre-processing: Pre-processing methods transform training data to mitigate underlying bias or discrimination before model learning.They are typically application agnostic and target bias arising during data collection or reuse.
  • In-processing: In-processing methods modify or introduce learning algorithms that incorporate fairness during model training.They may add fairness terms to objectives or impose fairness constraints.
  • Post-processing: Post-processing methods treat the ranking or recommendation algorithm as a black box and rerank its output to improve fairness.Because they transform the optimal output, fairness comes at the cost of accuracy, while the resulting changes are comparatively easy to inspect.

5 Pre-processing Methods

Pre-processing methods address bias before ranking or recommendation by transforming data, labels, or weights. The survey organizes these approaches and highlights both their mechanisms and trade-offs, including residual discrimination from correlated attributes and potential accuracy or dataset-value costs.

  • Overview: Pre-processing methods transform training data to remove underlying bias or discrimination before downstream algorithms produce rankings or recommendations.They include approaches studied in classification and a smaller set proposed for recommender systems.
  • 5.2 Class Relabeling: Massaging relabels selected minority and majority examples by promoting high-scoring minority objects and demoting low-scoring majority objects.A ranker orders candidates by their probability of receiving positive labels, after which the top-k minority and bottom-k majority objects are selected.
  • 5.2 Class Relabeling: The required number of label modifications depends on dataset discrimination and the sizes of the protected and non-protected groups.The survey defines discrimination as the difference in positive-class probabilities between minority and majority groups and computes paired modifications to reach zero discrimination.
  • 5.2 Class Relabeling: In the job-application example, relabeling the highest-scoring female and lowest-scoring male makes discrimination zero before classifier training.Applicants are ranked using positive-class probabilities from a Naïve Bayes model, and the resulting dataset is used to train the classifier.
  • 5.7 Summary of Pre-processing Methods: Pre-processing fairness remains a multi-objective problem because reducing discrimination can lower accuracy, while removing correlated attributes can seriously hurt dataset value.The survey also identifies the relationship among dataset features, algorithms, and pre-processing performance as requiring systematic future study.
  • 5.3 Reweighting: Reweighting avoids changing labels by assigning lower or higher weights to objects according to observed-versus-expected representation under independence.For the job example, female positive cases receive a reweighting factor of 1.5 because their expected probability is 0.3 versus an observed probability of 0.2.
  • 5.1 Suppression: Suppressing protected attributes is algorithm-independent, but correlated features can preserve discriminatory information and removing them can reduce dataset value.The classifier may still learn discrimination reflected in the training data through variables correlated with protected attributes.

6 In-processing Methods

In-processing methods modify or introduce ranking and recommendation models, typically incorporating fairness into learning objectives. The survey covers regularization, variational autoencoders, and fair representations, balancing fairness with utility or accuracy.

  • In-processing methods modify existing or introduce new models, distinguishing learning approaches from preference-function approaches.
  • Learning approaches: Learning approaches construct ranking models from labeled training data and minimize loss measuring divergence from input rankings.
  • Regularization: Regularization adds an unfairness term to the original loss, with instantiations depending on the training data, loss function, and fairness measure.
  • Learning to rank: DELTR extends ListNet by adding a fairness constraint, with λ controlling the trade-off between ranking utility and fairness.
  • Recommendation models: For recommenders, independence regularization reduces information about sensitive attributes in recommendation outputs, using terms such as mutual information or distribution distances.
  • Variational autoencoders: Test-time VAE noise experimentally reduces unfairness in recommendation rankings, although higher variance changes predicted scores and can slightly reduce ranking quality.
  • Fair representations: Fair representation learning balances encoding quality, fairness, and prediction accuracy through weighted objectives, and ranking variants replace classification accuracy with ranking distance.

7 Post-processing Methods

Post-processing methods treat ranking and recommendation algorithms as black boxes and transform their outputs to satisfy fairness requirements while preserving the initial ranking as far as possible. The survey presents generative, optimization-based, calibration, package, and repeated-group recommendation approaches.

  • Post-processing takes a ranking and fairness specification as input and produces a new ranking that satisfies fairness while respecting the initial ranking where possible.
  • Generative processes: A generative process incrementally selects protected or non-protected items using Bernoulli trials with parameter p.
  • Generative processes: The generated ranking preserves within-group qualification order and, under some assumptions, maximizes average top-k utility.
  • Constraint optimization: Optimization formulations either maximize fairness subject to a utility constraint or maximize utility subject to sufficient fairness.
  • Constraint optimization: Utility-constrained fairness problems can be solved with integer linear programming or, in special cases, dynamic programming.
  • Group recommendations: Recommendation-package methods greedily select items satisfying the largest number of currently unsatisfied users, with category and distance constraints available.
  • Calibration: Calibration methods re-rank recommendations by trading off prediction scores against calibration, controlled by λ.
  • Multiple outputs: Dynamic α weighting promotes an extremely unsatisfied group member’s preferences in the next round while approximating average aggregation when satisfaction is balanced.

8 Summary of In- and Post-processing Methods

The survey organizes fairness methods across processing stages, fairness targets, and output multiplicity. In-processing methods integrate fairness into objectives, whereas post-processing methods re-rank black-box outputs and provide more interpretable fairness changes but less predictable accuracy effects.

  • Methods are organized by individual versus group fairness, consumer versus producer fairness, and single versus multiple outputs.
  • In-processing: In-processing approaches commonly target group and producer fairness, usually single outputs, and balance accuracy with fairness by extending objective functions.
  • Post-processing: Post-processing approaches cover different fairness definitions while treating ranking and recommendation algorithms as black boxes and re-ranking their outputs.
  • Comparison: In-processing typically offers better fairness–accuracy trade-offs, but it does not guarantee fairness in ranked outputs because fairness is handled during training.
  • Comparison: Post-processing can cause unpredictable accuracy losses, yet its before-and-after outputs are easier to understand as fairer rankings.
  • Limitations: A combined fair-representation and classifier approach has a non-convex optimization problem and requires an arbitrary representation dimension.

9 Verifying Fairness

Fairness verification analyzes decision-making programs against fairness specifications using datasets or population models. The survey discusses runtime monitoring and highlights that individual-fairness proofs and human-readable explanations remain difficult.

  • Fairness verification asks whether a decision-making program’s behavior satisfies a specified fairness property.
  • Verification inputs: Verification can use a concrete dataset or a population model defining a joint probability distribution over program inputs.
  • Verification outcomes: A verifier can prove or disprove group fairness for a program and population.
  • Verification difficulty: Group-fairness verification is generally easier because it reduces to computing event probabilities, whereas individual fairness requires reasoning across multiple program runs.
  • Verification difficulty: Negative verification results may require human-readable proofs involving multiple or potentially infinite inputs, making explanations challenging.
  • Runtime monitoring: Fairness-aware programming lets developers state probabilistic fairness expectations in code and uses runtime monitoring plus statistical inference to detect violations.

10 Open Challenges

The survey identifies unresolved challenges in defining, evaluating, and deploying fairness for rankings and recommender systems. It calls for clearer abstractions connecting values to measures, broader data-pipeline coverage, better evaluation, and evidence from real applications.

  • Definitions and value systems: There is no universal fairness definition, and some definitions are incompatible except in highly constrained cases.The survey also calls for making each definition’s interpretation of bias or diversity explicit.
  • Data and evaluation: Available data is often limited and acquired through processes over which data scientists have limited control, constraining bias analysis.The survey proposes future benchmarks for measuring societal impact, analogous to database-performance benchmarks.
  • Data and evaluation: Fairness must be addressed across the whole data pipeline, from data selection and cleaning through representation, visualization, and user interfaces.The survey notes that presenting results can itself introduce bias.
  • Data and evaluation: Existing evaluation tools mainly target statistical group fairness in classification, leaving tools for rankings, recommenders, datasets, algorithms, and systems underdeveloped.The survey also calls for efficient fairness measurement and monitoring over time.
  • Deployment and impact: The long-term social effects of fairness interventions remain an open question, including whether they could backfire in unpredictable ways.The survey presents this as a central question for future research.
  • Deployment and impact: Real-world applications remain limited because organizations must balance fairness with business metrics such as click-through rate and purchases.A LinkedIn Talent Search deployment improved fairness metrics without significant impact on business metrics in online A/B tests.
  • Definitions and value systems: Fairness definitions should distinguish value systems from the technical measures that codify them, with mappings across abstraction levels.The proposed architecture separates beliefs and value systems from higher-level fairness definitions and intermediate transformations.
  • Cross-context fairness: Fairness research needs unified treatment across decision-making contexts, while recognizing that models and algorithms may differ by application.The survey relates ranking and recommendation fairness to resource allocation, scheduling, cache allocation, and chairman selection.

11 Conclusions

The survey frames fairness in rankings and recommendations as important across consequential applications, but emphasizes that definitions and enforcement methods remain incompletely understood. It organizes existing knowledge systematically, surveys solution classes, and identifies broader research challenges without establishing which approach works best in each context.

  • Conclusions: Fairness matters in ranking and recommender applications such as hiring, lending, and college admissions because they involve decision making.
  • Conclusions: The survey systematically organizes general, ranking, recommendation, and rank-aggregation fairness definitions into a taxonomy and compares their differences and commonalities.It uses this analysis to formulate open questions about suitability, perception, and unified judgment of fairness.
  • Conclusions: Fairness solutions are classified as pre-processing, in-processing, and post-processing approaches, with further dimensions within each category.The survey reports that no common evaluation establishes which approach works best for which context.
  • Conclusions: The paper extends its discussion beyond rankings and recommendations to other decision systems and broader data-management challenges for designing and evaluating fair applications.
Loading 2104.05994v2…