A Theoretical Framework for Risk Analysis of Stochastic Rankers
2026-06-15 • Information Retrieval
Information Retrieval
AI summaryⓘ
The authors study stochastic ranking policies that create a range of possible rankings instead of a single fixed order to improve diversity or fairness. They focus on understanding how much the effectiveness of search results can vary before actually picking a ranking from these policies. By analyzing a measure called discounted cumulative gain (DCG), they find that this variation depends on how relevant items are distributed in the original list. Their experiments with real data show that their theoretical predictions about effectiveness changes match what happens in practice.
stochastic rankingdeterministic rankersdiscounted cumulative gain (DCG)retrieval effectivenessrerankingpermutation distributionrecall pointsTREC Fairness trackdiversity in information retrievalfair exposure
Authors
Debasis Ganguly
Abstract
Different from deterministic rankers that seek to maximize relevance at top ranks, stochastic ranking policies instead estimate distributions over permutations, from which rankings are sampled, towards obtaining diversified or fair exposure. Such policies are commonly evaluated in terms of expected effectiveness postreranking. However, the randomness inherent in these policies gives rise to a fundamental but under-explored ex ante question: prior to applying stochastic reranking, how large can the induced variation in retrieval effectiveness be in the worst case? This paper presents a theoretical analysis of reranking risk, defined as the maximum absolute change in discounted cumulative gain (DCG) resulting from a permutation sampled from a stochastic reranking policy applied to a fixed retrieved list.We derive that this risk is governed by the distribution of the recall points in the initial retrieved list. We conduct experiments on submitted runs from the TREC Fairness 2022 track that employ stochastic reranking policies and empirically demonstrate that the effectiveness variations predicted by our theory closely approximate the observed changes in DCG.