The Art of Calling the Winner by Asking Just Enough Questions: Competitive Preference Elicitation with Next-Best Queries
Computer Science and Game Theory
Summary
The authors study how to efficiently ask people about their preferences to pick a winner from multiple options using voting rules. They focus on a setup where each question asks a person for their next favorite choice, and they measure how many questions are needed compared to the absolute minimum. They find that for some scoring methods, fewer questions are needed (sublinear growth), but for others like Condorcet rules, the number of questions grows proportionally to the number of options. They introduce new techniques for the Borda count method, proving that their approach requires fewer questions in the worst case and works well in practice.
Authors
Nisarg Shah, Ziqi Yu
Abstract
We study active elicitation of agent preferences for collectively choosing among $m$ alternatives using prominent voting rules. We focus on the next-best query model, in which an agent responds to a query by revealing their next favorite alternative, and measure the competitive ratio, which is the worst-case ratio between the number of queries made by the active elicitation algorithm and the minimum number of queries needed to reveal the winning alternative(s) in hindsight. We show that sublinear competitive ratios are achievable for many positional scoring rules, whereas every Condorcet-consistent rule has competitive ratio linear in $m$. For Borda count, we develop two complementary techniques: level-wise pruning, whose analysis extends to general concave scoring rules, and multi-scale score thresholding, which gives an $O(\sqrt m)$ worst-case guarantee for Borda. We also demonstrate strong empirical performance of level-wise pruning on real data.