Robustness among multiwinner voting rules

DOI10.1007/978-3-319-66700-3_7MaRDI QIDQ5894693zbMATH OpenOpenAlexWikidataFDO

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)

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

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)

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.

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

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)