Finding Possible Winners in Spatial Voting with Incomplete Information
Hadas Shachnai, Rotem Shavitt, Andreas Wiese · 2025
Read Finding Possible Winners in Spatial Voting with Incomplete Information by Hadas Shachnai, Rotem Shavitt, Andreas Wiese (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-12451.txt.
Introduction
Hadas Shachnai, Rotem Shavitt, and Andreas Wiese studied a voting puzzle in a 2025 study: who could win an election when voter views are known only in part. In their model, voters and candidates sit as points in space, and voters favor the candidate nearest to them. For each voter, only a range of spots is known, not the exact point.
The team asked how hard it is to compute the set of possible winners under scoring rules. In one dimension, the problem can be solved fast for a broad family of rules. For harder rules, such as approval voting, they give a method that works well when the number of candidates is small. They also sort out which weighted versions stay easy and which turn hard.
Catalog record
| CREATOR | Hadas Shachnai, Rotem Shavitt, Andreas Wiese |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 93 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-12451
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Finding Possible Winners in Spatial Voting with Incomplete Information Hadas Shachnai, Rotem Shavitt, Andreas Wiese Abstract We consider a spatial voting model where both candidates and voters are positioned in the d d -dimensional Euclidean space, and each voter ranks candidates based on their proximity to the voter’s ideal point. We focus on the scenario where the given information about the locations of the voters’ ideal points is incomplete; for each dimension, only an interval of possible values is known. In this context, we investigate the computational complexity of determining the possible winners under positional scoring rules. Our results show that the possible winner problem in one dimension is solvable in polynomial time for all k k -truncated voting rules with constant k k . Moreover, for some scoring rules for which the possible winner problem is NP-complete, such as approval voting for any dimension or k k -approval for d ≥ 2 d\geq 2 dimensions, we give an FPT algorithm parameterized by the number of candidates. Finally, we classify tractable and intractable settings of the weighted possible winner problem in one dimension, and resolve the computational complexity of the weighted case for all two-valued positional scoring rules when d = 1 d=1 . 1 Introduction The spatial model of voting associates voters and candidates with points in the d -dimensional Euclidean space, i.e., in \mathbb{R}^{d} . Each dimension corresponds to an issue on which the voters and the candidates have an opinion; this opinion is defined by the coordinate of the voter or candidate in this dimension. Voters prefer candidates closer to their respective point (measured as the Euclidean distance in \mathbb{R}^{d} ) over those who are further away. Hence, for each voter this induces an order of the candidates. In the social choice literature, preferences with this structure are often referred to as ( d -)Euclidean preferences [ 10 , 19 ] . The most common example of a spatial model is a political spectrum, such as the traditional left-right axis where d=1 , but issue spaces can be of higher dimension (see, e.g., [ 1 ] ). We consider a common scenario where the point in \mathbb{R}^{d} of each candidate is known precisely, e.g., from the election campaign, but for the voters’ preferences only partial information is available. For each voter and each of the d dimensions, we assume that we are given an interval which contains the opinion of the voter corresponding to this dimension. This model captures real-world uncertainty in political elections, where it is often difficult to determine exactly which party a voter supports. However, we can typically estimate a range for their views—for instance, whether they tend to lean left, right, or center. From this partial information we can identify a set of possible preference orders for the voter. We study voting systems in which there is a global scoring vector \vec{s}_{m}=(s_{m}(1),s_{m}(2),...,s_{m}(m)) , depending on the number of candidates, with s_{m}(1)\geq s_{m}(2)\geq...\geq s_{m}(m) such that each voter gives s_{m}(1) votes to her favorite candidate, s_{m}(2) votes to her second favorite candidate, and so on. Also, we study approval voting where each voter v_{j} gives one vote to each candidate whose opinion is within a given approval radius \rho_{j} of the point in \mathbb{R}^{d} corresponding to v_{j} . In both settings, we say that a candidate can win the election if no other candidate receives a higher total score. Since the precise opinion of each voter is not known, it is unclear which candidate will win the election. Two key questions arising in this setting are whether a specific candidate can be a possible winner (who wins in at least one scenario by the opinions of the voters) or a necessary winner (one who wins in every possible scenario). These questions, introduced in the seminal work of [ 25 ] , have garnered significant attention in various settings involving incomplete information about voters’ preferences (see Section 1.1 ). Problem k -approval Multi-valued positional scoring rules Approval voting \mathsf{PW}\mathord{\langle{1\rangle}} in P [ 22 ] in P for any k -truncated scoring rule for a constant k [Theorem 1 ] NP-c [ 22 ] FPT in m [Theorem 5 ] \mathsf{PW}\mathord{\langle{d\rangle}} NP-c for k\geq 3 , d\geq 2 [ 22 ] , FPT in m [Theorem 4 ] FPT in m [Theorem 4 ] NP-c [ 22 ] FPT in m [Theorem 5 ] \mathsf{WPW}\mathord{\langle{1\rangle}} in P if k(m)\geq\frac{m}{2} \forall m\in\mathbb{N} , otherwise NP-c [Theorem 6 ] NP-c for Borda with m\geq 4 [Theorem 7 ] NP-c [ 22 ] Table 1 : Our results for \mathsf{PW}\mathord{\langle{1\rangle}} , \mathsf{PW}\mathord{\langle{d\rangle}} for d\geq 2 , and \mathsf{WPW}\mathord{\langle{1\rangle}} and corresponding previous results for these problems. The necessary winner problem ( \mathsf{NW} ) is well understood in this model, thanks to a thorough study in Imber et al. [ 22 ] . However, the complexity of \mathsf{PW}\mathord{\langle{d\rangle}} , i.e., the possible winner problem with incomplete voters’ information in d dimensions, is known only for certain classes of scoring rules (defined via certain classes of vectors \mathbf{s} ). Specifically, as shown in [ 22 ] , \mathsf{PW}\mathord{\langle{1\rangle}} is solvable in polynomial time for all two-valued rules, i.e., rules in which the vector \vec{s} contains only two different values, and for two specific families of rules with more than two values: (i) The three-valued rule F(k,t) , in which the scoring vector is s=(2,\ldots,2,1,\ldots,1,0,\ldots,0) , starting with k occurrences of two and ending with t zeroes; \mathsf{PW}\mathord{\langle{1\rangle}} is tractable for F(k,t) whenever k>t . (ii) Weighted veto rules, which are of the form s=(\alpha,\ldots,\ldots,\beta_{1},\ldots,\beta_{k}) for \alpha>\beta_{1}\geq\cdot\cdot\cdot\geq\beta_{k} with k<m/2 . On the other hand, \mathsf{PW}\mathord{\langle{d\rangle}} is NP-complete for any number of dimensions d\geq 2 , already for the (relatively simple) scoring vector \mathbf{s}=(1,1,1,0,...,0) [ 22 ] . These previous results leave several intriguing questions open: (1) Is \mathsf{PW}\mathord{\langle{1\rangle}} still tractable for other positional scoring rules with more than two values, e.g., for \vec{s}=(2,1,0,...,0) ? (2) For voting rules under which \mathsf{PW}\mathord{\langle{d\rangle}} is NP-complete, can we devise parameterized algorithms? (3) What happens if each voter is associated with a weight, e.g., representing a group of voters sharing the same (unknown) common opinion, or members with varying levels of influence in a board of directors? Is the weighted possible winner problem \mathsf{WPW}\mathord{\langle{d\rangle}} harder than \mathsf{PW}\mathord{\langle{d\rangle}} ? We answer all three questions positively, see Table 1 for an overview. First, we present a polynomial-time algorithm for \mathsf{PW}\mathord{\langle{1\rangle}} for any scoring vector \vec{s} with a constant number of non-zero entries. Such scoring vectors are very common in real-life voting systems: the Eurovision Song Contest [ 31 ] ) uses the scoring vector \vec{s}=(12,10,8,7,6,5,4,3,2,1,0...,0) and the NBA MVP contest uses \vec{s}=(10,7,5,3,1,0,\dots,0) . Also, this class contains the k -truncated Borda rule (k,k-1,...,1,0,\ldots,0) which is used in the NCAA Football Division 1A Coaches’ poll for k=25 . Such scoring rules are popular because ranking all candidates becomes impractical when there are many candidates. Moreover, voters often lack strong preferences beyond their top choices, making the order among lower-ranked candidates irrelevant. Also, keeping the number of positive entries fixed ensures stability in the voting system in repeated contests as described above, where the number of candidates may vary, and a voting rule that depends on this number complicates the process