Carnegie Mellon University
file.pdf (237.13 kB)

A Maximum Likelihood Approach For Selecting Sets of Alternatives

Download (237.13 kB)
journal contribution
posted on 2002-07-01, 00:00 authored by Ariel D. Procaccia, Sashank J. Reddi, Nisarg Shah

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 N P-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.


Publisher Statement

© ACM, 2002. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution.



Usage metrics