Answer: \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions
Proposition 1 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateCandidate x 2 Y is a robust winner w.r.t. hX, Y, v, ri if there is no destructive control against x by adding candidates, where the spoiler set is U = X \ Y . The proof is immediate: the chair has destructive con- trol against x via adding candidates iff there is a spoiler set S ✓U such that r(v(Y [ S)) 6= x (i.e., x is not a robust winner).
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(X\), a known-available set \(Y\subseteq X\), a target \(x^\star\in Y\), and a distribution \(\mu\) over a support of complete rankings, does \(x^\star\) win under the paper’s plurality tie-breaking rule for every available set \(A\) with \(Y\subseteq A\subseteq X\), when each candidate’s score is the total mass of rankings that place it first in \(A\)?
Given a finite candidate set \(X\), let \(m=|X|\), and let \(x^\star\in Y\subseteq X\) be a target and a known-available set.
A society is given by its support: a list of \(\tau\) distinct complete, strict rankings of \(X\), each with positive binary rational mass; the masses sum to \(1\). Here \(\tau\) is the support size, not the number of possible rankings.
An additional input is a strict priority order on \(X\). For each available set \(Y\subseteq A\subseteq X\), use plurality with mass-weighted scores and select the highest-priority candidate among those with maximum score, restricting the same priority order to \(A\).
Call \(x^\star\) robust if it wins for every such \(A\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L\).
Is deciding whether \(x^\star\) is robust in \(\mathrm{P}\), or is it \(\mathrm{coNP}\)-hard?
For finite electorates, robustness is equivalent to the absence of destructive control by adding any subset of the unknown candidates; plurality robustness is reported as \(\mathrm{coNP}\)-complete ([Boutilier et al.](https://ojs.aaai.org/index.php/AAAI/article/download/8893/8752)).
Destructive plurality control by adding candidates is \(\mathrm{NP}\)-complete in the unique-winner model ([Hemaspaandra et al.](https://arxiv.org/pdf/cs/0507027)). No result settling the exact rational-mass formulation with the specified priority order was located.
Deciding robustness is \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions. This holds even when the target has lowest priority.
Here “binary rational” means a rational number whose numerator and denominator are encoded in binary.
Write the support as distinct rankings \(R_1,\ldots,R_\tau\), with masses \(\mu_i=p_i/q_i>0\). For a nonempty available set \(A\), let \(\operatorname{top}_i(A)\) be its highest-ranked candidate in \(R_i\). Define
\(\displaystyle s_A(x)=\sum_{\{i:\operatorname{top}_i(A)=x\}}\mu_i.\)
A certificate of nonrobustness is a subset \(S\subseteq X\setminus Y\), encoded by at most \(m\) bits. The verifier computes the winner on \(A=Y\cup S\) and accepts exactly when that winner differs from \(x^\star\).
All score comparisons can be performed exactly in polynomial time. Set
\(\displaystyle Q=\prod_{i=1}^{\tau}q_i,\qquad w_i=p_i(Q/q_i).\)
The bit length of \(Q\) is at most the sum of the denominator bit lengths, hence is \(\mathrm{O}(L)\). Each \(w_i\) is an integer, and the normalization hypothesis gives
\(\displaystyle \sum_{i=1}^{\tau}w_i=Q.\)
Consequently, every integer score
\(\displaystyle W_A(x)=\sum_{\{i:\operatorname{top}_i(A)=x\}}w_i\)
has \(\mathrm{O}(L)\) bits. Moreover, \(W_A(x)=Qs_A(x)\), so these integer scores preserve every comparison and tie.
Using elementary integer multiplication and division, computing all weights takes \(\mathrm{O}(\tau L^2)\) bit operations. With candidates indexed by binary identifiers, scanning all rankings, accumulating scores, and applying the priority order takes
\(\displaystyle \mathrm{O}\!\left(\tau m\log(m+1)+(\tau+m)L\right)\)
bit operations. Including input reading, certificate verification therefore takes
\(\displaystyle \mathrm{O}\!\left(L+\tau L^2+\tau m\log(m+1)+(\tau+m)L\right).\)
Thus nonrobustness belongs to \(\mathrm{NP}\), and robustness belongs to \(\mathrm{coNP}\).
We use the following established result: given disjoint qualified and additional candidate sets \(C,D\), a distinguished candidate \(c\in C\), and an explicitly listed finite electorate with complete strict rankings of \(C\cup D\), it is \(\mathrm{NP}\)-complete to decide whether some \(S\subseteq D\) makes \(c\) fail to be the unique plurality winner on \(C\cup S\).
This is the destructive plurality control problem in Section 3 of [Hemaspaandra, Hemaspaandra, and Rothe](https://arxiv.org/pdf/cs/0507027), established by Theorem 3.2 and Corollary 4.32. Their definition permits any subset of additional candidates; it imposes no cardinality budget. Their hardness construction has a nonempty electorate.
These hypotheses match the reduction below.
Take an instance of that problem with \(n>0\) voters. Construct
\(\displaystyle X=C\cup D,\qquad Y=C,\qquad x^\star=c.\)
Choose a strict priority order putting every candidate other than \(c\) ahead of \(c\). Fix this same order for every available set.
Aggregate identical complete rankings. If the resulting distinct rankings are \(R_1,\ldots,R_\tau\), with positive multiplicities \(n_1,\ldots,n_\tau\), assign
\(\displaystyle \mu_i=\frac{n_i}{n}.\)
This satisfies every support requirement:
For every \(S\subseteq D\), put \(A=C\cup S\). Let \(v_A(x)\) denote the original number of plurality votes for \(x\). Aggregation preserves the contribution of every ballot, so
\(\displaystyle s_A(x)=\frac{v_A(x)}{n}\qquad(x\in A).\)
Therefore the two elections have exactly the same score comparisons and ties.
Because \(c\) has lowest priority, it is selected on \(A\) if and only if it is the unique score maximizer:
Consequently,
\(\displaystyle \exists S\subseteq D:\ c\text{ is not the unique original plurality winner on }C\cup S\)
is equivalent to
\(\displaystyle \exists A,\ Y\subseteq A\subseteq X:\ x^\star\text{ is not selected on }A.\)
This is precisely nonrobustness.
The transformation is polynomial in the original input length. For example, sorting the explicit ballots lexicographically and counting equal ballots takes polynomial time. Its output length is
\(\displaystyle \mathrm{O}\!\left(\tau m\log(m+1)+\tau\log(n+1)+m\log(m+1)\right).\)
In particular, the reduction never enumerates all possible rankings.
Section 3 gives a polynomial-time many-one reduction from an \(\mathrm{NP}\)-complete problem to nonrobustness. Section 1 proves nonrobustness is in \(\mathrm{NP}\). Hence nonrobustness is \(\mathrm{NP}\)-complete, and taking complements proves that robustness is \(\mathrm{coNP}\)-complete.
An explicit deterministic algorithm precomputes the integer weights and checks every subset of \(X\setminus Y\). Its running time is
\(\displaystyle \mathrm{O}\!\left(L+\tau L^2+2^{m-|Y|}\bigl[\tau m\log(m+1)+(\tau+m)L\bigr]\right).\)
A polynomial-time algorithm for the general problem would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The argument establishes that robustness is \(\mathrm{coNP}\)-complete under polynomial-time many-one reductions, even when the target has lowest priority. I found no major or minor mathematical issues.
The prover explicitly interprets binary rational masses as fractions with binary-encoded numerators and denominators. This matches the intended formulation.
Since \(x^\star\in Y\), every admissible available set contains the target and is nonempty. Thus every ranking has a well-defined highest available candidate, and plurality always has at least one score maximizer. The strict priority order selects exactly one candidate.
A subset \(S\subseteq X\setminus Y\) is a valid certificate of nonrobustness. Every admissible set arises as \(A=Y\cup S\), so the certificate covers exactly the required existential negation of robustness.
The common denominator \(Q=\prod_{i=1}^{\tau}q_i\) has bit length bounded by the sum of the denominator bit lengths, hence by \(\mathrm{O}(L)\). Each \(q_i\) divides \(Q\), making \(w_i=p_i(Q/q_i)\) an integer.
The normalization hypothesis gives \(\sum_i w_i=Q\). Positivity therefore bounds every individual weight and every candidate’s integer score by \(Q\). Consequently, all relevant integers have \(\mathrm{O}(L)\) bits.
The identity \(W_A(x)=Qs_A(x)\) is correct. Since \(Q>0\), it preserves strict comparisons and equalities, including those used by the priority rule. No numerical approximation is involved.
The stated \(\mathrm{O}(\tau L^2)\) preprocessing bound is a valid conservative bound using elementary integer arithmetic: all products, divisions, and resulting weights involve integers of \(\mathrm{O}(L)\) bits.
Scanning the explicitly listed rankings costs \(\mathrm{O}(\tau m\log(m+1))\) with indexed candidate identifiers. There are at most \(\tau\) score contributions, and initialization, comparisons, and priority selection fit within \(\mathrm{O}((\tau+m)L)\).
The resulting certificate-verification bound is polynomial in the input parameters. Thus nonrobustness belongs to \(\mathrm{NP}\), and robustness belongs to \(\mathrm{coNP}\).
I checked the [Hemaspaandra–Hemaspaandra–Rothe paper](https://arxiv.org/pdf/cs/0507027). Section 3 defines candidate addition without a cardinality budget, with destructive success meaning that the distinguished candidate is no longer the unique winner. It specifies explicitly listed ballots; the preferences are complete and strict. Theorem 3.2 and Corollary 4.32 establish the claimed plurality hardness.
The restriction to nonempty electorates is justified: Construction 4.28, used for that hardness result, includes strictly positive voter groups. Thus the reduction’s assumption \(n>0\) retains an \(\mathrm{NP}\)-hard source family. No unverified budget or winner-model conversion remains.
Setting \(X=C\cup D\), \(Y=C\), and \(x^\star=c\) satisfies the target problem’s candidate-set requirements.
Aggregating identical complete rankings produces distinct support entries with positive multiplicities. Assigning \(\mu_i=n_i/n\) gives positive rational masses summing to one, each with encoding length \(\mathrm{O}(\log(n+1))\). The bound \(\tau\le n\) is correct.
For every subset \(S\subseteq D\) and every \(x\in C\cup S\), the equality \(s_{C\cup S}(x)=v_{C\cup S}(x)/n\) follows directly from aggregation. It holds simultaneously for all available sets because the aggregated rankings remain complete rankings of \(X\).
With \(c\) lowest in the fixed priority order, \(c\) is selected exactly when it is the unique score maximizer. The prover correctly handles strict victory, strict defeat, and a tie at the maximum. This equivalence also covers singleton available sets.
Therefore the source instance admits destructive control exactly when the constructed instance is nonrobust. The construction and output size are polynomial in the explicit source input length; neither step enumerates possible rankings.
The reduction proves \(\mathrm{NP}\)-hardness of nonrobustness. Together with membership, this establishes \(\mathrm{NP}\)-completeness. Taking complements correctly establishes \(\mathrm{coNP}\)-completeness of robustness, preserving the lowest-priority restriction.
The deterministic bound correctly charges weight preprocessing once and election evaluation for each of the \(2^{m-|Y|}\) subsets. It remains valid when \(Y=X\), where precisely one election is checked.
The statement that a polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\) is correct.
Repair feedback: None required. The theorem citation, hypotheses, arithmetic, reduction equivalence, and running-time bounds are verifiable as written.
⟨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.