Aggregating votes that are preference orders over candidates or alternatives is a fundamental problem of decision theory and social choice. We study this problem in the setting when alternatives are described as tuples of values of attributes. The combinatorial spaces of such alternatives make explicit enumerations of alternatives from the most to the least preferred infeasible. Instead, votes may be specified implicitly in terms of some compact and intuitive preference representation mechanism. In our work, we assume that votes are given as lexicographic preference trees and consider two preference-aggregation problems, the winner problem and the evaluation problem. We study them under the assumption that positional scoring rules are used for aggregation. In particular, we consider k-Approval and b-Borda, a generalized Borda rule, and we discover new computational complexity results for them.
|Title of host publication||Algorithmic Decision Theory - 6th International Conference, ADT 2019, Proceedings|
|Editors||Saša Pekec, Kristen Brent Venable|
|Number of pages||15|
|State||Published - 2019|
|Event||6th International Conference on Algorithmic Decision Theory, ADT 2019 - Durham, United States|
Duration: Oct 25 2019 → Oct 27 2019
|Name||Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)|
|Conference||6th International Conference on Algorithmic Decision Theory, ADT 2019|
|Period||10/25/19 → 10/27/19|
Bibliographical noteFunding Information:
The work of the second author was supported by the NSF grant IIS-1618783.
The work of the second author was supported by the NSF grant
© 2019, Springer Nature Switzerland AG.
ASJC Scopus subject areas
- Theoretical Computer Science
- Computer Science (all)