Solving hard control problems in voting systems via integer programming
From MaRDI portal
Publication:322433
DOI10.1016/J.EJOR.2015.08.052zbMATH Open1346.91075arXiv1408.5987OpenAlexW1915090682MaRDI QIDQ322433FDOQ322433
Authors: Rudolf Berghammer, F. Neumann, S. Polyakovskiy 
Publication date: 7 October 2016
Published in: European Journal of Operational Research (Search for Journal in Brave)
Abstract: Voting problems are central in the area of social choice. In this article, we investigate various voting systems and types of control of elections. We present integer linear programming (ILP) formulations for a wide range of NP-hard control problems. Our ILP formulations are flexible in the sense that they can work with an arbitrary number of candidates and voters. Using the off-the-shelf solver Cplex, we show that our approaches can manipulate elections with a large number of voters and candidates efficiently.
Full work available at URL: https://arxiv.org/abs/1408.5987
Recommendations
- Binary linear programming solutions and non-approximability for control problems in voting systems
- Parameterized computational complexity of control problems in voting systems
- How hard is it to control an election?
- Llull and Copeland Voting Computationally Resist Bribery and Constructive Control
- The computational difficulty of manipulating an election
Cites Work
- Reducibility among combinatorial problems
- A Short Introduction to Computational Social Choice
- When are elections with few candidates hard to manipulate?
- Anyone but him: the complexity of precluding an alternative
- How hard is it to control an election?
- Multimode control attacks on elections
- Cloning in elections: finding the possible winners
- Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control
- Approval voting
- Title not available (Why is that?)
- Relation algebra, RelView, and plurality voting
- Relation Algebra and RelView Applied to Approval Voting
- Is computational complexity a barrier to manipulation?
- Binary linear programming solutions and non-approximability for control problems in voting systems
Cited In (2)
Uses Software
This page was built for publication: Solving hard control problems in voting systems via integer programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q322433)
