TL;DR
This paper tackles the "possible winner" problem in spatial voting models where voter preferences are not fully known, only intervals of possible opinions. The authors develop polynomial-time algorithms for certain scoring rules in one dimension and fixed-parameter tractable algorithms for higher dimensions, significantly advancing our understanding of computational social choice under uncertainty.
What Problem Does This Paper Address?
In political science and economics, spatial voting models are used to represent elections where voters and candidates have "ideal points" in a multi-dimensional space (e.g., representing stances on various issues). Voters prefer candidates closer to their ideal point. However, in real-world scenarios, a voter's exact ideal point is often unknown; we might only know it falls within a certain range or interval for each issue. This uncertainty makes it challenging to determine which candidate could win an election.
The paper focuses on the "possible winner" (PW) problem: can a specific candidate win the election under at least one possible completion of the voters' preferences, given the known intervals? This is a crucial question for understanding election outcomes when information is incomplete. While the "necessary winner" problem (a candidate who wins in every possible scenario) is relatively well-understood, the PW problem remains computationally challenging, especially in higher dimensions and for various voting rules. The paper aims to provide a more complete picture of the computational complexity of PW for different voting rules and dimensions, and also considers the impact of voter weights.
Methods
The paper introduces several novel algorithmic approaches:
- Polynomial-time algorithm for 1D k-truncated scoring rules: The authors reduce the PW problem in one dimension with k-truncated scoring rules to a new problem called "shapes scheduling." This scheduling problem involves assigning jobs (voters) to machines (scores) over time, with each job having specific resource requirements that change. They then devise a dynamic programming algorithm to solve this shapes scheduling problem efficiently.
- Fixed-parameter tractable (FPT) algorithm for d-dimensional PW: For any positional scoring rule and approval voting, the authors present an algorithm whose runtime is exponential only in the number of candidates ($m$), not the number of voters ($n$) or dimensions ($d$). This is achieved by formulating the problem as an integer linear program, where variables represent the number of voters of each "type" (defined by their possible voting vectors).
- Complexity analysis for weighted voting: The paper also investigates the weighted possible winner problem (WPW), where voters have associated weights. They establish NP-completeness for WPW(1) under the Borda scoring rule and identify conditions under which WPW(1) for two-valued positional scoring rules is tractable or NP-complete.
Datasets
Not discussed in the paper. The paper focuses on theoretical complexity analysis and algorithmic development rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Shapes Scheduling as a Novel Abstraction: The reduction of the PW problem to "shapes scheduling" is a key methodological contribution. This new problem formulation might have broader applications in other scheduling or resource allocation contexts.
- FPT for High-Dimensional Spatial Voting: The development of an FPT algorithm for PW in $d$-dimensional space parameterized by the number of candidates is a significant theoretical result. It shows that even with high dimensionality, the problem becomes manageable if the number of candidates is small.
- Impact of Voter Weights: The paper highlights that introducing voter weights can significantly increase the computational hardness of the possible winner problem, even in the simple one-dimensional case. This underscores the importance of considering influence when analyzing election outcomes.
- Dichotomy for 1D Weighted Voting: The paper provides a clear classification for the complexity of weighted possible winner problems in one dimension for two-valued scoring rules, distinguishing between tractable and NP-complete cases based on the scoring rule's structure.
Key Results
- PW(1) with k-truncated scoring rules: Solvable in polynomial time for constant $k$.
- PW(d) for positional scoring rules and approval voting: Fixed-parameter tractable (FPT) with respect to the number of candidates ($m$).
- WPW(1) with Borda scoring: NP-complete for $m=4$.
- WPW(1) with two-valued positional scoring rules: Classified as either in P or NP-complete based on the scoring rule's parameters.
Limitations and Future Work
- Open Problems for 1D PW: The paper notes that the complexity of PW(1) for certain natural scoring rules (like Borda) remains open, even for the unweighted case.
- Complexity of WPW(d): The complexity of the weighted possible winner problem in $d \ge 2$ dimensions is still largely open, even for simple scoring rules.
- Parameterization for WPW(1): Identifying a natural parameter for which WPW(1) is FPT is suggested as future work.
- Generalization of Shapes Scheduling: While the paper shows shapes scheduling is NP-hard without certain constraints, exploring its complexity under relaxed conditions could be fruitful.
Summary updated