Sampling Random Group Fair Rankings

In this paper, we take an axiomatic approach to define random group-fair rankings that satisfy a natural set of consistency and fairness axioms. We show that this leads to a unique distribution $\mathcal{D}$ over rankings obtained by merging given ranked list of items from different sensitive demographic groups while satisfying given lower and upper bounds on the representation of each group in the top ranks. Randomized or stochastic rankings have been of interest in recent literature for offering better fairness and robustness than deterministic rankings. Our problem formulation works even when there is implicit bias, incomplete relevance information, or when only ordinal ranking is available instead of relevance scores or utility values. We propose three algorithms to sample a random group fair ranking from the distribution $\mathcal{D}$ mentioned above. Our first algorithm samples rankings from a distribution $\epsilon$-close to $\mathcal{D}$ in total variation distance, and has expected running time polynomial in all input parameters and $1/\epsilon$, when there is a sufficient gap between upper and lower bound representation constraints for all the groups. Our second algorithm samples rankings from $\mathcal{D}$ exactly, in time exponential in the number of groups. Our third algorithm samples random group fair rankings from $\mathcal{D}$ exactly and is faster than the first algorithm when the gap between upper and lower bounds on the representation for each group is small. We experimentally validate the above guarantees of our algorithms for group fairness in top ranks and representation in every rank on real-world data sets.