The Art of Calling the Winner by Asking Just Enough Questions

Nisarg Shah, Ziqi Yu
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:6149-6164, 2026.

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 most 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 the best competitive ratio is sublinear in $m$ for many positional scoring rules but linear in $m$ for all Condorcet-consistent rules. Our analysis centers on a simple elicitation algorithm we propose, which not only achieves optimal theoretical bounds, but also impressive empirical performance on real data.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-shah26a, title = {The Art of Calling the Winner by Asking Just Enough Questions}, author = {Shah, Nisarg and Yu, Ziqi}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {6149--6164}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/shah26a/shah26a.pdf}, url = {https://proceedings.mlr.press/v337/shah26a.html}, 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 most 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 the best competitive ratio is sublinear in $m$ for many positional scoring rules but linear in $m$ for all Condorcet-consistent rules. Our analysis centers on a simple elicitation algorithm we propose, which not only achieves optimal theoretical bounds, but also impressive empirical performance on real data.} }
Endnote
%0 Conference Paper %T The Art of Calling the Winner by Asking Just Enough Questions %A Nisarg Shah %A Ziqi Yu %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-shah26a %I PMLR %P 6149--6164 %U https://proceedings.mlr.press/v337/shah26a.html %V 337 %X 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 most 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 the best competitive ratio is sublinear in $m$ for many positional scoring rules but linear in $m$ for all Condorcet-consistent rules. Our analysis centers on a simple elicitation algorithm we propose, which not only achieves optimal theoretical bounds, but also impressive empirical performance on real data.
APA
Shah, N. & Yu, Z.. (2026). The Art of Calling the Winner by Asking Just Enough Questions. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:6149-6164 Available from https://proceedings.mlr.press/v337/shah26a.html.

Related Material