Parliamentary Voting Procedures: Agenda Control, Manipulation, and Uncertainty

Robert Bredereck, Jiehua Chen, Rolf Niedermeier, Toby Walsh

JAIR 2017 pp. 133-173

doi:10.1613/JAIR.5407 /jair/2017/bredereck2017jair-parliamentary/

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 possible winners is NP-hard for both procedures. Whereas finding necessary winners is coNP-hard for the amendment procedure, it is polynomial-time solvable for the successive one.

PDF JAIR Semantic Scholar

Cite

Text

Bredereck et al. "Parliamentary Voting Procedures: Agenda Control, Manipulation, and Uncertainty." Journal of Artificial Intelligence Research, 2017. doi:10.1613/JAIR.5407

Markdown

[Bredereck et al. "Parliamentary Voting Procedures: Agenda Control, Manipulation, and Uncertainty." Journal of Artificial Intelligence Research, 2017.](https://mlanthology.org/jair/2017/bredereck2017jair-parliamentary/) doi:10.1613/JAIR.5407

BibTeX

@article{bredereck2017jair-parliamentary,
  title     = {{Parliamentary Voting Procedures: Agenda Control, Manipulation, and Uncertainty}},
  author    = {Bredereck, Robert and Chen, Jiehua and Niedermeier, Rolf and Walsh, Toby},
  journal   = {Journal of Artificial Intelligence Research},
  year      = {2017},
  pages     = {133-173},
  doi       = {10.1613/JAIR.5407},
  volume    = {59},
  url       = {https://mlanthology.org/jair/2017/bredereck2017jair-parliamentary/}
}