Maxmin-Fair Ranking: Individual Fairness under Group-Fairness
  Constraints
  We study a novel problem of fairness in ranking aimed at minimizing the
amount of individual unfairness introduced when enforcing group-fairness
constraints. Our proposal is rooted in the distributional maxmin fairness
theory, which uses randomization to maximize the expected satisfaction of the
worst-off individuals. We devise an exact polynomial-time algorithm to find
maxmin-fair distributions of general search problems (including, but not
limited to, ranking), and show that our algorithm can produce rankings which,
while satisfying the given group-fairness constraints, ensure that the maximum
possible value is brought to individuals.
