| paper | Finding Possible Winners in Spatial Voting with Incomplete Information |
| authors | Hadas Shachnai, Rotem Shavitt, Andreas Wiese |
| venue | IJCAI 2025 |
| filed under | voting · incomplete-info |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c2r1) |
| judge confidence | high |
| authors would recognise it | yes |
Theorem 2
statement extracted from the paper’s text layer
Given rational candidate positions \(p_1,\ldots,p_m\in\mathbb{Q}^d\), a positional scoring vector, target \(c^\star\), and finitely many types \(t\) with rational boxes \(B_t\subseteq\mathbb{Q}^d\) and masses \(\mu_t\) summing to \(1\), let \(A_t\) be the score vectors realizable by points in \(B_t\) under nearest-candidate ranking and fixed tie-breaking. Decide whether there are variables \(x_{t,z}\ge0\) such that \(\sum_{z\in A_t}x_{t,z}=\mu_t\) for every \(t\), and \(\sum_t\sum_{z\in A_t}x_{t,z}(z(c^\star)-z(c))\ge0\) for every \(c\ne c^\star\).
An atomless electorate partitioned into finitely many indistinguishable uncertainty cohorts \(t\), each with mass \(\mu_t\) and spatial box \(B_t\). Variables \(x_{t,z}\) allocate cohort mass to feasible score vectors \(z\in A_t\), and the objective is to make the target’s aggregate score margin against every other candidate nonnegative.
Theorem 2 is the primary coverage, with Theorem 1 providing a simpler one-dimensional special mirror; Theorem 3 has an analogous approval-voting version. The weighted results in Theorems 4 and 5, necessary-winner results, and auxiliary shapes-scheduling hardness are not covered.
The strongest positive case is built from the paper’s own Theorem 2. It is proved in this paper, not cited: “For every positional scoring rule and any \(d\ge1\), \(PW\langle d\rangle\) can be solved in time \((n\log(s_m(1)))^{O(1)}f(m)\),” hence is FPT in the number of candidates.
I would mirror it with the following problem, which I would call Continuous Spatial Possible Winner, \(CSPW_\infty\).
An instance has rational candidate positions \(p_1,\ldots,p_m\in\mathbb Q^d\), a positional scoring vector \(\vec s_m\), a target \(c^\star\), and finitely many voter types \(t\in T\). Type \(t\) consists of a rational box \(B_t\subseteq\mathbb Q^d\) describing the type’s possible ideal points and a rational mass \(\mu_t\ge0\), with \(\sum_t\mu_t=1\). The mass \(\mu_t\) is the fraction of the electorate belonging to that uncertainty type.
Let \(Z\) be the set of all score vectors obtainable from permutations of the candidates. For each type \(t\), let \(A_t\subseteq Z\) be the score vectors realizable by some ideal point in \(B_t\). This is exactly the behavioral quotient used in Section 4 of the paper: two voters belong to the same type whenever they can realize precisely the same subsets of \(Z\). The geometry is retained because \(A_t\) is generated by the original spatial boxes.
The decision variable is \(x_{t,z}\ge0\), the amount of type-\(t\) mass assigned to score vector \(z\in A_t\). It must satisfy \(\sum_{z\in A_t}x_{t,z}=\mu_t\) for every type. Thus a type may split its mass among several feasible spatial completions, which is exactly what an atomless population permits. The objective is to maximize the target’s worst score margin, namely \(\max_x\min_{c\ne c^\star}\sum_{t}\sum_{z\in A_t}x_{t,z}(z(c^\star)-z(c))\). The target is a possible co-winner precisely when this optimum is nonnegative. A solution consists of the mass allocation \(x\), together with a witnessing ideal point for every \(z\) receiving positive mass.
This is a direct high-multiplicity relaxation of the paper’s integer program. The paper already introduces \(n_\tau\), the number of voters of each behavioral type, and integer variables \(x^z_\tau\). The mirror replaces those integer counts by rational masses and asks for divisible population rather than individually named voters. Nothing else changes: the candidates remain discrete, the spatial uncertainty remains, the scoring rule remains, and “possible winner” still means existence of one completion in which \(c^\star\) is a co-winner.
The natural regime is a large election in which voters are surveyed or classified into a moderate number of uncertainty bins: for example, millions of voters whose ideal points are known only to lie in one of \(\tau\) recurring issue-space boxes. Here \(n\gg\tau\), and voters in one bin have the same relevant information and the same feasible score-vector set. This is not an artificial reinterpretation of the paper. The paper itself observes that only the feasible voting vectors matter and compresses voters into exactly these types.
The continuous problem is in Class A. There are at most \(m!\) score vectors, so the mass-allocation problem is an LP with at most \(\tau m!\) variables. If the \(A_t\) are supplied explicitly, this is polynomial in the explicit instance size. If the input consists of spatial boxes, each \(A_t\) can be generated by the feasibility tests already used in Lemma 8; enumerating the \(m!\) possibilities gives an \(f(m)\operatorname{poly}(\tau,d,L)\)-time algorithm. Thus the continuous mirror preserves the paper’s FPT parameterization, while replacing the fixed-dimensional integer program by an ordinary LP.
There is also a clean bridge back to discrete elections. With rational data, a feasible LP has a rational solution \(x\). Clearing denominators produces a finite election with sufficiently many clones of each type whose integer voter counts realize exactly those mass transfers. Conversely, every finite election induces rational masses. So this is not merely an analogy: it is the divisible, high-multiplicity version of the paper’s own formulation.
A second, narrower anchor is the paper’s Theorem 1, also proved here: for every constant \(k\), \(PW\langle1\rangle\) under any \(k\)-truncated scoring rule is solvable in polynomial time, specifically in time \(O(n^{1+k+3k^2}m^3)\).
Its continuous counterpart can be stated even more directly as One-Dimensional Interval-Cohort Possible Winner, \(1D\text{-}PW_\infty\). Candidates have rational positions \(c_1<\cdots<c_m\). A type \(t\) has a rational interval \(I_t=[\ell_t,u_t]\) and mass \(\mu_t\). The midpoints \((c_i+c_j)/2\), together with the fixed tie-breaking rule, partition the line into \(O(m^2)\) regions \(E\), each inducing one fixed candidate ranking and hence one score vector \(a_E\). Let \(\mathcal E_t\) be the regions intersecting \(I_t\). Choose variables \(y_{t,E}\ge0\) with \(\sum_{E\in\mathcal E_t}y_{t,E}=\mu_t\), and maximize \(\min_{c\ne c^\star}\sum_{t,E}y_{t,E}(a_E(c^\star)-a_E(c))\). Again, \(c^\star\) is possible exactly when the optimum is nonnegative.
This is an LP with \(O(\tau m^2)\) variables, so it is polynomial in \(m\), \(\tau\), and the numerical input length. It mirrors the paper’s top-\(k\) spatial uncertainty problem exactly, while making explicit what becomes divisible in the high-multiplicity regime. The paper’s shapes-scheduling construction describes the same local score patterns; the continuous version simply allocates cohort mass among those patterns.
Theorem 2 is my lead anchor because the paper itself supplies the relevant notion of type. Theorem 1 is a useful second anchor because it gives a genuinely polynomial mirror in \(m\), not merely an FPT one. The same first formulation also has an approval-voting variant by taking \(Z=\{0,1\}^m\), corresponding to the paper’s Theorem 3, although I would not count that as a separate anchor.
I would not anchor the positive case on Theorem 5, the NP-completeness of weighted \(PW\langle1\rangle\) with Borda for \(m=4\). A weighted continuous mirror can certainly be written by making \((I_t,w_t)\) part of the type and weighting each unit of mass by \(w_t\), but its plausibility is weaker when the hardness relies on many distinct weights. If weights repeat in a genuine cohort regime, the resulting problem is again an LP and the hardness likely disappears; if every voter has an idiosyncratic weight, then \(\tau\) grows with \(n\) and the high-multiplicity justification is poor.
The weakest point is therefore clear: the mirror permits one uncertainty type to split across several mutually exclusive spatial completions. That is not a faithful model of a seven-person committee, nor of an election in which every voter has a unique interval. It is faithful for a large electorate containing many indistinguishable voters in each uncertainty class. The argument survives because this is precisely the high-multiplicity regime the programme is meant to study, and rational LP solutions can be implemented exactly by sufficiently many clones.
The main further questions are whether the general \(CSPW_\infty\) LP admits algorithms polynomial in \(m\), rather than merely FPT in \(m\); whether succinct spatial descriptions create a continuum-specific pricing problem; how much finite-population rounding error is introduced at the co-winner boundary; and whether weighted or necessary-winner variants retain tractability under the same cohort assumptions.
The strongest negative case is that the proposed mirrors change the semantics of the paper’s problem. In \(PW\langle d\rangle\), each voter has an individually specified uncertainty box, and a completion chooses one ideal point for each named voter. Theorem 2’s behavioral “types” are an algorithmic quotient, not necessarily genuine population cohorts. Replacing the integer variables \(x^z_\tau\) by real masses allows one uncertainty type to split across several incompatible completions. That turns
\[ \exists (T_1,\ldots,T_n) \]
into the existence of a measure-valued mixture. If the uncertainty is epistemic, the latent position of each voter is fixed rather than divisible; if it is aleatory, the question has become one about an aggregate distribution, not the paper’s possible-winner question. The proposed witnessing point for each positive-mass \(z\) does not identify which voters occupy it.
The same objection applies to Theorem 1. Its shapes-scheduling reduction depends on indivisible jobs: each voter selects one interval of candidate scores. The continuous variables \(y_{t,E}\) dissolve the scheduling problem into a finite LP and therefore no longer mirror the combinatorial object whose complexity the theorem studies.
These are the best objections, but they do not survive the stronger mirror the programme permits. One can posit a genuine high-multiplicity regime: a large electorate contains many voters with the same uncertainty box, and a completion of an atomless cohort is a measurable assignment of ideal points within that box. Since only finitely many ranking cells or score vectors matter, assigning mass to cells is not a lottery imposed on named voters; it is exactly the continuum analogue of assigning many indistinguishable voters to different feasible completions. The paper itself supplies the relevant quotient through its sets of feasible voting vectors and counts \(n_\tau\). Thus Theorem 2 has a legitimate high-multiplicity relaxation, and its approval-voting variant from Theorem 3 does as well.
Theorem 1 likewise has a natural version: repeated interval cohorts in a one-dimensional electorate. The midpoint cells are genuine behavioral types, and the \(y_{t,E}\) variables describe the distribution of an atomless cohort across its feasible positions. The resulting LP may be less interesting than shapes scheduling, but “continuous does not help” or “the answer becomes easy” is expressly not an objection under this programme.
There is also no valid appeal to individual identity, absence of multiplicity, or prior continuous treatment. Possible-winner scoring depends only on aggregate scores; repeated uncertainty descriptions are a plausible electoral regime; and the paper contains no existing continuous computational analysis of that regime. The only remaining reservation is modelling fidelity: whether unresolved positions should be represented as cohort-level divisibility. That is a choice worth formalizing, not an obstruction.
So the honest negative case is weak. I cannot defeat either Theorem 2 or Theorem 1 under the programme’s high-multiplicity standard; both provide worthwhile continuous mirrors.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.