Solving hard control problems in voting systems via integer programming

DOI10.1016/J.EJOR.2015.08.052MaRDI QIDQ322433zbMATH OpenOpenAlexFDO

Authors Rudolf Berghammer, F. Neumann, S. Polyakovskiy

Publication date 7 October 2016

Published in European Journal of Operational Research (Search for Journal in Brave)

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

zbMATH Keywords

integer programmingcontrol problemelection modelvoting system

Mathematics Subject Classification ID

Social choice (91B14) Integer programming (90C10) Voting theory (91B12)

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.

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

• scientific article; zbMATH DE number 3497901 (Why is no real title available?)
• A Short Introduction to Computational Social Choice
• Anyone but him: the complexity of precluding an alternative
• Approval voting
• Binary linear programming solutions and non-approximability for control problems in voting systems
• Cloning in elections: finding the possible winners
• How hard is it to control an election?
• Is computational complexity a barrier to manipulation?
• Multimode control attacks on elections
• Reducibility among combinatorial problems
• Relation Algebra and RelView Applied to Approval Voting
• Relation algebra, RelView, and plurality voting
• Schulze and ranked-pairs voting are fixed-parameter tractable to bribe, manipulate, and control
• When are elections with few candidates hard to manipulate?

Cited in

(2)

• Supermajority politics: equilibrium range, policy diversity, utilitarian welfare, and political compromise
• Binary linear programming solutions and non-approximability for control problems in voting systems

Describes a project that uses

Uses Software

• PrefLib
• CPLEX
• RelView

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)