PAC Rank Elicitation through Adaptive Sampling of Stochastic Pairwise Preferences


  • Róbert Busa-Fekete MTA-SZTE
  • Balázs Szörényi INRIA Lille
  • Eyke Hüllermeier University of Paderborn



rank elicitation, PAC, adaptive sampling, sample complexity


We introduce the problem of PAC rank elicitation, which consists of sorting a given set of options based on adaptive sampling of stochastic pairwise preferences. More specifically, we assume the existence of a ranking procedure, such as Copeland's method, that determines an underlying target order of the options. The goal is to predict a ranking that is sufficiently close to this target order with high probability, where closeness is measured in terms of a suitable distance measure. We instantiate this setting with combinations of two different distance measures and ranking procedures. For these instantiations, we devise efficient strategies for sampling pairwise preferences and analyze the corresponding sample complexity. We also present first experiments to illustrate the practical performance of our methods.




How to Cite

Busa-Fekete, R., Szörényi, B., & Hüllermeier, E. (2014). PAC Rank Elicitation through Adaptive Sampling of Stochastic Pairwise Preferences. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1).



Main Track: Novel Machine Learning Algorithms