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.
Department of Computer Science University of Illinois Chicago Chicago, IL 60607 · Department of Electrical and Computer Engineering University of Illinois Chicago Chicago, IL 60607