Answer: Polynomial-time solvable; in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\).
Theorem 6.3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateprovides the case used in Table 1 to show an ex- ample where combining two easy-to-control rules yields a compu- tationally hard case.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), target \(p\), registered mass \(\mu_t\) and eligible unregistered mass \(\nu_t\) on supported ranking types \(t\), and an addition budget \(\kappa\), decide whether there are masses \(x_t\) with \(0\le x_t\le\nu_t\) and \(\sum_t x_t\le\kappa\) such that \(\sum_t(\mu_t+x_t)(s_r(t,p)-s_r(t,c))\ge0\) for every \(c\ne p\) and \(r\in\{2\text{-Approval},1\text{-Veto}\}\). Take \(\mu\), \(\nu\), and \(\kappa\) as binary rational masses on the same registered-population scale.
Given a candidate set \(C\) with \(m=|C|\ge2\), a target \(p\in C\), and strict complete ranking types, consider constructive control by adding divisible voter mass under the fixed rule family \(F=\{2\text{-Approval},1\text{-Veto}\}\).
A society is given by its support: the list of types with positive mass, each with its mass as a binary rational. Here use the union support \(T=\{t:\mu_t+\nu_t>0\}\), with \(\tau=|T|\); absent registered or unregistered masses are zero. The support size is not the number of possible rankings.
Registered masses \(\mu_t\), eligible unregistered masses \(\nu_t\), and the budget \(\kappa\) are nonnegative binary rationals in one common population unit; neither society is required to have total mass one. Let \(L\) be the total input bit length.
For \(r\in F\), let \(s_r(t,c)\) be the standard per-unit scoring-rule score of candidate \(c\) in ranking \(t\). Scores are summed using voter mass; all candidates attaining the maximum are winners, with no tie-breaking.
The decision problem asks whether there exist real masses \(x_t\) satisfying \(0\le x_t\le\nu_t\), \(\sum_{t\in T}x_t\le\kappa\), and \(\sum_{t\in T}(\mu_t+x_t)(s_r(t,p)-s_r(t,c))\ge0\) for every \(c\in C\setminus\{p\}\) and \(r\in F\). The same addition must succeed under both rules.
Is this continuous mass-addition decision problem in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For explicitly listed, unweighted, indivisible voters, constructive control by adding voters under this rule family is \(\mathrm{NP}\)-complete. [Primary source](https://www.ifaamas.org/Proceedings/aamas2014/aamas/p61.pdf)
No result settling exactly the divisible-mass problem above was located in the literature search.
The divisible-mass decision problem is in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\). It is exactly a linear feasibility problem of polynomial encoding length.
For each listed ranking \(t\), let \(\operatorname{pos}_t(c)\) denote candidate \(c\)’s position. The scoring functions are
\(s_{2\text{-Approval}}(t,c)=\mathbf{1}\{\operatorname{pos}_t(c)\le 2\}\),
\(s_{1\text{-Veto}}(t,c)=\mathbf{1}\{\operatorname{pos}_t(c)<m\}\).
These formulas also apply when \(m=2\).
For every \(r\in F\), \(c\ne p\), and \(t\in T\), define
\(d_{r,c,t}=s_r(t,p)-s_r(t,c)\in\{-1,0,1\}\),
and define the registered margin
\(a_{r,c}=\sum_{t\in T}\mu_t d_{r,c,t}\).
All positions and score differences can be computed by scanning the explicitly listed rankings, using polynomial time in \(m,\tau,L\). No enumeration of absent rankings is needed.
Introduce one real variable \(x_t\) for each \(t\in T\). Consider the system
\(0\le x_t\le\nu_t\qquad(t\in T)\),
\(\sum_{t\in T}x_t\le\kappa\),
\(-\sum_{t\in T}d_{r,c,t}x_t\le a_{r,c}\qquad(r\in F,\ c\in C\setminus\{p\})\).
There are \(\tau\) variables and \(2\tau+1+2(m-1)\) inequalities.
To verify equivalence, the first two groups impose exactly eligibility and the addition budget. For each rule and rival, the last inequality is equivalent to
\(a_{r,c}+\sum_{t\in T}d_{r,c,t}x_t =\sum_{t\in T}(\mu_t+x_t)\bigl(s_r(t,p)-s_r(t,c)\bigr)\ge0\).
Thus it holds precisely when \(p\)’s score is at least \(c\)’s score under rule \(r\). Requiring these inequalities for every rival makes \(p\) a winner, including ties. The same variables occur in both rules’ inequalities, so the addition succeeds simultaneously.
Consequently, the original instance is a yes-instance if and only if this linear system is feasible.
If \(\tau=0\), both societies are empty. Choosing no addition gives every candidate score zero under both rules, so the answer is yes. Henceforth assume \(\tau\ge1\).
We must bound numerical encoding length, since the masses can be large binary rationals.
Write every input mass and the budget as a nonnegative integer numerator divided by a positive integer denominator. Let \(D\) be the product of all these denominators, with omitted zero masses assigned denominator one. Because their encodings are part of the input,
\(\log_2 D=O(L)\).
The product \(D\) can therefore be computed by polynomial-time integer arithmetic. Set \(y_t=Dx_t\). The equivalent system becomes
\(0\le y_t\le D\nu_t\),
\(\sum_{t\in T}y_t\le D\kappa\),
\(-\sum_{t\in T}d_{r,c,t}y_t\le Da_{r,c}\).
Every right-hand side is now an integer. In particular,
\(Da_{r,c}=\sum_{t\in T}(D\mu_t)d_{r,c,t}\).
Each scaled input quantity has \(O(L)\) bits: multiplying its numerator by \(D\) increases bit length by at most \(O(L)\). Summing at most \(\tau\) signed quantities increases bit length by at most \(O(\log(\tau+1))\). Hence every right-hand side has
\(O(L+\log(\tau+1))\)
bits. Every matrix entry belongs to \(\{-1,0,1\}\).
The dense encoding of the resulting integer linear system therefore has length at most
\(O\bigl((\tau+m+1)(\tau+L+\log(\tau+1))\bigr)\),
which is polynomial in \(m,\tau,L\). Its construction also takes polynomial time.
Apply the polynomial-time linear programming feasibility theorem:
Given a binary-encoded rational matrix \(A\) and rational vector \(b\), feasibility of \(Az\le b\) over real vectors \(z\) can be decided in time polynomial in the total encoding length.
This is the standard consequence of Khachiyan’s theorem; the reduction to linear-inequality feasibility and its bit-complexity treatment are described in [Nemirovski’s lecture notes, Section 8.4.2](https://www2.isye.gatech.edu/~nemirovs/OPTIII_LectureNotes2020.pdf).
All hypotheses hold here: the system is explicitly listed, all coefficients are integers, and its encoding length is polynomially bounded. The theorem decides exact feasibility, including feasible regions of lower dimension; strict inequalities or a positive interior radius are not required.
By the equivalence established above, its answer is exactly the answer to the divisible-mass control problem. This proves membership in \(\mathrm{P}\).
The cited [AAMAS paper, Theorem 6.3](https://www.ifaamas.org/Proceedings/aamas2014/aamas/p61.pdf), establishes \(\mathrm{NP}\)-completeness for indivisible voters.
In that model, aggregating unweighted voters by ranking requires each \(x_t\) to be an integer. The present problem instead permits every real value between zero and \(\nu_t\). Removing integrality produces exactly the linear system proved tractable above. Thus the indivisible-voter hardness does not establish hardness of the divisible-mass problem.
As usual, membership in \(\mathrm{P}\) means that this problem could be \(\mathrm{NP}\)-hard under polynomial-time many-one reductions only if \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly. Its linear system is exactly equivalent to the continuous decision problem, its encoding has polynomial length, and the stated polynomial-time feasibility theorem applies. I found no major or minor mathematical issues.
Both scoring formulas match the specified rules. When \(m=2\), 2-Approval gives both candidates one point per unit mass, while 1-Veto gives only the first-ranked candidate one point. Thus the formulas remain valid at the smallest permitted candidate count.
Each difference \(d_{r,c,t}\) belongs to \(\{-1,0,1\}\). The registered margin \(a_{r,c}\) correctly includes all registered mass: every type with positive registered mass belongs to the union support \(T\). Types absent from that support contribute zero.
Computing positions and differences from the explicitly listed rankings takes polynomial time. The argument correctly uses the listed support size, without enumerating possible rankings.
The variable bounds and budget inequality reproduce the admissible additions exactly.
The sign in the winner inequalities is correct:
\(-\sum_t d_{r,c,t}x_t\le a_{r,c}\) is equivalent to
\(a_{r,c}+\sum_t d_{r,c,t}x_t\ge0\).
Substituting the definition of \(a_{r,c}\) gives precisely the score-margin constraint in USER_TASK.
Requiring these inequalities for every rival is equivalent to making \(p\) a maximum-score candidate. The non-strict inequalities correctly permit ties. Using the same variables for both rules enforces one simultaneous addition.
Consequently, both directions of the claimed equivalence hold, including for real additions that are not rational.
If \(\tau=0\), the definition of union support and nonnegativity imply that both societies are empty. The empty addition satisfies the nonnegative budget, and all scores are zero. The prover correctly returns yes.
Zero eligible masses, zero registered masses, and a zero budget are all handled by the displayed constraints. No normalization assumption is introduced. The argument also permits arbitrarily large masses represented by binary rationals.
Every denominator is a positive integer, so their product \(D\) is positive. Its logarithm is bounded by the sum of the input denominator bit lengths, hence by \(O(L)\). Computing this product therefore takes polynomial time.
The substitution \(y_t=Dx_t\) is invertible over the reals. Multiplying the original inequalities by the positive number \(D\) preserves their direction and feasibility. The transformed variables remain real; the integer coefficients do not impose integrality on additions.
Because each input denominator divides \(D\), every scaled mass and the scaled budget are integers. The expression for \(Da_{r,c}\) is also correct.
Each scaled input quantity has \(O(L)\) bits. Adding at most \(\tau\) signed terms adds at most \(O(\log(\tau+1))\) bits to the magnitude bound; recording a sign requires only constant overhead. Thus the claimed right-hand-side bound is valid, including for negative margins.
The count of \(\tau\) variables and \(2\tau+1+2(m-1)\) inequalities is correct. All matrix coefficients remain in \(\{-1,0,1\}\).
The stated dense encoding bound accounts for the matrix entries and right-hand sides and is polynomial in \(m,\tau,L\). The ranking scans, integer products, exact divisions, and margin sums operate on polynomially many integers of polynomial bit length. The construction-time claim is therefore justified.
The prover states the required theorem precisely: exact feasibility of an explicitly encoded rational linear inequality system over real variables is decidable in time polynomial in its encoding length.
Its hypotheses hold for the constructed system. Exact feasibility includes lower-dimensional feasible sets, so zero upper bounds, forced equalities, and score ties do not invalidate the application. The cited [lecture notes, Section 8.4.2](https://www2.isye.gatech.edu/~nemirovs/OPTIII_LectureNotes2020.pdf) support the polynomial-time solvability assertion and its bit-complexity treatment.
Combining this theorem with the established equivalence proves the requested membership in \(\mathrm{P}\).
The source attribution is correct: [Theorem 6.3 of the AAMAS paper](https://www.ifaamas.org/Proceedings/aamas2014/aamas/p61.pdf) states NP-completeness for the specified rule family in the indivisible-voter model.
For aggregated unweighted voters, integer additions count selected voters of each ranking. Allowing arbitrary real additions removes that restriction. The prover correctly explains why the discrete hardness theorem does not establish continuous hardness. Its final qualification concerning \(\mathrm{P}=\mathrm{NP}\) is also correct.
No additional clarification or repair is required.
⟨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.