Preference Elicitation as Average-Case Sorting

Authors

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

Keywords:

Social Choice / Voting

Abstract

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.

Downloads

Published

2021-05-18

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. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16709

Issue

Section

AAAI Technical Track on Game Theory and Economic Paradigms