Abstract
This paper investigates "partial spatial voting," a model where candidates and voters are points in $d$-dimensional space, but voter locations are known only as hyper-rectangles. We analyze the computational complexity of identifying "necessary" and "possible" winners under various voting rules. Our results show that geometric constraints often make these problems more tractable than in traditional preference models, particularly for positional scoring rules in fixed dimensions.
Introduction
In computational social choice, incomplete information is typically modeled using partial orders. However, many real-world scenarios, such as political elections, are better described by the spatial model. Here, voters and candidates are points in a multi-dimensional space, and voters prefer candidates closer to their "ideal point." This research addresses the gap where a voter's ideal point is an interval (hyper-rectangle) rather than a single coordinate, creating a set of possible rankings. We focus on two primary problems:
- Necessary Winners (NW): Candidates who win regardless of where voters are placed within their allowed intervals.
- Possible Winners (PW): Candidates who win in at least one valid placement of voters.
Methodology
The study employs geometric complexity analysis and reductions to classical computer science problems. As a theoretical work, no empirical datasets were used; results are proven for worst-case scenarios across all valid inputs.
- Hyperplane Arrangements: To solve the NW problem, the authors utilize the fact that $m$ candidates in $d$ dimensions define hyperplanes that partition the space into regions of constant rankings. This allows for checking a polynomial number of distinct rankings ($O(m^{2d})$) instead of an infinite set of points. Hyperplane arrangements partitioning the space into regions of constant candidate rankings. Source, p. 4
- Scheduling Reductions: The PW problem in one dimension is linked to multi-machine scheduling, treating candidates as time slots and voters as jobs with specific arrival and deadline constraints.
- Sweep-line Algorithms: For spatial approval voting in 2D, a geometric sweep-line approach efficiently enumerates possible sets of approved candidates.
Results Summary
The core findings highlight that spatial constraints often act as a "filter," making some hard problems tractable. For instance, the NW problem is solvable in polynomial time for all positional scoring rules in any fixed dimension. However, Approval Voting remains more difficult, with the PW problem being NP-complete even in a single dimension.
Conclusion and Future Work
While fixed-dimensional algorithms are polynomial, they face the "curse of dimensionality" as the number of issues (dimensions) grows. Future work includes investigating the Borda count complexity in 1D, strategic candidate positioning under voter uncertainty, and the application of these frameworks to Condorcet-consistent rules.
Summary updated