We study the problem of fair ranking in recommender systems. We provide a formal probabilistic framework in which ranking policies are distributions over permutations, and the utility of a user is the exposure given to the items they interact with, relative to that of an ideal ranking. We consider utility parity across user groups, as well as its category-aware refinement, conditional utility parity, which requires parity within each category of items. Following a recent view of fairness as distributional stability, we show that both criteria are equivalent to the stability of the utility under changes in the composition of user groups. Optimizing over mixtures of ranking policies leads to a second-order cone program, for which we provide generalization bounds. A numerical study validates our theoretical findings.
Figures & tables
Figure 1: Synthetic data. (a, b) Utility gaps (women − men) under UP and CUP with free targets. (c) Utility. (d) CUP with targets ta=κΦa(P0;μΞ) at β=0.5 , relative to P0 . Means and standard deviations over 3 seeds.
Figure 2: MovieLens-1M. Each policy is compared with its backbone B . Utility against the largest gap between women and men over genres (a), and against the worst-case utility loss 1−minaminξΦa(P;ξ)/minξΦa(B;ξ) (b), both relative to B ; the best policies lie in the upper left corner. UP and CUP vary the target level κ from 1 (top) to 0.8 (bottom); hollow squares are values feasible on part of the splits only ( 6/10 for κ=1 , 9/10 for κ=0.95 ). CUP without target varies the budget λ , and CatFAIR the fairness regularisation parameter. (c) Per genre, for CUP ( κ=0.9 ) and the other baselines next to their backbones: gap between women and men divided by the utility of the genre under B (top), and change of this utility with respect to B (bottom). Means and standard errors over 10 splits.
Appendix figures & tables5 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 3: Synthetic data, deployment on new users ( β=0.5 , λ=5 ). Utility of the mixtures selected on the estimation users (share of women 0.4 ), as a function of the share of women among new users, relative to its mean value at 0.5 . Means and standard deviations over 3 seeds.
genre
movies
relevant items
share of relevant items
women
men
Sci-Fi
138
13953
0.14
0.19
Adventure
108
8155
0.08
0.11
Crime
182
11615
0.12
0.15
Romance
424
24360
0.40
0.28
Children’s
159
10307
0.15
0.12
Appendix
Table 1: MovieLens-1M after preprocessing: 5018 users, of which 28% women, and 1280 movies. On average, a user has 61 history items (median 39 ), 16 relevant items (median 10 ) and 1219 candidates. Share of relevant items: share of the relevant items of each group that belong to the genre.
policy
description
uniform
every candidate at every position with equal probability
popularity
log(1+ni) , the same ranking for every user
PureSVD
⟨eu,qi⟩
P0
unweighted
ξ -reweighted (5)
weights wξ(g) , ξ∈{0.1,0.3,0.5,0.7,0.9}
one group (2)
trained on the users of one group, deployed on all users
Appendix
Table 2: Dictionary on MovieLens-1M. All policies but the first three are LambdaMART models trained on the same rows.
κ
λ
1
0.95
0.9
0.85
0.8
1
0
0
0
0
1
1.5
1
3
5
7
7
2
6
9
10
10
10
≥3
10
10
10
10
10
Appendix
Table 3: Number of splits (out of 10) on which CUP is feasible.
step
time
UP and CUP
PureSVD and features
0.2 s
fitting the 16 LightGBM rankers
50 s
scoring the candidates of estimation and test users
81 s
utilities of the 19 policies
1.6 s
one SOCP, UP / CUP
2.5 / 7.4 ms
Appendix
Table 4: Computation time on MovieLens-1M, per split.
One of the many fairness definitions pursued in recent recommender system research targets mitigating demographic information encoded in model representations. Models optimized for this definition are typically evaluated on how well demographic attributes can be classified given model representations, with the (implicit) assumption that this measure accurately reflects recommendation parity, i.e., how similar recommendations given to different users are. We challenge this assumption by comparing the amount of demographic information encoded in representations with various measures of how the recommendations differ. We propose two new approaches for measuring how well demographic information can be classified given ranked recommendations. Our results from extensive testing of multiple models on one real and multiple synthetically generated datasets indicate that optimizing for fair representations positively affects recommendation parity, but also that evaluation at the representation level is not a good proxy for measuring this effect when comparing models. We also provide extensive insight into how recommendation-level fairness metrics behave for various models by evaluating their performances on numerous generated datasets with different properties.
Bjørnar Vassøy, Benjamin Kille, Helge Langseth
Norwegian University of Science and Technology, Trondheim, Norway
Scoring functions are used to represent the relevance of individual documents. In modern information retrieval or recommendation systems, they are often learned from data and play a pivotal role in ranking sets of documents or items in a way that maximizes utility to a query or user. With the recent interest in algorithmic fairness, the success of scoring has naturally led to methods that learn scores that simultaneously trade off fairness and utility. In this work, we show that in stark contrast with utility-centric objectives, scoring is sub-optimal in achieving all utility-fairness trade-offs. We establish this with a series of counter-examples with a generic fairness formulation. We show that the issue persists whether we have a deterministic scoring function or a randomized one, or whether we measure fairness at the scope of a single query or across multiple queries. On the positive side, we empirically demonstrate that semi-greedy post-processing has the potential to achieve much better trade-offs, often approaching the ideal of exhaustive post-processing in a tractable way.
Shubham Singh, Ian A. Kash, Mesrob I. Ohannessian
Department of Computer Science University of Illinois Chicago Chicago, IL 60607 · Department of Electrical and Computer Engineering University of Illinois Chicago Chicago, IL 60607
We view fairness as a property of distributional stability. Rather than assessing a predictor under a fixed data distribution, we study how its predictions change under perturbations that modify the composition of protected groups. A predictor is fair if it remains stable under such shifts. Under this perspective, several classical notions of fairness arise as stability with respect to specific perturbations, with the associated unfairness gap given by a Lipschitz constant of a prediction-rate functional. This formulation also yields guarantees that hold uniformly over a range of demographic compositions at test time, without requiring knowledge of the deployment distribution. It leads to a learning procedure based on convex combinations of reweighted predictors, formulated as a second-order cone program, for which we establish generalization bounds. Experiments on standard benchmarks illustrate the approach.
Gayane Taturyan, Charlotte Laclau, Stephan Clémencon
LTCI, Télécom Paris, Institut Polytechnique de Paris, Palaiseau, France