Source-linked AI summary
Fairness of Exposure in Rankings
Ashudeep Singh, Thorsten Joachims
TL;DR
Online rankings allocate exposure to people and other items, so fairness must address ranked items as well as user utility. The paper develops a probabilistic-ranking and linear-programming framework for application-specific exposure constraints, with algorithms that optimize expected utility while satisfying fairness in expectation.
Problem
Ranking systems increasingly rank people and other consequential items, creating a need to balance user utility with responsibilities toward those items through application-appropriate fairness notions.
Method
The paper formulates exposure-based fairness constraints over probabilistic rankings and solves the resulting utility optimization with linear programming.
Results
The framework implements demographic parity, disparate treatment, and disparate impact, while sampled rankings satisfy fairness constraints in expectation and maximize expected utility.
Takeaways & Limitations
Fair exposure should remain expressible across applications because appropriate trade-offs between user utility and ranked-item rights may differ by setting.
Takeaways & Limitations
Group-level fairness can leave individual items within a group subject to disparate treatment or impact, and fairness constraints can substantially reduce utility.
Abstract
from arXiv · showhide
Rankings are ubiquitous in the online world today. As we have transitioned from finding books in libraries to ranking products, jobs, job applicants, opinions and potential romantic partners, there is a substantial precedent that ranking systems have a responsibility not only to their users but also to the items being ranked. To address these often conflicting responsibilities, we propose a conceptual and computational framework that allows the formulation of fairness constraints on rankings in terms of exposure allocation. As part of this framework, we develop efficient algorithms for finding rankings that maximize the utility for the user while provably satisfying a specifiable notion of fairness. Since fairness goals can be application specific, we show how a broad range of fairness constraints can be implemented using our framework, including forms of demographic parity, disparate treatment, and disparate impact constraints. We illustrate the effect of these constraints by providing empirical results on two ranking problems.
1 INTRODUCTION
Online rankings now allocate exposure for products, people, opinions, and opportunities, creating responsibilities to ranked items as well as users. The paper proposes fairness constraints that balance user utility with fair exposure across application-specific scenarios.
- Rankings have expanded from library search to products, jobs, job seekers, opinions, and potential romantic partners.
- Because position largely determines exposure, rankings can affect interviews, rentals, readership, legal risk, and reputational risk.
- The paper frames fairness as an application-specific trade-off between utility for users and rights of ranked items.
- A job-seeker example shows how small relevance differences can produce large exposure and economic-opportunity differences between groups.The example ranks six applicants with slightly higher relevance scores for male applicants and uses position-biased exposure.
- An image-search example illustrates how disproportionate representation of male CEOs can make rankings appear biased when results serve as a statistical sample.
- The paper also connects ranking fairness to whether speakers’ speech reaches interested listeners, linking exposure allocation with freedom of speech.
2 RELATED WORK
Prior work addresses fairness in supervised learning, rankings, and diversified retrieval, but much ranking research focuses on parity or user utility alone. This paper positions its framework as a broader way to compute optimal probabilistic rankings under varied fairness constraints.
- The paper relates its approach to algorithmic fairness in supervised learning, fairness for rankings, and diversified ranking in information retrieval.
- Earlier ranking measures often restrict the fraction of items with each attribute in ranking prefixes or use parity-based regularization.
- The proposed framework goes beyond parity constraints by efficiently computing optimal probabilistic rankings for a large class of fairness constraints.
- Related concurrent work focuses on individual fairness and uses integer linear programming, whereas this framework treats individual fairness as protected groups of size one.
- Unlike diversified ranking and the Probability Ranking Principle, this approach balances user utility with the needs of ranked items.
3 A FRAMEWORK FOR RANKING UNDER FAIRNESS CONSTRAINTS
The framework optimizes ranking utility subject to flexible fairness constraints by replacing deterministic rankings with probabilistic rankings represented through doubly stochastic matrices and solved using linear programming.
- Framework motivation: Fairness depends on context, so the framework supports application-specific constraints rather than a single definition of fair ranking.Different fairness notions can imply different utility trade-offs.
- Optimization formulation: The framework generalizes the Probability Ranking Principle by treating it as the special case with no fairness constraints.Without fairness constraints, decreasing position attention yields ranking by document utility.
- Probabilistic rankings: Probabilistic rankings replace exponential search over deterministic rankings, while expected utility is computed from documents’ marginal rank probabilities in a doubly stochastic matrix P.P_ij denotes the probability that document d_i appears at rank j.
- Linear programming: The utility-maximization problem becomes a linear program over P, with linear doubly stochastic and fairness constraints.Fairness constraints can be written as f^T P g = h, where f and g encode document and position properties.
- Recovering rankings: A probabilistic ranking R can be recovered from P using Birkhoff-von Neumann decomposition into permutation matrices.The permutation matrices represent deterministic rankings, and their coefficients determine sampling probabilities.
- Algorithm outcome: The sampled rankings satisfy the specified fairness constraints in expectation while maximizing expected utility.The framework assumes true relevance values u(d|q), although practical systems would use predictive estimates.
4 CONSTRUCTING GROUP FAIRNESS CONSTRAINTS
The framework expresses demographic parity, disparate treatment, and disparate impact as exposure-allocation constraints, then computes utility-maximizing rankings subject to them. Experiments on job-seeker and news-recommendation data show that these constraints alter rankings and trade off fairness against DCG to different degrees.
- The framework implements demographic parity, disparate treatment, and disparate impact as linear exposure constraints that can be enforced efficiently with provable guarantees.
- Demographic Parity Constraints: Demographic parity equalizes average exposure across groups without using relevance, which can substantially reduce utility when group relevance distributions differ.In the job-seeker example, DCG decreases from 3.8193 for the unfair ranking to 3.8031 for the fair ranking; much larger losses are possible when female relevance is lowered.
- Demographic Parity Constraints: The demographic-parity job-seeker ranking is stochastic but decomposes into a mixture of two deterministic permutation matrices.
- Demographic Parity Constraints: On the news dataset, demographic parity moves G1 documents from starting at position 5 to starting at rank 1 or 2, producing an almost deterministic fair ranking.
- Disparate Treatment Constraints: Disparate treatment makes exposure depend on relevance, and the job-seeker fair ranking achieves the target DTR while retaining more DCG than demographic parity.The corresponding fair ranking is decomposed into three permutation matrices.
- Disparate Treatment Constraints: For news recommendation, disparate treatment has very little impact on DCG because the unconstrained ranking is already almost fair under that criterion.
- Disparate Impact Constraints: Disparate impact substantially improves DIR in the job-seeker and news experiments, while reducing DCG relative to unconstrained rankings.For news recommendation, DCG remains higher than under demographic parity and lower than under the unconstrained and disparate-treatment rankings.
5 DISCUSSION
The framework supports multiple group-fairness constraints, but fair rankings can remain unfair within groups, depend on utility estimates, incur utility costs, or be infeasible under extreme conditions.
- Fairness framework: The framework implements demographic parity, disparate treatment, and disparate impact, while emphasizing that fairness constraints are application-specific trade-offs.It is designed to cover a substantial range of fairness constraints rather than prescribe a single correct definition.
- Group fairness vs. individual fairness: Group-level guarantees do not ensure individual fairness within groups, although protected groups of size one can express individual fairness.Additional constraints over attributes such as race, disability, and national origin can further refine the fairness notion.
- Using estimated utilities: The framework assumes access to true expected utilities, whereas practical systems estimate relevances with machine-learning models that may inherit selection bias from click data.Counterfactual learning techniques are cited as permitting unbiased learning-to-rank despite biased click data.
- Cost of fairness: Fairness constraints can reduce effectiveness, with demographic parity approaching zero utility when all relevant documents are in one group and the other group grows indefinitely.The cost of fairness is quantified as CoF = uT(P*−P)v.
- Feasibility of fair solutions: The linear program may have no fair solution when relevance ratios fall outside the exposure range achievable by varying the ranking.For disparate treatment, extreme relevance configurations can make the constraint infeasible.
- Feasibility of fair solutions: Adding documents outside the two compared groups, or from the more relevant group, can widen the achievable exposure range and restore feasibility without undue exposure.This adjustment can satisfy the constraint in scenarios where the original ranking problem is otherwise constrained.
6 CONCLUSIONS
The paper frames ranking fairness as exposure allocation between groups and uses probabilistic rankings with linear programming to optimize utility under flexible fairness constraints. It expresses demographic parity, disparate treatment, and disparate impact, arguing that appropriate fair exposure depends on the application.
- The paper treats ranking fairness as an exposure-allocation problem between groups.
- It uses probabilistic rankings and linear programming to compute utility-maximizing rankings under a class of fairness constraints.
- The framework expresses constraints motivated by demographic parity, disparate treatment, and disparate impact.
- The paper concludes that the appropriate definition of fair exposure depends on the application, making an expressive framework desirable.