TL;DR
This paper delves into the computational complexity of election control when manipulators are present, analyzing both cooperative (chair and manipulators allied) and competitive (chair and manipulators opposing) scenarios. The authors establish general upper bounds for these problems, showing they can be quite complex, but then demonstrate that for many common election systems, the complexity drops significantly, even to polynomial time.
What Problem Does This Paper Address?
Elections are fundamental to decision-making, and with the rise of online systems, their importance is growing. However, the power of computation also brings concerns about manipulative attacks. Two primary types of attacks are "control" (an agent tries to make a specific candidate win by altering the election structure) and "manipulation" (voters change their ballots to achieve a desired outcome). This paper uniquely investigates the complexity of control attacks in the presence of manipulators. It considers two main settings:
- Cooperative Case: The "chair" orchestrating the control is allied with the manipulators.
- Competitive Case: The manipulators actively try to thwart the chair's control efforts.
The paper also examines how the order of operations (chair first vs. manipulators first) affects complexity in the competitive scenarios.
Methods
The authors define formal computational problems for these scenarios and analyze their complexity using standard tools from theoretical computer science, particularly the polynomial hierarchy. They prove upper bounds for general election systems and then demonstrate matching lower bounds (completeness results) for specific election systems, showing these bounds are tight. A key aspect is their analysis of how existing election system properties, like the Weak Axiom of Revealed Preferences (WARP), can drastically simplify control problems. For specific election systems like plurality, approval, and Condorcet, they show that the presence of manipulators doesn't significantly increase complexity, often keeping it within polynomial time.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Order Matters: In competitive scenarios, whether the chair acts before the manipulators or vice-versa significantly impacts the problem's complexity.
- Axiomatic Simplicity: Election systems satisfying certain properties (like unique-WARP) can inherently simplify control problems, reducing the combinatorial explosion of possibilities.
- Real-World Systems are Easier: While general upper bounds can be high (involving complex levels of the polynomial hierarchy), many practical election systems (plurality, approval, Condorcet) remain computationally tractable even with manipulators.
- Cooperative vs. Competitive Dynamics: The cooperative case often inherits complexity from pure control, while the competitive case introduces new challenges and sometimes flips the nature of the problem (e.g., constructive control becoming related to destructive manipulation).
Key Results
The paper establishes general upper bounds for control-plus-manipulation problems, reaching levels like NPNP and coNPNPNP in the polynomial hierarchy. Crucially, they prove that for many election systems, these high bounds are tight, meaning these complex classes are achievable. However, for important systems like plurality, approval, and Condorcet, they show that the complexity of both cooperative and competitive control-plus-manipulation falls to polynomial time, often significantly lower than the general bounds. They also analyze specific cases for veto and Borda elections, finding some instances where competitive control-plus-manipulation is surprisingly easier or harder than expected.
Limitations and Future Work
The authors acknowledge that their constructions for proving lower bounds can be artificial and that the third level of the polynomial hierarchy is complex to work with. They explicitly state that their results leave open the possibility that for particular, important real-world systems, the complexity might be much simpler than the general upper bounds suggest. They also point to several open directions, including investigating more complex election systems (like Schulze, Copeland, fallback, sincere-preference approval) and exploring how their findings apply to these systems. The paper also notes that while they handle the "chair's perspective" in competitive cases, the manipulators' perspective is implicitly covered due to the duality of constructive/destructive problems.
Summary updated