Answer: \(\mathsf{P}\)
Theorem 9 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximatePW⟨d⟩is NP-complete for any d ≥1 for AV. 5Note that every two d-spheres intersect in a (d−1)-sphere. For d ≥3, it is thus not clear how to define the corresponding event points for a sweep plane algorithm in d dimensions. We now briefly discuss the impact of these results on approval-based multi-winner elections. Approval-based committee voting.
statement extracted from the paper’s text layer; consult the paper for the exact wording
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?
Definitions. Let \(C\) be a finite candidate set with rational positions \(p_c\in\mathbb{Q}\). Each voter type \(t\) has an interval \(I_t=[\ell_t,u_t]\), approval radius \(\rho_t\), and rational mass \(\mu_t\). Its realizable approval sets are \(\mathcal A_t=\{\{c\in C:|x-p_c|\le\rho_t\}:x\in I_t\}\). A mass assignment chooses \(x_{t,A}\ge0\) with \(\sum_{A\in\mathcal A_t}x_{t,A}=\mu_t\); candidate \(c\)'s approval score is \(\sum_{t,A:c\in A}x_{t,A}\). The target \(c^\star\) is a possible winner if some mass assignment gives it score at least every other candidate's score.
Target. Is this continuous possible-winner problem for one-dimensional spatial approval voting in \(\mathsf{P}\), or is it \(\mathsf{NP}\)-hard?
Nearest known results. The corresponding discrete problem, with one independently positioned voter for each interval and ordinary approval voting, is \(\mathsf{NP}\)-complete already in one dimension. No result for the mass-by-type formulation is stated here.
Theorem. Under the standard binary encoding in which the candidates and voter types are listed explicitly, the continuous possible-winner problem belongs to \(\mathsf{P}\).
The essential reason is that each type may split its mass arbitrarily among its realizable approval sets. Consequently, the possible-winner question is a rational linear-program feasibility problem of polynomial size.
Fix a voter type \(t\), and write
\[ I_t=[\ell_t,u_t],\qquad \rho_t\ge 0. \]
For a position \(x\in I_t\), define
\[ F_t(x)=\{c\in C:p_c-\rho_t\le x\le p_c+\rho_t\}. \]
Thus \(\mathcal A_t=\{F_t(x):x\in I_t\}\).
Let
\[ B_t=\{\ell_t,u_t\}\cup \bigl(\{p_c-\rho_t,p_c+\rho_t:c\in C\}\cap I_t\bigr). \]
Remove repetitions and sort the resulting rational numbers:
\[ s_1<s_2<\cdots<s_k. \]
Define the finite sample set
\[ E_t=\{s_1,\ldots,s_k\}\cup \left\{\frac{s_i+s_{i+1}}2:1\le i<k\right\}. \]
Every realizable approval set of type \(t\) is attained at some point of \(E_t\). Hence
\[ \mathcal A_t=\{F_t(x):x\in E_t\}. \]
Let \(x\in I_t\).
If \(x=s_i\) for some \(i\), then \(x\in E_t\), so there is nothing to prove.
Otherwise, \(x\) lies in a unique open interval \((s_i,s_{i+1})\). Fix a candidate \(c\). The truth value of
\[ p_c-\rho_t\le y\le p_c+\rho_t \]
can change as \(y\) varies only when \(y\) crosses one of the two boundary points \(p_c-\rho_t\) or \(p_c+\rho_t\). By construction, no such boundary point lies in \((s_i,s_{i+1})\). Therefore membership of \(c\) in \(F_t(y)\) is constant throughout this open interval.
Taking \(y=(s_i+s_{i+1})/2\in E_t\) gives \(F_t(x)=F_t(y)\). Since this holds for every \(x\in I_t\), the claimed equality follows. Evaluating the points \(s_i\) themselves also handles closed interval boundaries, simultaneous boundary events, and the case \(\rho_t=0\). \(\square\)
If \(m=|C|\), then \(k\le 2m+2\), and therefore
\[ |E_t|\le 2k-1\le 4m+3. \]
Thus each \(\mathcal A_t\) contains at most \(4m+3\) distinct sets and can be enumerated in polynomial time. All required operations are sorting, addition, subtraction, and comparison of binary-encoded rational numbers, so their bit complexity is polynomial in the input length.
Enumerate the distinct sets in \(\mathcal A_t\) as
\[ \mathcal A_t=\{A_{t,1},\ldots,A_{t,r_t}\}. \]
Introduce a variable \(x_{t,j}\) for the mass of type \(t\) assigned to \(A_{t,j}\).
For every type \(t\), impose
\[ x_{t,j}\ge 0\quad\text{for all }j, \qquad \sum_{j=1}^{r_t}x_{t,j}=\mu_t. \]
The resulting approval score of candidate \(c\) is the linear expression
\[ S_c(x)=\sum_t\sum_{\substack{1\le j\le r_t\\c\in A_{t,j}}}x_{t,j}. \]
To make \(c^\star\) a co-winner, impose, for every \(c\in C\setminus\{c^\star\}\),
\[ S_{c^\star}(x)-S_c(x)\ge 0. \]
Call this rational linear system \(L\).
The target \(c^\star\) is a possible winner if and only if \(L\) is feasible.
Suppose first that a mass assignment witnessing that \(c^\star\) is a possible winner exists. Since every set used by type \(t\) belongs to the enumerated family \(\mathcal A_t\), its assigned masses give variables \(x_{t,j}\) satisfying nonnegativity and the mass-conservation equality. The winner inequalities hold because the assignment gives \(c^\star\) score at least that of every opponent. Hence \(L\) is feasible.
Conversely, suppose \(L\) has a feasible solution. For every \(t\) and \(j\), assign mass \(x_{t,j}\) to the realizable approval set \(A_{t,j}\). The mass-conservation constraints make this a valid mass assignment. Its candidate scores are exactly the expressions \(S_c(x)\), and the remaining constraints give \(S_{c^\star}(x)\ge S_c(x)\) for every candidate \(c\). Thus \(c^\star\) is a possible winner. \(\square\)
If there are \(q\) explicitly listed voter types, then the number of variables is at most
\[ \sum_t r_t\le q(4m+3). \]
There are \(q\) mass-conservation equalities, at most \(m-1\) winner inequalities, and one nonnegativity constraint per variable. All matrix coefficients belong to \(\{-1,0,1\}\), while the right-hand sides are \(0\) or the input masses \(\mu_t\).
Feasibility of a rational linear system can be decided in time polynomial in its number of variables, number of constraints, and binary encoding length. The constructed system therefore has polynomial size and can be tested in polynomial time.
In the discrete problem, each voter must make one indivisible choice of position and hence one indivisible choice of approval set. Those choices create integer or combinatorial constraints.
Here, a type of mass \(\mu_t\) may split that mass among all its realizable approval sets. Its attainable score contribution is therefore the scaled convex hull of finitely many \(0\)-\(1\) approval vectors. Comparing the sum of these convex contributions with the target score requires only linear inequalities; no integrality constraint remains.
The continuous mass-by-type possible-winner problem is polynomial-time solvable by enumeration of the polynomially many approval patterns followed by rational linear-program feasibility. Thus the requested classification is \(\mathsf{P}\). As usual, membership in \(\mathsf{P}\) rules out \(\mathsf{NP}\)-hardness under polynomial-time many-one reductions unless \(\mathsf{P}=\mathsf{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover correctly classifies the explicitly encoded rational mass-by-type problem as polynomial-time solvable. The enumeration argument captures every realizable approval set, the linear program is equivalent to the possible-winner condition, and its size and coefficient encoding are polynomial.
The only gap is an input-model ambiguity: the proof uses binary-encoded rational interval endpoints and approval radii, although the task explicitly declares only candidate positions and masses rational. This is an expositional issue repairable by stating the numerical encoding assumption precisely.
For a fixed type \(t\), candidate \(c\)'s membership changes only at \(p_c-\rho_t\) or \(p_c+\rho_t\). Including all such boundary points lying in \(I_t\), together with \(\ell_t\) and \(u_t\), partitions the interval into singleton boundary points and open subintervals.
The argument that \(F_t\) is constant on each open subinterval is correct. Sampling every boundary point and one midpoint of every adjacent pair therefore captures:
The bound \(k\leq 2m+2\) is correct, as is
\[ |E_t|\leq 2k-1\leq 4m+3. \]
Duplicated approval sets may be removed without changing the feasible mass assignments.
The variables \(x_{t,j}\), nonnegativity constraints, and equations
\[ \sum_j x_{t,j}=\mu_t \]
exactly match the definition of a mass assignment once all distinct realizable approval sets have been enumerated.
The score expressions \(S_c(x)\) are correct. Requiring
\[ S_{c^\star}(x)-S_c(x)\geq 0 \]
for every opponent correctly models co-winner status, matching the task's “score at least every other candidate's score” condition.
Both directions of the feasibility equivalence are justified. No integrality condition is required because the definition expressly permits arbitrary splitting of each type's mass.
With \(q\) explicitly listed types, the variable count is at most \(q(4m+3)\). The stated constraint counts are correct. After combining the two score sums, the coefficients are indeed in \(\{-1,0,1\}\), and the right-hand sides are either \(0\) or an input mass.
Polynomial-time feasibility of rational linear systems applies, provided all numerical input has finite binary rational encoding. Sorting boundary points, computing midpoints, testing candidate membership, deduplicating approval sets, and constructing the LP all require only polynomially many operations on polynomial-bit-length rationals.
The proof assumes that \(\ell_t\), \(u_t\), and \(\rho_t\) are binary-encoded rationals. This appears in the assertion that all boundary computations involve “binary-encoded rational numbers,” but it is not stated explicitly in the theorem.
The user task explicitly calls \(p_c\) and \(\mu_t\) rational but does not equally specify the domains or encodings of \(\ell_t\), \(u_t\), and \(\rho_t\). Merely saying “standard binary encoding” does not completely resolve this ambiguity. Complexity is not well-defined for arbitrary unencoded real parameters.
This is minor because the proof is complete under the evident finite rational encoding, and repairing the write-up requires only an explicit input assumption, not a new mathematical argument.
The explanation is consistent with the formal proof. Discrete voters create indivisible choices, whereas the stated mass model replaces each type's possible contributions by arbitrary convex combinations. Consequently, the discrete NP-hardness result does not directly apply.
State explicitly that every \(\ell_t\), \(u_t\), and \(\rho_t\), in addition to every \(p_c\) and \(\mu_t\), is a binary-encoded rational number, with all candidates and voter types listed explicitly.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.