New complexity results on aggregating lexicographic preference trees using positional scoring rules

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

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.

Original languageEnglish
Title of host publicationAlgorithmic Decision Theory - 6th International Conference, ADT 2019, Proceedings
EditorsSaša Pekec, Kristen Brent Venable
Pages97-111
Number of pages15
DOIs
StatePublished - 2019
Event6th International Conference on Algorithmic Decision Theory, ADT 2019 - Durham, United States
Duration: Oct 25 2019Oct 27 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11834 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference6th International Conference on Algorithmic Decision Theory, ADT 2019
Country/TerritoryUnited States
CityDurham
Period10/25/1910/27/19

Bibliographical note

Funding Information:
The work of the second author was supported by the NSF grant IIS-1618783.

Funding Information:
The work of the second author was supported by the NSF grant

Publisher Copyright:
© 2019, Springer Nature Switzerland AG.

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science (all)

Fingerprint

Dive into the research topics of 'New complexity results on aggregating lexicographic preference trees using positional scoring rules'. Together they form a unique fingerprint.

Cite this