A note on the complexity of manipulating weighted Schulze voting

DOI10.1016/J.IPL.2020.105989MaRDI QIDQ2203580zbMATH OpenOpenAlexFDO

Authors Julian-Steffen Müller, Sven Kosub

Publication date 7 October 2020

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

computational complexitycomputational social choiceSchulze voting

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Social choice (91B14) Mathematical economics and fuzziness (91B86)

Abstract: We prove that the constructive weighted coalitional manipulation problem for the Schulze voting rule can be solved in polynomial time for an unbounded number of candidates and an unbounded number of manipulators.

Recommendations

• Weighted electoral control
• Weighted manipulation for four-candidate Llull is easy
• Where are the hard manipulation problems?
• The computational difficulty of manipulating an election
• When are elections with few candidates hard to manipulate?

Cites work

• A new monotonic, clone-independent, reversal symmetric, and condorcet-consistent single-winner election method
• Barriers to manipulation in voting
• scientific article; zbMATH DE number 6928629 (Why is no real title available?)
• Manipulation of Voting Schemes: A General Result
• Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control
• Strategic manipulability without resoluteness or shared beliefs: Gibbard-Satterthwaite generalized
• Strategy-proofness and Arrow's conditions: existence and correspondence theorems for voting procedures and social welfare functions
• The computational difficulty of manipulating an election
• When are elections with few candidates hard to manipulate?

Cited in

(7)

• On the existence of a minimum integer representation for weighted voting systems
• scientific article; zbMATH DE number 6389705 (Why is no real title available?)
• Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control
• Weighted manipulation for four-candidate Llull is easy
• scientific article; zbMATH DE number 6928629 (Why is no real title available?)
• Weighted electoral control
• Exact algorithms for weighted and unweighted Borda manipulation problems

This page was built for publication: A note on the complexity of manipulating weighted Schulze voting

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