Unweighted coalitional manipulation under the Borda rule is NP-hard

N. Betzler; R. Niedermeier; G.J. Woeginger

doi:10.5591/978-1-57735-516-8/IJCAI11-021

Unweighted coalitional manipulation under the Borda rule is NP-hard

N. Betzler, R. Niedermeier, G.J. Woeginger

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

71 Citaten (Scopus)

2 Downloads (Pure)

Samenvatting

The Borda voting rule is a positional scoring rule where, for m candidates, for every vote the first candidate receives m-1 points, the second m-2 points and so on. A Borda winner is a candidate with highest total score. It has been a prominent open problem to determine the computational complexity of UNWEIGHTED COALITIONAL MANIPULATION UNDER BORDA: Can one add a certain number of additional votes (called manipulators) to an election such that a distinguished candidate becomes a winner? We settle this open problem by showing NP-hardness even for two manipulators and three input votes. Moreover, we discuss extensions and limitations of this hardness result.

Originele taal-2	Engels
Titel	Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011, Barcelona, Catalonia, Spain, July 16-22, 2011)
Redacteuren	T. Walsh
Plaats van productie	Menlo Park CA
Uitgeverij	AAI Press
Pagina's	55-60
ISBN van geprinte versie	978-1-57735-516-8
DOI's	https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-021
Status	Gepubliceerd - 2011

Toegang tot document

10.5591/978-1-57735-516-8/IJCAI11-021

Citeer dit

@inproceedings{d8b3877ca786403a96130904d95888c6,

title = "Unweighted coalitional manipulation under the Borda rule is NP-hard",

abstract = "The Borda voting rule is a positional scoring rule where, for m candidates, for every vote the first candidate receives m-1 points, the second m-2 points and so on. A Borda winner is a candidate with highest total score. It has been a prominent open problem to determine the computational complexity of UNWEIGHTED COALITIONAL MANIPULATION UNDER BORDA: Can one add a certain number of additional votes (called manipulators) to an election such that a distinguished candidate becomes a winner? We settle this open problem by showing NP-hardness even for two manipulators and three input votes. Moreover, we discuss extensions and limitations of this hardness result.",

author = "N. Betzler and R. Niedermeier and G.J. Woeginger",

year = "2011",

doi = "10.5591/978-1-57735-516-8/IJCAI11-021",

language = "English",

isbn = "978-1-57735-516-8",

pages = "55--60",

editor = "T. Walsh",

booktitle = "Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011, Barcelona, Catalonia, Spain, July 16-22, 2011)",

publisher = "AAI Press",

}

Betzler, N, Niedermeier, R & Woeginger, GJ 2011, Unweighted coalitional manipulation under the Borda rule is NP-hard. in T Walsh (uitgave), Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011, Barcelona, Catalonia, Spain, July 16-22, 2011). AAI Press, Menlo Park CA, blz. 55-60. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-021

Unweighted coalitional manipulation under the Borda rule is NP-hard. / Betzler, N.; Niedermeier, R.; Woeginger, G.J.
Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011, Barcelona, Catalonia, Spain, July 16-22, 2011). uitgave / T. Walsh. Menlo Park CA: AAI Press, 2011. blz. 55-60.

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

TY - GEN

T1 - Unweighted coalitional manipulation under the Borda rule is NP-hard

AU - Betzler, N.

AU - Niedermeier, R.

AU - Woeginger, G.J.

PY - 2011

Y1 - 2011

N2 - The Borda voting rule is a positional scoring rule where, for m candidates, for every vote the first candidate receives m-1 points, the second m-2 points and so on. A Borda winner is a candidate with highest total score. It has been a prominent open problem to determine the computational complexity of UNWEIGHTED COALITIONAL MANIPULATION UNDER BORDA: Can one add a certain number of additional votes (called manipulators) to an election such that a distinguished candidate becomes a winner? We settle this open problem by showing NP-hardness even for two manipulators and three input votes. Moreover, we discuss extensions and limitations of this hardness result.

AB - The Borda voting rule is a positional scoring rule where, for m candidates, for every vote the first candidate receives m-1 points, the second m-2 points and so on. A Borda winner is a candidate with highest total score. It has been a prominent open problem to determine the computational complexity of UNWEIGHTED COALITIONAL MANIPULATION UNDER BORDA: Can one add a certain number of additional votes (called manipulators) to an election such that a distinguished candidate becomes a winner? We settle this open problem by showing NP-hardness even for two manipulators and three input votes. Moreover, we discuss extensions and limitations of this hardness result.

U2 - 10.5591/978-1-57735-516-8/IJCAI11-021

DO - 10.5591/978-1-57735-516-8/IJCAI11-021

M3 - Conference contribution

SN - 978-1-57735-516-8

SP - 55

EP - 60

BT - Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI 2011, Barcelona, Catalonia, Spain, July 16-22, 2011)

A2 - Walsh, T.

PB - AAI Press

CY - Menlo Park CA

ER -

Unweighted coalitional manipulation under the Borda rule is NP-hard

Samenvatting

Toegang tot document

Vingerafdruk

Citeer dit