| paper | Spatial Voting with Incomplete Voter Information |
| authors | — |
| venue | AAAI 2024 |
| 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 9
statement extracted from the paper’s text layer
Given rational candidate positions on the real line, finitely many voter types with rational masses summing to one, an interval and approval radius for each type, and a target candidate, let \(A_t\) be the approval sets induced by points in type \(t\)'s interval. Does there exist a mass allocation \(x_{t,A} \ge 0\) with \(\sum_A x_{t,A} = \mu_t\) for every type such that the target's total approval is at least every candidate's total approval?
A nonatomic high-multiplicity electorate of independent agents grouped into identical interval-and-radius types; variables allocate each type's mass among its feasible approval sets, and feasibility means a nonnegative target approval margin against every candidate.
The mirror covers Theorems 9, 6, and 2; it leaves Theorems 3–5, 7–8, the partial-order comparison, and the approval-based committee extension unmirrored. Lemma 2 and Theorem 7 serve as supporting enumeration tools.
The strongest positive case is a high-multiplicity version of the paper’s own partial-spatial model. The paper already has continuous ideal-point geometry, but its society is still a list of individually represented voters. My mirror makes the electorate continuous while preserving the candidates, Euclidean rankings, uncertainty rectangles, approval radii, tie-breaking, and possible/necessary-winner questions.
Take a fixed dimension \(d\), candidate locations \(p(c)\in\mathbb Q^d\), and finitely many voter types \(T\). Type \(t\) consists of:
Thus a type is a cohort of voters identical in every respect used by the paper. The intended regime is a large election—say millions of voters classified into a few hundred region-and-issue-position cohorts—so \(n\gg\tau\), where \(\tau=|T|\).
For each type, let \(\mathcal B_t\) be the finite set of ballots induced by points in \(B_t\). A continuous completion chooses variables \(x_{t,b}\ge 0\), where \(x_{t,b}\) is the mass of type \(t\) assigned ballot \(b\), subject to
\[ \sum_{b\in\mathcal B_t}x_{t,b}=\mu_t. \]
This is exactly the high-multiplicity relaxation: with \(M\) copies of type \(t\), rational \(x_{t,b}\) can be implemented by assigning \(Mx_{t,b}\) voters to ballot \(b\). The only new freedom is divisibility among identical voters, which is the point of the continuum.
My lead anchor is Theorem 9, proved in this paper: \(PW\langle d\rangle\) is NP-complete for approval voting for every \(d\ge1\). The reduction uses cited NP-hardness of non-preemptive scheduling, but the voting theorem itself is established here.
Call the mirror Mass-Possible-Winner-AV\(\langle1\rangle\). An instance consists of rational one-dimensional candidate positions, a finite distribution over interval-and-radius types, a target candidate \(c^\star\), and approval voting. For type \(t\), define
\[ \mathcal A_t=\{A\subseteq C:\exists x\in B_t,\ A=\{c:\lvert x-p(c)\rvert\le \rho_t\}\}. \]
The question is whether there are variables \(x_{t,A}\) satisfying the mass constraints and making \(c^\star\) a co-winner:
\[ \sum_{t,A}x_{t,A}\mathbf 1[c^\star\in A] \ \ge\ \sum_{t,A}x_{t,A}\mathbf 1[c\in A] \qquad\text{for every }c\in C. \]
Equivalently, maximize the target’s minimum approval margin. A solution is the mass allocation \(x\), together with a geometric witness point for every approval set receiving positive mass.
I expect this problem to be in Class A. The paper’s Theorem 7, proved here, gives polynomial-time enumeration of all approval completions of one voter for \(d\le2\). In one dimension, each \(\mathcal A_t\) therefore has polynomial size, and the displayed formulation is an LP with polynomially many variables and constraints. The NP-hardness in Theorem 9 is consequently not preserved in the cohort regime: it comes from coordinating individually represented voters with different scheduling windows, whereas a repeated cohort can divide its mass fractionally among its feasible approval sets.
This is a faithful mirror. The original authors should recognize the same spatial approval model and the same possible-winner semantics; only the list of repeated voter rows has been replaced by their histogram. It is not claiming that every finite election in Theorem 9 becomes easy—only that its high-multiplicity analogue is a meaningful and computationally different object.
A second, independent anchor is Theorem 6, also proved in this paper: for every fixed \(d\ge2\) and \(k\ge3\), \(PW\langle d\rangle\) is NP-complete for \(k\)-approval. The reduction again comes from scheduling, this time with job lengths \(k\) and \(k-1\), using the cited result of Elffers and de Weerdt.
The mirror is Mass-Possible-Winner-\(k\)-Approval\(\langle2\rangle\). The instance has rational two-dimensional candidate locations, masses of interval-box types, a fixed \(k\ge3\), and a target \(c^\star\). For each type \(t\), let
\[ \mathcal K_t=\{\text{top-}k\text{ candidate sets induced by points in }B_t\}. \]
Choose \(x_{t,A}\ge0\) for \(A\in\mathcal K_t\), with \(\sum_Ax_{t,A}=\mu_t\). The target is possible exactly when
\[ \sum_{t,A}x_{t,A}\mathbf 1[c^\star\in A] \ \ge\ \sum_{t,A}x_{t,A}\mathbf 1[c\in A] \]
for every candidate \(c\).
For fixed \(d\), the paper’s Lemma 2, proved here using the arrangement argument and the cited Lemma 1 of Jamieson and Nowak, enumerates all feasible rankings of one spatial type in polynomial time—\(O(m^{2d})\) possibilities. Taking their top \(k\) candidates gives all \(\mathcal K_t\). Hence the continuous problem is again a polynomial-size LP for fixed \(d\), including the paper’s hard \(d=2,k\ge3\) case.
This second anchor matters because it shows that the positive case is not specific to approval radii or to the geometry of circles. It is the same phenomenon for ranked positional voting: the discrete hardness is scheduling-style integrality over individually represented voters, and mass divisibility removes that bottleneck.
A third, more conservative anchor is Theorem 2, proved in this paper: for every positional scoring rule and every fixed \(d\), \(NW\langle d\rangle\) is solvable in polynomial time. Its continuous counterpart is Mass-Necessary-Winner-Scoring\(\langle d\rangle\). For each type \(t\), let \(\mathcal R_t\) be its feasible rankings. For a target \(c^\star\), compute
\[ \Delta(c^\star)= \max_{c\ne c^\star} \sum_t\mu_t \max_{R\in\mathcal R_t} \bigl(s(R,c)-s(R,c^\star)\bigr). \]
The target is necessary exactly when \(\Delta(c^\star)\le0\). The reason is that a rival’s worst score difference is additive across types, and an adversarial mass realization can put every unit of a type on its worst feasible ranking. Lemma 2 enumerates those rankings in polynomial time, so this mirror remains in Class A.
The scope is therefore deliberately focused: I am not claiming to continuize every result in the paper. These three mirrors cover the paper’s central possible-winner hardness results, Theorems 9 and 6, and its general necessary-winner algorithm, Theorem 2. They predict a clean population-driven tractability boundary. Open follow-ups include the case where \(d\) is part of the input, exact rounding guarantees back to finite electorates, and whether additional cross-agent correlations or identity-specific constraints can restore hardness.
The weakest point is clear. The paper’s reductions use heterogeneous voters whose interval windows encode different jobs. If one insists that every voter must remain individually indivisible, the LP mirror is too weak—but that is precisely the finite-population problem, not its high-multiplicity version. In the proposed cohort scenario, many voters genuinely share the same uncertainty description, and fractional allocation of their mass is the honest aggregate quantity. The paper’s spatial coordinates are continuous already; the contribution of the mirror is making the society continuous and exposing which of its hardness results were really driven by voter multiplicity.
The strongest negative case is that the proposed mirrors do not preserve the paper’s central object. In the paper, a possible winner requires one jointly realized completion of the named voters. The proposed LP instead permits a cohort sharing one uncertainty box to split its mass among several ballots. That is a measure-valued completion, not merely a larger version of the paper’s completion. The scheduling reductions in Theorems 6 and 9 rely precisely on each voter/job being an indivisible unit with its own window. If all copies of a type must share one hidden position, the split is invalid; if they may split independently, the scheduling structure has been convexified away.
This also exposes the limitation of all three anchors: they are not three independent continuizations, but one generic operation. Once each type’s feasible ballot set is enumerable, possible-winner feasibility is a linear program for any additive voting rule, and necessary-winner testing is a typewise maximum. The spatial geometry merely supplies the ballot sets. Theorem 7 and Lemma 2 already provide the enumeration needed, so the proposed continuous results are immediate weighted extensions of the paper’s algorithms rather than new spatial-complexity phenomena.
That is a respectable reservation, but it does not defeat Theorem 9 under the programme’s stated standards. A cohort of voters sharing a region, issue-position band, and approval radius is a perfectly coherent high-multiplicity regime. For such a cohort, independent hidden positions are exactly the natural nonatomic interpretation of individual uncertainty. The resulting Mass-Possible-Winner-AV problem is well posed, uses the paper’s model, and has a polynomial-size LP in one dimension. The fact that the answer differs from the finite problem is not an objection here: identifying that the scheduling hardness depended on indivisibility is precisely the intended Class-A payoff.
Theorem 6 survives for the same reason, and more strongly. Repeated two-dimensional uncertainty boxes are no less meaningful than repeated preference types; they could describe large demographic or geographic cohorts. Lemma 2 gives polynomially many feasible rankings per cohort for fixed dimension, after which the mass possible-winner problem is again an exact LP. One could insist that the cohort has a common unknown location, but that would be an additional correlation assumption, not a more faithful consequence of the paper. Under the independent-agent interpretation, the proposed mirror is legitimate.
Theorem 2 is the weakest anchor as a contribution: its continuous version simply replaces the voter sum by a weighted type sum, while the existing proof already decomposes completely by voter. It adds little beyond a high-multiplicity restatement. But that does not invalidate it, and Theorems 6 and 9 do not depend on this weaker anchor.
Thus the honest negative case can question whether the authors’ particular application supplies a convincing real-world reason for millions of voters to share identical uncertainty descriptions. It can also recommend studying correlated cohort uncertainty or finite-population rounding, where the distinction between a true continuum and a fractional relaxation becomes substantive. But it cannot defeat the proposed mirrors themselves. Under the programme’s explicit acceptance of high-multiplicity relaxation, Theorem 9—and independently Theorem 6—provides a worthwhile continuous mirror. A universal “no scenario works” verdict would therefore overstate the evidence.
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.