Research map / Learning theory and algorithms / Submodular and game algorithms
Spatial Voting with Incomplete Voter Information
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Studies possible and necessary winner complexity in spatial voting where voters' ideal points are known only as intervals per dimension, for positional scoring rules and approval voting.
Problem
Computing possible and necessary winners when voters' Euclidean ideal points are only known to lie in axis-aligned intervals (partial spatial profiles), for positional scoring rules and approval voting in d dimensions.
Approach
Models voter uncertainty as per-dimension intervals for ideal points rather than partial orders; enumerates ranking completions via hyperplane arrangements (polynomial for fixed d), reduces plurality/veto cases to partial-order results, and reduces two-valued rule possible-winner to multi-machine scheduling with arrival times and deadlines.
Key results
- Necessary winners under positional scoring rules in partial spatial voting are polynomial-time for every fixed d.
- Possible winners for plurality and veto are polynomial for every fixed d; possible winners for two-valued rules in d=1 (e.g., k-approval) are polynomial via reduction to scheduling.
- Possible-winner problem for k-approval is NP-complete for d>=2 and k>=3; for approval voting, possible-winner is NP-complete for any d>=1 while necessary-winner is polynomial for d<=2.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use interval uncertainty over voter locations in fixed-dimensional spatial voting | Necessary-winner problem for positional scoring rules · Partial spatial voting, fixed d | computational complexity | Helped |
| Allow dimension d to be part of the input | Necessary winners under plurality and veto · Partial spatial voting | computational complexity | Helped |
| Use one-dimensional spatial voter uncertainty | Possible winners under any two-valued positional scoring rule · Partial spatial voting, d=1 | computational complexity | Helped |
| Use one-dimensional spatial voter uncertainty with a weighted veto rule | Possible-winner problem · Partial spatial voting, d=1 | computational complexity | Helped |
| Use F(k,t) with k > t in one-dimensional spatial voting | Possible-winner problem · Partial spatial voting, d=1 | computational complexity | Helped |
| Allow dimension d to be part of the input | Possible winners under plurality and veto · Partial spatial voting | computational complexity | Helped |
| Increase spatial dimension to d ≥ 2 and use k-approval with k ≥ 3 | Possible-winner problem · Partial spatial voting | computational complexity | Hurt |
| Use spatial approval voting with d ≤ 2 | Necessary-winner problem · Partial spatial approval voting | computational complexity | Helped |
| Use approval voting with incomplete spatial voter locations | Possible-winner problem · Partial spatial approval voting, d ≥ 1 | computational complexity | Hurt |
| Replace partial-order uncertainty with one-dimensional partial spatial uncertainty | Possible winners under two-valued rules other than plurality and veto · Partial spatial voting, d=1 | computational complexity | Helped |
Surprising findings
- Possible-winner problem for some positional scoring rules is intractable for partial orders but tractable in one-dimensional partial spatial voting.
- Possible-winner under approval voting is NP-complete even in one dimension.
Limitations
- Running time of necessary-winner algorithm is exponential in d.
- Possible-winner for k-approval with d>=2 is NP-complete, and Borda in one dimension is left open.
Experimental setup
Builds on: partial-order possible/necessary winner framework spatial voting model non-preemptive multi-machine scheduling with arrival times and deadlines
Closest papers by meaning
- An Analysis of Approval-Based Committee Rules for 2D-Euclidean Elections (AAAI 2021 · similarity 0.88)
- Optimizing Multiple Simultaneous Objectives for Voting and Facility Location (AAAI 2023 · similarity 0.87)
- On the Distortion of Voting With Multiple Representative Candidates (AAAI 2018 · similarity 0.87)
- On the Distortion of Committee Election with 1-Euclidean Preferences and Few Distance Queries (AAAI 2025 · similarity 0.86)
- Nearly Tight Bounds on Approximate Equilibria in Spatial Competition on the Line (AAAI 2025 · similarity 0.86)
- Proportional Aggregation of Preferences for Sequential Decision Making (AAAI 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.