Hidden Disparities in Ranking: Category-Aware Fairness via Distributional Stability

Gayane Taturyan, Charlotte Laclau, Stephan Clémençon

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.