FA*IR: A Fair Top-k Ranking Algorithm

Abstract

In this work, we define and solve the Fair Top-k Ranking problem, in which we want to determine a subset of k candidates from a large pool of n >> k candidates, maximizing utility (i.e., select the "best" candidates) subject to group fairness criteria. Our ranked group fairness definition extends group fairness using the standard notion of protected groups and is based on ensuring that the proportion of protected candidates in every prefix of the top-k ranking remains statistically above or indistinguishable from a given minimum. Utility is operationalized in two ways: (i) every candidate included in the top-$k$ should be more qualified than every candidate not included; and (ii) for every pair of candidates in the top-k, the more qualified candidate should be ranked above. An efficient algorithm is presented for producing the Fair Top-k Ranking, and tested experimentally on existing datasets as well as new datasets released with this paper, showing that our approach yields small distortions with respect to rankings that maximize utility without considering fairness criteria. To the best of our knowledge, this is the first algorithm grounded in statistical tests that can mitigate biases in the representation of an under-represented group along a ranked list.

In Proceedings of the 26th ACM International Conference on Information and Knowledge Management (CIKM'17). This version corrects an error on Table 4

References in corpus (8)

• Equality of Opportunity in Supervised Learning
• Inherent Trade-Offs in the Fair Determination of Risk Scores
• On the (im)possibility of fairness
• Quantifying Search Bias: Investigating Sources of Bias for Political Searches in Social Media
• Exposing the Probabilistic Causal Structure of Discrimination
• How to be Fair and Diverse?
• Measuring Fairness in Ranked Outputs
• Fairness in Reinforcement Learning

Cited by in corpus (113)

• Mitigating Bias in Algorithmic Hiring: Evaluating Claims and Practices
• Fairness of Exposure in Rankings
• Fairness in Machine Learning: A Survey
• Fairness in Machine Learning: Lessons from Political Philosophy
• Fairness-Aware Ranking in Search & Recommendation Systems with Application to LinkedIn Talent Search
• Equity of Attention: Amortizing Individual Fairness in Rankings
• Beyond Personalization: Research Directions in Multistakeholder Recommendation
• Bias in Bios: A Case Study of Semantic Representation Bias in a High-Stakes Setting
• Evaluating Stochastic Rankings with Expected Exposure
• Designing Fair Ranking Schemes
• User-centered Evaluation of Popularity Bias in Recommender Systems
• FairSight: Visual Analytics for Fairness in Decision Making
• A Nutritional Label for Rankings
• Fighting Fire with Fire: Using Antidote Data to Improve Polarization and Fairness of Recommender Systems
• Fairness in Ranking: A Survey
• Operationalizing Individual Fairness with Pairwise Fair Representations
• A Graph-based Approach for Mitigating Multi-sided Exposure Bias in Recommender Systems
• User Fairness, Item Fairness, and Diversity for Rankings in Two-Sided Markets
• Interplay between Upsampling and Regularization for Provider Fairness in Recommender Systems
• Societal Biases in Retrieved Contents: Measurement Framework and Adversarial Mitigation for BERT Rankers
• Human-Centric Multimodal Machine Learning: Recent Advances and Testbed on AI-based Recruitment
• Ride-share matching algorithms generate income inequality
• Evaluation Metrics for Measuring Bias in Search Engine Results
• Policy Learning for Fairness in Ranking
• Maximizing Marginal Fairness for Dynamic Learning to Rank
• Policy-Gradient Training of Fair and Unbiased Ranking Functions
• The few-get-richer: a surprising consequence of popularity-based rankings
• De-biasing "bias" measurement
• Assessing Viewpoint Diversity in Search Results Using Ranking Fairness Metrics
• Fair and Diverse Allocation of Scarce Resources
• Unbiased Cascade Bandits: Mitigating Exposure Bias in Online Learning to Rank Recommendation
• Fairness of Exposure in Light of Incomplete Exposure Estimation
• Understanding and Mitigating the Effect of Outliers in Fair Ranking
• Popularity Bias in Recommendation: A Multi-stakeholder Perspective
• Achieving Fairness in the Stochastic Multi-armed Bandit Problem
• Intersectional Two-sided Fairness in Recommendation
• Fairness-Aware Explainable Recommendation over Knowledge Graphs
• FAIR: Fairness-Aware Information Retrieval Evaluation
• Learning Fair Scoring Functions: Bipartite Ranking under ROC-based Fairness Constraints
• It's Not You, It's Me: The Impact of Choice Models and Ranking Strategies on Gender Imbalance in Music Recommendation
• Representativity Fairness in Clustering
• FairSearch: A Tool For Fairness in Ranked Search Results
• Diverse Data Selection under Fairness Constraints
• Reducing Disparate Exposure in Ranking: A Learning To Rank Approach
• Introducing the Expohedron for Efficient Pareto-optimal Fairness-Utility Amortizations in Repeated Rankings
• Happiness Maximizing Sets under Group Fairness Constraints (Technical Report)
• Subverting Fair Image Search with Generative Adversarial Perturbations
• Addressing the Multistakeholder Impact of Popularity Bias in Recommendation Through Calibration
• RecSim NG: Toward Principled Uncertainty Modeling for Recommender Ecosystems
• Probabilistic Permutation Graph Search: Black-Box Optimization for Fairness in Ranking
• Deontological Ethics By Monotonicity Shape Constraints
• Unmasking Gender Bias in Recommendation Systems and Enhancing Category-Aware Fairness
• Balanced Ranking with Diversity Constraints
• Predictive Uncertainty-based Bias Mitigation in Ranking
• Vertical Allocation-based Fair Exposure Amortizing in Ranking
• Marginal-Certainty-aware Fair Ranking Algorithm
• Regulating Group Exposure for Item Providers in Recommendation
• Overview of the TREC 2020 Fair Ranking Track
• Fairness Rising from the Ranks: HITS and PageRank on Homophilic Networks
• Representation Online Matters: Practical End-to-End Diversification in Search and Recommender Systems
• FairSort: Learning to Fair Rank for Personalized Recommendations in Two-Sided Platforms
• Hypergraph Clustering for Finding Diverse and Experienced Groups
• On the Problem of Underranking in Group-Fair Ranking
• A Framework for Fairness in Two-Sided Marketplaces
• Driving the Herd: Search Engines as Content Influencers
• A Ranking Approach to Fair Classification
• On Discrimination Discovery and Removal in Ranked Data using Causal Graph
• Bias-Aware Agent: Enhancing Fairness in AI-Driven Knowledge Retrieval
• Identifying Biased Subgroups in Ranking and Classification
• Intersectional Affirmative Action Policies for Top-k Candidates Selection
• FARA: Future-aware Ranking Algorithm for Fairness Optimization
• Fairness-Aware Recommendation of Information Curators
• Quantifying the Impact of User Attention on Fair Group Representation in Ranked Lists
• Consequential Ranking Algorithms and Long-term Welfare
• A Conceptual Framework for Evaluating Fairness in Search
• Individually Fair Ranking
• Investigating Societal Biases in a Poetry Composition System
• Mapping Stakeholder Needs to Multi-Sided Fairness in Candidate Recommendation for Algorithmic Hiring
• Learn to be Fair without Labels: a Distribution-based Learning Framework for Fair Ranking
• Fair Set Cover
• Fairness in Ranking under Disparate Uncertainty
• The FairCeptron: A Framework for Measuring Human Perceptions of Algorithmic Fairness
• Fairness Through Regularization for Learning to Rank
• Pairwise Fairness for Ranking and Regression
• hyperFA*IR: A hypergeometric approach to fair rankings with finite candidate pool
• Fair Outlier Detection
• RAGUEL: Recourse-Aware Group Unfairness Elimination
• Language Fairness in Multilingual Information Retrieval
• Quota-based debiasing can decrease representation of already underrepresented groups
• FiSH: Fair Spatial Hotspots
• Affirmative Action Policies for Top-k Candidates Selection, With an Application to the Design of Policies for University Admissions
• Towards Model-Agnostic Post-Hoc Adjustment for Balancing Ranking Fairness and Algorithm Utility
• Users' Perception of Search Engine Biases and Satisfaction
• A Reproducibility Study of Product-side Fairness in Bundle Recommendation
• Learning to Re-rank with Constrained Meta-Optimal Transport
• Maxmin-Fair Ranking: Individual Fairness under Group-Fairness Constraints
• Towards More Accountable Search Engines: Online Evaluation of Representation Bias
• FAST: A Fairness Assured Service Recommendation Strategy Considering Service Capacity Constraint
• Using Image Fairness Representations in Diversity-Based Re-ranking for Recommendations
• A Note on the Significance Adjustment for FA*IR with Two Protected Groups
• Fairness-Aware Online Personalization
• Estimation of Fair Ranking Metrics with Incomplete Judgments
• Prior Signal Editing for Graph Filter Posterior Fairness Constraints
• Practical Compositional Fairness: Understanding Fairness in Multi-Component Recommender Systems
• Robust Reputation Independence in Ranking Systems for Multiple Sensitive Attributes
• Understanding the impact of the alphabetical ordering of names in user interfaces: a gender bias analysis
• Joint Evaluation of Fairness and Relevance in Recommender Systems with Pareto Frontier
• Searching Personal Collections
• Gender Stereotype Reinforcement: Measuring the Gender Bias Conveyed by Ranking Algorithms
• Facets of Fairness in Search and Recommendation
• Pairwise Fairness for Ordinal Regression
• Recommendation or Discrimination?: Quantifying Distribution Parity in Information Retrieval Systems
• How Fair is Fairness-aware Representative Ranking and Methods for Fair Ranking