TL;DR
This paper tackles the challenge of manipulating election outcomes by presenting novel integer programming (IP) formulations for various NP-hard control problems in voting systems. By leveraging off-the-shelf IP solvers like CPLEX, the authors demonstrate that these complex control scenarios can be efficiently solved even with a large number of voters and candidates, offering a practical approach to understanding and potentially mitigating election manipulation.
What Problem Does This Paper Address?
Elections are fundamental to social choice, but they are susceptible to manipulation. One such manipulation is "control," where an external actor (the "chair") attempts to influence the election outcome by strategically altering the set of voters or candidates. While many control problems are known to be computationally hard (NP-hard), making them theoretically resistant to manipulation, this paper investigates whether these problems can be solved efficiently in practice. The authors aim to bridge the gap between theoretical hardness and practical solvability by developing integer programming models for several common voting systems and control scenarios.
Methods
The core of this paper lies in its development of integer linear programming (ILP) formulations for various control problems in voting systems. Specifically, they focus on "constructive control," where the goal is to ensure a specific candidate wins. The authors translate the decision problems for controlling elections by deleting voters or candidates into ILP models. These models are then solved using the CPLEX solver. The paper systematically presents these ILP formulations for several voting systems, including Approval Voting, Condorcet Voting, Plurality Voting, Maximin Voting, and Bucklin Voting. The ILP formulations are designed to be flexible, accommodating arbitrary numbers of candidates and voters.
Datasets
The authors utilize the PrefLib (Preference Library) dataset, a well-known repository of real-world preference data. They specifically use instances from the "Tied Order - Complete List" and "Strict Orders - Complete List" benchmark suites. These datasets are crucial for evaluating the performance of their proposed ILP models on realistic election scenarios.
Key Insights and Ideas
- Bridging Theory and Practice: The paper demonstrates that NP-hard control problems, while theoretically difficult, can be practically solvable using modern integer programming solvers. This suggests that theoretical hardness alone might not be a sufficient safeguard against manipulation.
- Unified Modeling Approach: The authors provide a systematic way to model control problems across different voting systems using a common framework (ILP), highlighting the versatility of this approach.
- Efficiency with Large Instances: The experimental results show that their ILP formulations can efficiently handle elections with a substantial number of voters and candidates, which is a significant practical achievement.
- Constructive vs. Destructive Control: The paper clearly distinguishes between constructive (making a candidate win) and destructive (preventing a candidate from winning) control, and shows how their constructive models can be adapted for destructive scenarios.
Key Results
The computational experiments reveal that the proposed ILP models, when solved using CPLEX, are highly effective.
- For Range Voting, all 331 instances from the "Tied Order - Complete List" benchmark were solved to optimality or near-optimality within a total computation time of 25 seconds.
- For Preference-based Voting (Condorcet, Plurality, Maximin, Bucklin), the models generally performed well. For instance, the Condorcet model solved 605 out of 627 instances to optimality in just 5.5 seconds.
- While most instances were solved quickly, some harder instances, particularly for Bucklin elections with candidate deletion, took significantly longer (up to 8.5 hours for a single instance), indicating that the complexity of the voting system and the control problem still matters.
- The paper also notes that for some instances, infeasibility was detected, meaning that it's impossible to achieve the desired control outcome, which aligns with theoretical predictions for certain voting systems.
Limitations and Future Work
- Focus on Specific Control Types: The paper primarily focuses on constructive control by deleting voters or candidates. While they briefly discuss adapting models for destructive control, a more in-depth exploration of various control types (e.g., bribery, partition) across more voting systems would be valuable.
- Voting System Scope: While several common voting systems are covered, there are many other voting systems (e.g., fallback voting, SP-AV) for which these ILP models could be extended.
- Computational Limits: Although the ILP approach is efficient for many cases, some instances, particularly for complex voting rules like Bucklin with candidate deletion, remain computationally challenging.
- Future Directions: The authors suggest exploring other computational methods like SAT-solving and constraint programming, as well as investigating other types of illegal influences like bribery and voter partitioning. They also propose extending the approach to other voting systems.
Summary updated