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

Xudong Liu; Miroslaw Truszczynski

doi:10.1007/978-3-030-31489-7_7

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

Xudong Liu, Miroslaw Truszczynski

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-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 language	English
Title of host publication	Algorithmic Decision Theory - 6th International Conference, ADT 2019, Proceedings
Editors	Saša Pekec, Kristen Brent Venable
Pages	97-111
Number of pages	15
DOIs	https://doi.org/10.1007/978-3-030-31489-7_7
State	Published - 2019
Event	6th International Conference on Algorithmic Decision Theory, ADT 2019 - Durham, United States Duration: Oct 25 2019 → Oct 27 2019

Publication series

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

Conference

Conference	6th International Conference on Algorithmic Decision Theory, ADT 2019
Country/Territory	United States
City	Durham
Period	10/25/19 → 10/27/19

Bibliographical note

Publisher Copyright:
© 2019, Springer Nature Switzerland AG.

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-31489-7_7

Cite this

Liu, X., & Truszczynski, M. (2019). New complexity results on aggregating lexicographic preference trees using positional scoring rules. In S. Pekec, & K. B. Venable (Eds.), Algorithmic Decision Theory - 6th International Conference, ADT 2019, Proceedings (pp. 97-111). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11834 LNAI). https://doi.org/10.1007/978-3-030-31489-7_7

Liu, Xudong ; Truszczynski, Miroslaw. / New complexity results on aggregating lexicographic preference trees using positional scoring rules. Algorithmic Decision Theory - 6th International Conference, ADT 2019, Proceedings. editor / Saša Pekec ; Kristen Brent Venable. 2019. pp. 97-111 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{669d56ae60b94b31af58617e66a8bd77,

title = "New complexity results on aggregating lexicographic preference trees using positional scoring rules",

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.",

author = "Xudong Liu and Miroslaw Truszczynski",

note = "Publisher Copyright: {\textcopyright} 2019, Springer Nature Switzerland AG.; 6th International Conference on Algorithmic Decision Theory, ADT 2019 ; Conference date: 25-10-2019 Through 27-10-2019",

year = "2019",

doi = "10.1007/978-3-030-31489-7_7",

language = "English",

isbn = "9783030314880",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "97--111",

editor = "Sa{\v s}a Pekec and Venable, {Kristen Brent}",

booktitle = "Algorithmic Decision Theory - 6th International Conference, ADT 2019, Proceedings",

}

Liu, X & Truszczynski, M 2019, New complexity results on aggregating lexicographic preference trees using positional scoring rules. in S Pekec & KB Venable (eds), Algorithmic Decision Theory - 6th International Conference, ADT 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11834 LNAI, pp. 97-111, 6th International Conference on Algorithmic Decision Theory, ADT 2019, Durham, United States, 10/25/19. https://doi.org/10.1007/978-3-030-31489-7_7

New complexity results on aggregating lexicographic preference trees using positional scoring rules. / Liu, Xudong; Truszczynski, Miroslaw.
Algorithmic Decision Theory - 6th International Conference, ADT 2019, Proceedings. ed. / Saša Pekec; Kristen Brent Venable. 2019. p. 97-111 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11834 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

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

AU - Liu, Xudong

AU - Truszczynski, Miroslaw

PY - 2019

Y1 - 2019

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85075640563&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85075640563&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-31489-7_7

DO - 10.1007/978-3-030-31489-7_7

M3 - Conference contribution

AN - SCOPUS:85075640563

SN - 9783030314880

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 97

EP - 111

BT - Algorithmic Decision Theory - 6th International Conference, ADT 2019, Proceedings

A2 - Pekec, Saša

A2 - Venable, Kristen Brent

T2 - 6th International Conference on Algorithmic Decision Theory, ADT 2019

Y2 - 25 October 2019 through 27 October 2019

ER -

Liu X, Truszczynski M. New complexity results on aggregating lexicographic preference trees using positional scoring rules. In Pekec S, Venable KB, editors, Algorithmic Decision Theory - 6th International Conference, ADT 2019, Proceedings. 2019. p. 97-111. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-31489-7_7

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

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this