Robustness among multiwinner voting rules

DOI10.1007/978-3-319-66700-3_7zbMATH Open1403.91129arXiv1707.01417OpenAlexW2963352083WikidataQ62039057 ScholiaQ62039057MaRDI QIDQ5894693FDOQ5894693

Authors: Robert Bredereck, Piotr Faliszewski, Andrzej Kaczmarczyk, Rolf Niedermeier, Piotr Skowron, Nimrod Talmon 

Publication date: 13 February 2018

Published in: Algorithmic Game Theory (Search for Journal in Brave)

Abstract: We investigate how robust the results of committee elections are to small changes in the input preference orders, depending on the voting rules used. We find that for typical rules the effect of making a single swap of adjacent candidates in a single preference order is either that (1) at most one committee member might be replaced, or (2) it is possible that the whole committee will be replaced. We also show that the problem of computing the smallest number of swaps that lead to changing the election outcome is typically NP-hard, but there are natural FPT algorithms. Finally, for a number of rules we assess experimentally the average number of random swaps necessary to change the election result.

Full work available at URL: https://arxiv.org/abs/1707.01417

Recommendations

• Robustness among multiwinner voting rules
• Robustness of approval-based multiwinner voting rules
• Robustness radius for Chamberlin-Courant on restricted domains
• Properties of multiwinner voting rules
• Winner determination and manipulation in minisum and minimax committee elections

zbMATH Keywords

\({\mathrm {FPT}}\) algorithms\({\mathrm {NP}}\)-hardmultiwinner voting rules

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Voting theory (91B12)

Cited In (12)

• Robustness among multiwinner voting rules
• Multiwinner analogues of the plurality rule: axiomatic and algorithmic perspectives
• Isomorphic Distances Among Elections
• Sophisticated voting rules: The case of two tournaments
• Approximation and hardness of shift-bribery
• Resolute control: forbidding candidates from winning an election is hard
• Complexity of manipulation and bribery in premise-based judgment aggregation with simple formulas
• Even more effort towards improved bounds and fixed-parameter tractability for multiwinner rules
• Utilitarian welfare and representation guarantees of approval-based multiwinner rules
• Monotonicity and robustness of majority rule
• Robustness of approval-based multiwinner voting rules
• Majority tournaments: Sincere and sophisticated voting decisions under amendment procedure

This page was built for publication: Robustness among multiwinner voting rules

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5894693)