Exact Learning of Preference Structure: Single-peaked Preferences and Beyond

Sonja Kraiczy, Edith Elkind
Proceedings of the 39th International Conference on Machine Learning, PMLR 162:11598-11612, 2022.

Abstract

We consider the setting where the members of a society (voters) have preferences over candidates, and the candidates can be ordered on an axis so that the voters’ preferences are single-peaked on this axis. We ask whether this axis can be identified by sampling the voters’ preferences. For several natural distributions, we obtain tight bounds on the number of samples required and show that, surprisingly, the bounds are independent of the number of candidates. We extend our results to the case where voters’ preferences are sampled from two different axes over the same candidate set (one of which may be known). We also consider two alternative models of learning: (1) sampling pairwise comparisons rather than entire votes, and (2) learning from equivalence queries.

Cite this Paper

BibTeX
@InProceedings{pmlr-v162-kraiczy22a, title = {Exact Learning of Preference Structure: Single-peaked Preferences and Beyond}, author = {Kraiczy, Sonja and Elkind, Edith}, booktitle = {Proceedings of the 39th International Conference on Machine Learning}, pages = {11598--11612}, year = {2022}, editor = {Chaudhuri, Kamalika and Jegelka, Stefanie and Song, Le and Szepesvari, Csaba and Niu, Gang and Sabato, Sivan}, volume = {162}, series = {Proceedings of Machine Learning Research}, month = {17--23 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v162/kraiczy22a/kraiczy22a.pdf}, url = {https://proceedings.mlr.press/v162/kraiczy22a.html}, abstract = {We consider the setting where the members of a society (voters) have preferences over candidates, and the candidates can be ordered on an axis so that the voters’ preferences are single-peaked on this axis. We ask whether this axis can be identified by sampling the voters’ preferences. For several natural distributions, we obtain tight bounds on the number of samples required and show that, surprisingly, the bounds are independent of the number of candidates. We extend our results to the case where voters’ preferences are sampled from two different axes over the same candidate set (one of which may be known). We also consider two alternative models of learning: (1) sampling pairwise comparisons rather than entire votes, and (2) learning from equivalence queries.} }
Endnote
%0 Conference Paper %T Exact Learning of Preference Structure: Single-peaked Preferences and Beyond %A Sonja Kraiczy %A Edith Elkind %B Proceedings of the 39th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2022 %E Kamalika Chaudhuri %E Stefanie Jegelka %E Le Song %E Csaba Szepesvari %E Gang Niu %E Sivan Sabato %F pmlr-v162-kraiczy22a %I PMLR %P 11598--11612 %U https://proceedings.mlr.press/v162/kraiczy22a.html %V 162 %X We consider the setting where the members of a society (voters) have preferences over candidates, and the candidates can be ordered on an axis so that the voters’ preferences are single-peaked on this axis. We ask whether this axis can be identified by sampling the voters’ preferences. For several natural distributions, we obtain tight bounds on the number of samples required and show that, surprisingly, the bounds are independent of the number of candidates. We extend our results to the case where voters’ preferences are sampled from two different axes over the same candidate set (one of which may be known). We also consider two alternative models of learning: (1) sampling pairwise comparisons rather than entire votes, and (2) learning from equivalence queries.
APA
Kraiczy, S. & Elkind, E.. (2022). Exact Learning of Preference Structure: Single-peaked Preferences and Beyond. Proceedings of the 39th International Conference on Machine Learning, in Proceedings of Machine Learning Research 162:11598-11612 Available from https://proceedings.mlr.press/v162/kraiczy22a.html.

Related Material