Spatial Voting with Incomplete Voter Information

Aviram Imber, Jonas Israel, Markus Brill, Hadas Shachnai, Benny KimelfeldAAAI 2024 · DOI

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:

  1. Necessary Winners (NW): Candidates who win regardless of where voters are placed within their allowed intervals.
  2. 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
Hyperplane arrangements partitioning the space into regions of constant candidate rankings.
  • 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.

Complexity results for Necessary Winner (NW) and Possible Winner (PW) problems.

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

BibTeX
@inproceedings{imber2024spatial,
  author = {Aviram Imber and Jonas Israel and Markus Brill and Hadas Shachnai and Benny Kimelfeld},
  title = {{Spatial Voting with Incomplete Voter Information}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i9.28838},
}
Figure