Caragiannis, Ioannis and Chatzigeorgiou, Xenophon and Krimpas, George A and Voudouris, Alexandros A (2019) Optimizing positional scoring rules for rank aggregation. Artificial Intelligence, 267. pp. 58-77. DOI https://doi.org/10.1016/j.artint.2018.11.001
Caragiannis, Ioannis and Chatzigeorgiou, Xenophon and Krimpas, George A and Voudouris, Alexandros A (2019) Optimizing positional scoring rules for rank aggregation. Artificial Intelligence, 267. pp. 58-77. DOI https://doi.org/10.1016/j.artint.2018.11.001
Caragiannis, Ioannis and Chatzigeorgiou, Xenophon and Krimpas, George A and Voudouris, Alexandros A (2019) Optimizing positional scoring rules for rank aggregation. Artificial Intelligence, 267. pp. 58-77. DOI https://doi.org/10.1016/j.artint.2018.11.001
Abstract
Nowadays, several crowdsourcing projects exploit social choice methods for computing an aggregate ranking of alternatives given individual rankings provided by workers. Motivated by such systems, we consider a setting where each worker is asked to rank a fixed (small) number of alternatives and, then, a positional scoring rule is used to compute the aggregate ranking. Among the apparently infinite such rules, what is the best one to use? To answer this question, we assume that we have partial access to an underlying true ranking. Then, the important optimization problem to be solved is to compute the positional scoring rule whose outcome, when applied to the profile of individual rankings, is as close as possible to the part of the underlying true ranking we know. We study this fundamental problem from a theoretical viewpoint and present positive and negative complexity results and, furthermore, complement our theoretical findings with experiments on real-world and synthetic data.
Item Type: | Article |
---|---|
Additional Information: | Accepted to Artificial Intelligence Journal. A preliminary version appeared in Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), pages 430-436, 2017 |
Uncontrolled Keywords: | Computational social choice; Positional scoring voting rules; Crowdsourcing; Learning and voting; Preference learning; Approximation algorithms |
Divisions: | Faculty of Science and Health Faculty of Science and Health > Computer Science and Electronic Engineering, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 20 May 2020 11:46 |
Last Modified: | 07 Aug 2024 20:41 |
URI: | http://repository.essex.ac.uk/id/eprint/27260 |
Available files
Filename: Optimizing+positional+scoring+rules+for+rank+aggregation.pdf
Licence: Creative Commons: Attribution-Noncommercial-No Derivative Works 3.0