Preference Elicitation as Average-Case Sorting


  • Dominik Peters Harvard University
  • Ariel D. Procaccia Harvard University



Social Choice / Voting


Many decision making systems require users to indicate their preferences via a ranking. It is common to elicit such rankings through pairwise comparison queries. By using sorting algorithms, this can be achieved by asking at most O(m log m) adaptive comparison queries. However, in many cases we have some advance (probabilistic) information about the user's preferences, for instance if we have a learnt model of the user's preferences or if we expect the user's preferences to be correlated with those of previous users. For these cases, we design elicitation algorithms that ask fewer questions in expectation, by building on results for average-case sorting. If the user's preferences are drawn from a Mallows phi model, O(m) queries are enough; for a mixture of k Mallows models, log k + O(m) queries are enough; for Plackett-Luce models, the answer varies with the alternative weights. Our results match information-theoretic lower bounds. We also provide empirical evidence for the benefits of our approach.




How to Cite

Peters, D., & Procaccia, A. D. (2021). Preference Elicitation as Average-Case Sorting. Proceedings of the AAAI Conference on Artificial Intelligence, 35(6), 5647-5655.



AAAI Technical Track on Game Theory and Economic Paradigms