Ranking with Slot Constraints
Wentao Guo Andrew Wang Bradon Thymes Thorsten Joachims
We introduce the problem of ranking with slot constraints, which can be used
to model a wide range of application problems -- from college admission with
limited slots for different majors, to composing a stratified cohort of
eligible participants in a medical trial. We show that the conventional
Probability Ranking Principle (PRP) can be highly sub-optimal for
slot-constrained ranking problems, and we devise a new ranking algorithm,
called MatchRank. The goal of MatchRank is to produce rankings that maximize
the number of filled slots if candidates are evaluated by a human decision
maker in the order of the ranking. In this way, MatchRank generalizes the PRP,
and it subsumes the PRP as a special case when there are no slot constraints.
Our theoretical analysis shows that MatchRank has a strong approximation
guarantee without any independence assumptions between slots or candidates.
Furthermore, we show how MatchRank can be implemented efficiently. Beyond the
theoretical guarantees, empirical evaluations show that MatchRank can provide
substantial improvements over a range of synthetic and real-world tasks.