Parliamentary voting procedures: agenda control, manipulation, and uncertainty

DOI10.1613/JAIR.5407MaRDI QIDQ5278045zbMATH OpenOpenAlexWikidataFDO

Authors Robert Bredereck, Jiehua Chen, Rolf Niedermeier, Toby Walsh

Publication date 13 July 2017

Published in Journal of Artificial Intelligence Research (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Voting theory (91B12) History, political science (91F10)

Abstract: We study computational problems for two popular parliamentary voting procedures: the amendment procedure and the successive procedure. While finding successful manipulations or agenda controls is tractable for both procedures, our real-world experimental results indicate that most elections cannot be manipulated by a few voters and agenda control is typically impossible. If the voter preferences are incomplete, then finding which alternatives can possibly win is NP-hard for both procedures. Whilst deciding if an alternative necessarily wins is coNP-hard for the amendment procedure, it is polynomial-time solvable for the successive one.

Recommendations

• Sequential voting and agenda manipulation
• Voting procedures, complexity of
• Majority tournaments: Sincere and sophisticated voting decisions under amendment procedure
• Complexity of manipulation with partial information in voting
• Sophisticated voting outcomes and agenda control

Cited in

(8)

• Manipulative agendas in four-candidate elections
• Controlling the order of moves in voting by veto. II. Algorithms for constructing an optimal order of moves
• Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers
• Black and Farquharson on order-of-voting effects: An extension
• Sequential voting and agenda manipulation
• Agenda-Manipulation in Ranking
• On the parameterized complexity of controlling amendment and successive winners
• The relationship between two algorithms for decisions via sophisticated majority voting with an agenda

This page was built for publication: Parliamentary voting procedures: agenda control, manipulation, and uncertainty

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