A Maximum Likelihood Approach For Selecting Sets of Alternatives
This addresses selection problems in ranking and decision-making, but appears incremental as it generalizes classical results.
The paper tackles the problem of selecting a subset of alternatives from noisy evaluations, aiming for maximum likelihood objectives like containing the strongest alternative, and shows that intuitive methods are optimal under high noise conditions, with experiments indicating good practical performance.
We consider the problem of selecting a subset of alternatives given noisy evaluations of the relative strength of different alternatives. We wish to select a k-subset (for a given k) that provides a maximum likelihood estimate for one of several objectives, e.g., containing the strongest alternative. Although this problem is NP-hard, we show that when the noise level is sufficiently high, intuitive methods provide the optimal solution. We thus generalize classical results about singling out one alternative and identifying the hidden ranking of alternatives by strength. Extensive experiments show that our methods perform well in practical settings.