Answer: \(\mathrm{NP}\)-hard
Theorem 1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateAssuming P≠NP, there does not exist polynomial time 𝑂(1)-approximation algorithms for BRSV-R if R is 𝑘-approval for 𝑘≥3 or 𝑘-veto for 𝑘≥2 or borda.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(D=\{d_1,\ldots,d_{m+1}\}\), target \(d^\star\), a finite explicit type set \(\mathcal T\subseteq\Sigma(D)\times\mathbb Q_{\ge0}\), rational masses \(\mu_t\) summing to \(1\), integer \(\lambda>0\), rational budget \(B\), and Borda scores, choose transfers \(x_{t,\rho}\ge0\) satisfying \(\sum_{\rho}x_{t,\rho}\le\mu_t\) and \(\sum_{t=(\sigma_t,\kappa_t),\rho}\kappa_t x_{t,\rho}\le B\); let \(\nu_\rho=\sum_{\kappa:(\rho,\kappa)\in\mathcal T}(\mu_{(\rho,\kappa)}-\sum_{\eta}x_{(\rho,\kappa),\eta})+\sum_t x_{t,\rho}\), independently sample \(Z_\rho\sim\operatorname{Pois}(\lambda\nu_\rho)\), and maximize the probability that \(d^\star\) is a Borda co-winner.
Given \(D=\{d_1,\ldots,d_{m+1}\}\), let \(\Sigma(D)\) be the set of strict rankings of \(D\), and let \(d^\star\in D\). An input consists of a finite set of types \(\mathcal T\subseteq\Sigma(D)\times\mathbb Q_{\ge0}\), masses \(\mu_t\in\mathbb Q_{\ge0}\) with \(\sum_t\mu_t=1\), an integer \(\lambda>0\), and a budget \(B\in\mathbb Q_{\ge0}\). A type \(t=(\sigma_t,\kappa_t)\) has initial ranking \(\sigma_t\) and per-unit transfer cost \(\kappa_t\). Choose \(x_{t,\rho}\ge0\) for \(t\in\mathcal T,\rho\in\Sigma(D)\), with \(\sum_\rho x_{t,\rho}\le\mu_t\) and \(\sum_{t,\rho}\kappa_t x_{t,\rho}\le B\). The resulting mass of ranking \(\rho\) is \(\nu_\rho=\sum_{t:\sigma_t=\rho}(\mu_t-\sum_\eta x_{t,\eta})+\sum_t x_{t,\rho}\). Independently draw \(Z_\rho\sim\operatorname{Pois}(\lambda\nu_\rho)\); these are the numbers of sampled voters with ranking \(\rho\). Under Borda, \(d^\star\) succeeds when it is a co-winner.
Is maximizing \(\Pr[d^\star\text{ is a Borda co-winner}]\) in this continuous type-mass problem solvable in polynomial time, or is it NP-hard?
For the finite-voter independent-sampling version under Borda, assuming \(\mathrm P\ne\mathrm{NP}\), no polynomial-time \(O(1)\)-approximation algorithm exists. No result was verified for the Poisson type-mass formulation above.
The continuous Poisson type-mass problem is \( \mathrm{NP} \)-hard under Borda. More precisely, even with \( \lambda=1 \), costs in \( \{1,4\} \), and polynomially many explicitly listed types, it is \( \mathrm{NP} \)-hard to approximate the optimal success probability to inverse-polynomial additive accuracy. Consequently, exact polynomial-time maximization is impossible unless \( \mathrm P=\mathrm{NP} \).
This is a direct reduction; it does not rely on the stated finite-voter inapproximability result.
Write \(p=d^\star\). For a ranking \(\rho\) and candidate \(c\ne p\), define
\(a_\rho(c)=\operatorname{pos}_\rho(c)-\operatorname{pos}_\rho(p)\).
This equals the Borda-score contribution of \(\rho\) to \(p\)'s margin over \(c\). Thus, for sampled ranking counts \(Z_\rho\), \(p\) is a co-winner exactly when
\(\sum_\rho Z_\rho a_\rho(c)\ge 0\)
for every \(c\ne p\).
Because sums of independent Poisson variables are Poisson, voters can equivalently be regarded as a rate-\(1\) marked Poisson process whose mark distribution is the final ranking-mass vector.
We reduce from \( \mathrm{INDEPENDENT\ SET} \), which is \( \mathrm{NP} \)-complete by complementing the \( \mathrm{CLIQUE} \) instances in [Karp's classical reduction](https://doi.org/10.1007/978-1-4684-2001-2_9).
Let \(H=(V,E)\), where \(V=\{1,\ldots,n\}\). Write \(\alpha(H)\) for its independence number.
For every edge \(e\in E\), introduce a candidate \(c_e\). For every vertex \(i\), introduce a private candidate \(c_{\ell_i}\). Regard \(c_e\) as incident with the endpoints of \(e\), and \(c_{\ell_i}\) as incident only with \(i\).
Let
\(F=E\cup\{\ell_i:i\in V\}\)
and
\(\Delta=\max\bigl(2,\max_i(\deg_H(i)+1)\bigr)\).
Besides \(p\), introduce one candidate \(w\) and filler candidates \(f_1,\ldots,f_{\Delta-1}\). The number of candidates is polynomial in \(n\).
For each vertex \(i\), define a ranking \(r_i\) as follows:
Thus every incident forbidden candidate has margin between \(-\Delta\) and \(-1\), while every nonincident forbidden candidate has margin at least \(\Delta\).
Define
\(g:\quad p\succ f_1\succ\cdots\succ f_{\Delta-1}\succ\text{all forbidden candidates}\succ w\),
and let \(h\) be the reverse of \(g\). Hence
\(a_h(c)=-a_g(c)\)
for every \(c\ne p\).
For all vertices \(i,j\):
If \(i=j\), the private candidate \(c_{\ell_i}\) has a negative margin in both copies of \(r_i\), so \(p\) loses.
If \(\{i,j\}\in E\), then \(c_{\{i,j\}}\) has a negative margin in both rankings, so again \(p\) loses.
Suppose instead that \(i\ne j\) and \(\{i,j\}\notin E\). No forbidden candidate is incident with both vertices. A forbidden candidate incident with exactly one of them contributes at least \(-\Delta+\Delta=0\); one incident with neither contributes positively. The candidates \(w,f_1,\ldots,f_{\Delta-1}\) are below \(p\) in both rankings. Hence \(p\) is a co-winner.
In \(g+r_i\), every forbidden candidate receives margin at least \(\Delta\) from \(g\), offsetting its margin of at least \(-\Delta\) in \(r_i\). All other candidates have positive total margins. Finally, \(p\) is ranked first in both copies of \(g\). ∎
Set
\(\varepsilon=\frac{1}{100n^4}\), \(\qquad B=\varepsilon\left(1-\frac1n\right)\), \(\qquad \lambda=1\).
Create the following types:
The total mass is \(1\).
Although transfers may use any ranking whatsoever, the following lemma shows that arbitrary destinations do not bypass the construction.
Every optimal solution:
Consequently, an optimum is described by numbers \(q_i\) satisfying
\(0\le q_i\le\varepsilon/n\), \(\qquad \sum_iq_i=Q:=\varepsilon/n\),
where \(q_i\) is the mass left at \(r_i\), and the mass at \(g\) is exactly \(B\).
Let \(z\) be the transferred background mass. Since its cost is \(4\), \(z\le B/4<\varepsilon/4\). Hence the untransferred \(h\)-mass \(\beta\) and the total mass \(r\) of all other marked voters satisfy
\(\beta\ge1-\varepsilon-B/4\ge79/80\), \(\qquad r\le\varepsilon+B/4\le1/80\).
Consider a transferred mass \(\delta\) assigned to rankings other than \(g\), and reassign all of it to \(g\). Couple the two Poisson elections by relabelling a rate-\(\delta\) Poisson process.
If exactly one relabelled voter, exactly one untransferred \(h\)-voter, and no other nonbackground voter occur, then \(h+g\) is tied coordinatewise, whereas \(h+\rho\) cannot make \(p\) co-win for any \(\rho\ne g\). Indeed, \(h+\rho\) winning would require \(a_\rho\ge a_g\) coordinatewise. But
\(\sum_{c\ne p}a_\rho(c)=(m+1)\left(\frac{m+2}{2}-\operatorname{pos}_\rho(p)\right)\),
which is maximized by putting \(p\) first. Equality with the sum for \(g\), together with coordinatewise domination, forces \(a_\rho=a_g\), hence \(\rho=g\).
The probability of this strict-gain event is \(\delta\beta e^{-1}\). A loss can occur only if at least two relabelled voters occur or another nonbackground voter occurs. Its probability is at most \(\delta r\). Since
\(\beta/e-r>0\),
reassigning to \(g\) strictly improves the objective. Therefore every transferred voter goes to \(g\).
Now consider relabelling a mass \(\delta\) from some \(r_i\) to \(g\). If there is exactly one such voter, no other nonbackground voter, and zero or one \(h\)-voter, the change is strictly beneficial. The gain is at least
\(\delta(1+\beta)e^{-1}-\delta r>\delta/2\).
Suppose \(z>0\) background mass were transferred. Undoing that transfer can decrease success probability by at most \(z\), by the same Poisson coupling. It frees budget \(4z\), which can transfer \(4z\) additional active mass to \(g\); enough active mass remains because \(4z\le B-y\), where \(y\) was the previously transferred active mass. The latter change improves the probability by more than \(2z\). The combined change is strictly beneficial, contradicting optimality. Hence \(z=0\).
Finally, if some budget remained unused, transferring additional \(r_i\)-mass to \(g\) would improve the objective by more than one half of the transferred mass. Thus the whole budget is spent. ∎
After Lemma 2, let \(A\sim\operatorname{Pois}(\varepsilon)\) be the number of nonbackground voters and \(H_0\sim\operatorname{Pois}(1-\varepsilon)\) the number of background voters.
For one active voter:
For two active voters:
Define
\(L_H(q)=\sum_iq_i^2+2\sum_{\{i,j\}\in E}q_iq_j\).
All contributions involving at most two active voters therefore give
\(F(q)=C-\frac{e^{-1}}2L_H(q)+R(q)\),
where \(C\) is independent of \(q\), namely
\(C=e^{-1}\left(1+B(2-\varepsilon)+\frac{\varepsilon^2}{2}+\frac{(1-\varepsilon)B^2}{2}+\frac{(1-\varepsilon)^2B^2}{4}\right)\),
and \(R(q)\) is the success probability contributed by events with \(A\ge3\).
Using the third falling factorial of a Poisson variable,
\(0\le R(q)\le\Pr[A\ge3]\le\frac{\mathbb E[A(A-1)(A-2)]}{6}=\frac{\varepsilon^3}{6}=:\tau\).
Put \(p_i=q_i/Q\), where \(Q=\varepsilon/n\). Then \(p_i\ge0\) and \(\sum_i p_i=1\). Moreover,
\(\frac{L_H(q)}{Q^2}=\sum_i p_i^2+2\sum_{\{i,j\}\in E}p_ip_j\).
Since the remaining unordered pairs are precisely the edges of the complement graph,
\(\sum_i p_i^2+2\sum_{\{i,j\}\in E}p_ip_j=1-2\sum_{\{i,j\}\notin E,\ i\ne j}p_ip_j\).
The [Motzkin–Straus theorem](https://doi.org/10.4153/CJM-1965-053-6), applied to the complement of \(H\), states that the maximum of the last edge sum is
\(\frac12\left(1-\frac1{\alpha(H)}\right)\).
Consequently,
\(\min_q L_H(q)=\frac{Q^2}{\alpha(H)}\).
Therefore, if \(V_H\) denotes the optimal Poisson success probability,
\(C-\frac{e^{-1}Q^2}{2\alpha(H)}\le V_H\le C-\frac{e^{-1}Q^2}{2\alpha(H)}+\tau\).
For consecutive possible values \(a\) and \(a+1\), the distance between the corresponding lower endpoints is
\(\frac{e^{-1}Q^2}{2a(a+1)}\ge\frac{e^{-1}\varepsilon^2}{2n^4}>\frac{\varepsilon^2}{6n^4}\),
where \(e<3\) was used.
On the other hand,
\(\tau\le\frac{\varepsilon^3}{6}=\frac{\varepsilon^2}{600n^4}\).
Thus the intervals corresponding to distinct values of \(\alpha(H)\) are disjoint with inverse-polynomial separation. In particular, an additive approximation with error
\(\eta=\frac{\varepsilon^2}{1000n^4}=\frac{1}{10^7n^{12}}\)
determines whether \(\alpha(H)\ge k\). The quantities involving \(e^{-1}\) can be computed to the required polynomial number of bits.
Hence inverse-polynomial additive approximation of the optimal value is \( \mathrm{NP} \)-hard.
The same construction also rules out an exact optimizer that returns only an optimal transfer vector: if \(q^\star\) is obtained from such a vector, then
\(\frac1{\alpha(H)}\le\frac{L_H(q^\star)}{Q^2}\le\frac1{\alpha(H)}+\frac{e\varepsilon n^2}{3}<\frac1{\alpha(H)}+\frac1{100n^2}\).
The distinct reciprocals \(1,1/2,\ldots,1/n\) are separated by more than \(1/n^2\), so \(\alpha(H)\) can again be recovered.
Maximizing the Poisson Borda co-winner probability in the stated continuous type-mass model is \( \mathrm{NP} \)-hard, already for \( \lambda=1 \) and two transfer costs. This proves direct hardness for the Poisson formulation; the finite-voter \(O(1)\)-inapproximability statement is neither needed nor transferred.
The proof establishes inverse-polynomial additive hardness, not constant-factor inapproximability.
⟨structured verdict parsed — rendered above⟩
The reduction is substantively correct and establishes NP-hardness of inverse-polynomial additive approximation for the continuous Poisson type-mass problem. The ranking gadget, Poisson expansion, Motzkin–Straus application, and numerical separation all check out.
Several coupling estimates and computational-model details are asserted too tersely to count as fully rigorous as written. These are minor gaps: each requires an explicit routine justification rather than a new mathematical idea.
The definition
\[ a_\rho(c)=\operatorname{pos}_\rho(c)-\operatorname{pos}_\rho(p) \]
correctly equals the contribution of ranking \(\rho\) to \(p\)'s Borda margin over \(c\). Consequently, the coordinatewise nonnegativity criterion for \(p\) to be a co-winner is correct.
The marked Poisson-process interpretation is also valid because the final ranking masses sum to \(1\) and \(\lambda=1\).
Let \(s_i=\deg_H(i)+1\). Then \(s_i\leq\Delta\). In \(r_i\):
In \(g\), every forbidden candidate is at least \(\Delta\) positions below \(p\). Reversing a ranking negates all margins relative to \(p\), so \(a_h(c)=-a_g(c)\) is correct.
The construction remains meaningful when \(\Delta=2\): the list \(f_1,\ldots,f_{\Delta-2}\) is empty.
For \(r_i+r_j\):
Thus the claimed characterization is correct.
The assertions about \(g+r_i\) and \(g+g\) are also correct. The last sentence, “Finally, \(p\) is ranked first in both copies of \(g\),” is evidently intended to justify the \(g+g\) case, but its placement is grammatically unclear.
The numerical bounds are valid:
\[ \beta\geq 1-\varepsilon-\frac B4\geq\frac{79}{80}, \qquad r\leq\varepsilon+\frac B4\leq\frac1{80}. \]
The coordinatewise-domination argument for \(h+\rho\) is correct. If \(h+\rho\) is winning, then \(a_\rho\geq a_g\). The displayed sum of all margins is maximized when \(p\) is first; since \(g\) already puts \(p\) first, coordinatewise domination forces equality in every coordinate and hence \(\rho=g\).
The coupling comparison is sound in substance, but two probability estimates are not proved explicitly:
The analogous estimate for relabelling \(r_i\)-mass to \(g\) has the same omission. These are routine Poisson-coupling calculations, but they are critical to strict optimality and should be written out.
When background transfer is removed, the text says sufficient active mass remains because \(4z\leq B-y\). That inequality alone does not imply the capacity claim. The additional already-available fact \(B\leq\varepsilon\) is required to conclude
\[ 4z\leq B-y\leq\varepsilon-y. \]
Thus the conclusion is correct, but one premise is omitted from that sentence.
Subject to those clarifications, the normal form
\[ 0\leq q_i\leq Q,\qquad \sum_iq_i=Q,\qquad Q=\frac{\varepsilon}{n} \]
is established.
The cases with zero, one, and two active voters are correctly classified.
In particular:
\[ \frac{e^{-1}}2 \left( \sum_iq_i^2+2\sum_{\{i,j\}\in E}q_iq_j \right). \]
Therefore
\[ F(q)=C-\frac{e^{-1}}2L_H(q)+R(q) \]
with the displayed \(C\) is correct.
The remainder estimate is also correct:
\[ 0\leq R(q)\leq\Pr[A\geq3] \leq\frac{\mathbb E[A(A-1)(A-2)]}{6} =\frac{\varepsilon^3}{6}. \]
After setting \(p_i=q_i/Q\), the feasible region is the probability simplex. The additional upper bound \(p_i\leq1\) is automatic.
The identity
\[ \frac{L_H(q)}{Q^2} = 1-2\sum_{\{i,j\}\notin E}p_ip_j \]
is correct. Applying Motzkin–Straus to the complement graph is appropriate because its clique number is \(\alpha(H)\). Hence
\[ \min_qL_H(q)=\frac{Q^2}{\alpha(H)} \]
is correct.
For \(1\leq a<n\), the separation between consecutive main terms is
\[ \frac{e^{-1}Q^2}{2a(a+1)} \geq \frac{e^{-1}\varepsilon^2}{2n^4} > \frac{\varepsilon^2}{6n^4}. \]
Also,
\[ \tau=\frac{\varepsilon^3}{6} =\frac{\varepsilon^2}{600n^4}. \]
The proposed approximation error
\[ \eta=\frac{\varepsilon^2}{1000n^4} =\frac1{10^7n^{12}} \]
is sufficiently smaller than the interval separation. Thus an additive-\(\eta\) value approximation distinguishes the possible values of \(\alpha(H)\).
The text should explicitly state the comparison threshold for deciding whether \(\alpha(H)\geq k\), including the approximation error and the rational approximation to \(e^{-1}\). The existing separation estimates plainly provide such a threshold, so this is an expositional rather than mathematical gap.
The exact-optimizer paragraph is algebraically correct:
\[ \frac{L_H(q^\star)}{Q^2} \leq \frac1{\alpha(H)}+\frac{e\varepsilon n^2}{3} < \frac1{\alpha(H)}+\frac1{100n^2}. \]
However, it assumes without stating a computational representation in which the optimizer returns the transfer vector with enough exact or certified precision to compute \(L_H(q^\star)\). This should be made explicit when claiming hardness of an optimizer rather than hardness of optimal-value approximation.
Finally, the reduction should formally restrict to standard simple-graph Independent Set instances with \(n\geq2\). This is harmless because the source problem remains NP-hard under that restriction.
⟨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.