Answer: The divisible-mass problem is polynomial-time solvable, hence belongs to \(\mathrm{P}\).
Theorem 8 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximatePlurality CCAV for bottom orders and weak orders using average is NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), a preferred candidate \(p\), and supported weak-order ballot types \(t\) with registered masses \(\mu_t\) and eligible unregistered masses \(\nu_t\), all binary-rational, decide whether there are additions \(x_t\) with \(0 \le x_t \le \nu_t\) and \(\sum_t x_t \le \kappa\) such that \(p\) wins under average-extension plurality. For a type whose top tied group is \(G_1(t)\), each candidate in that group receives score \(1/|G_1(t)|\), and every other candidate receives zero; the resulting score is \(\sum_t a_t(c)(\mu_t+x_t)\).
Given a finite nonempty candidate set \(C\), let \(m=|C|\) and fix \(p\in C\). Ballot types are weak orders over all candidates; ties express indifference. Each type \(t\) has registered mass \(\mu_t\) and eligible unregistered mass \(\nu_t\), both nonnegative binary rationals.
A society is given by its support: the list of types with positive mass, each with its mass as a binary rational. Here \(\tau=|\{t:\mu_t+\nu_t>0\}|\) is the combined support size, not the number of possible types; omitted masses are zero. Masses are not required to sum to \(1\).
Under average-extension plurality, \(a_t(c)=1/|G_1(t)|\) when \(c\) belongs to the top tied group \(G_1(t)\), and \(a_t(c)=0\) otherwise. All candidates attaining the maximum score are winners.
Given a nonnegative binary-rational addition budget \(\kappa\), decide whether real additions \(x_t\) exist with \(0\le x_t\le\nu_t\), \(\sum_t x_t\le\kappa\), and \(s_x(p)\ge s_x(c)\) for every \(c\in C\), where \(s_x(c)=\sum_t a_t(c)(\mu_t+x_t)\). Additions preserve ballot types and cost one unit per unit of mass. Let \(L\) be the total input bit length; state running times in \(m,\tau,L\), including the binary encoding of \(\kappa\).
Is this continuous constructive control by adding voters problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For finite lists of unweighted voters, constructive control by adding voters under average-extension plurality is \(\mathrm{NP}\)-complete for weak orders, even when only the top group may contain ties ([Fitzsimmons–Hemaspaandra](https://comsoc-community.org/assets/proceedings/comsoc-2016/FitzsimmonsHemaspaandraCOMSOC2016.pdf)). No result settling the exact divisible-mass problem was located in the literature search.
The problem is in \(\mathrm{P}\). More precisely, it reduces to exact feasibility of a rational linear program with at most \(\tau\) variables and \(m+2\tau\) inequalities. Its total encoding length is polynomial in \(m,\tau,L\), including the binary encoding length of \(\kappa\).
The proof uses exactly the stated interpretation: additions are divisible real masses, ballot types are preserved, and making \(p\) a co-winner suffices.
Let \(T=\{t:\mu_t+\nu_t>0\}\), so \(|T|=\tau\), and let \(U=\{t\in T:\nu_t>0\}\). Write \(n=|U|\le\tau\). Only types in \(U\) need addition variables.
For each candidate \(c\), define its registered score by
\[
s_0(c)=\sum_{t\in T}a_t(c)\mu_t.
\]
<!-- -->
Here and below, the displayed formula is equivalently \(s_0(c)=\sum_{t\in T}a_t(c)\mu_t\).
Consider the following system in the real variables \(x_t\), indexed by \(t\in U\):
\( \sum_{t\in U}\bigl(a_t(p)-a_t(c)\bigr)x_t\ge s_0(c)-s_0(p)\).
This is a rational linear feasibility problem with \(n\) variables and \(2n+1+(m-1)=m+2n\) inequalities.
Equivalence. Any permitted addition vector satisfies the first two sets of inequalities. For each opponent \(c\), the score difference is
\(s_x(p)-s_x(c)=s_0(p)-s_0(c)+\sum_{t\in U}\bigl(a_t(p)-a_t(c)\bigr)x_t.\)
Thus the corresponding winner inequality holds exactly when \(s_x(p)\ge s_x(c)\).
Conversely, a feasible solution supplies permitted additions to the types in \(U\); assign zero additions to every other type. The same identity proves that \(p\) is a winner. Hence the control instance is a yes-instance if and only if this linear system is feasible.
If \(n=0\), simply compare the registered scores. In particular, when \(\tau=0\), all scores are zero and the answer is yes. When \(m=1\), zero additions always suffice.
The number of variables alone does not establish polynomial time: the coefficients and registered-score differences must also have polynomial encoding length.
For each \(t\in T\), write \(k_t=|G_1(t)|\), so \(1\le k_t\le m\). Write the input rationals as
\(\mu_t=u_t/q_t,\qquad \nu_t=v_t/r_t,\qquad \kappa=h/q_\kappa,\)
where the numerators are nonnegative integers and the denominators are positive integers. An omitted zero mass can be represented as \(0/1\).
Define the positive integer
\(D=q_\kappa\prod_{t\in T}q_t r_t k_t.\)
Set
\(B=L+\tau\lceil\log_2(m+1)\rceil.\)
The total binary length of the input denominators is at most \(L\), and each \(k_t\) contributes at most \(\lceil\log_2(m+1)\rceil\) bits to the logarithm of this product. Consequently, \(D\) has \(O(B)\) bits.
Multiply every inequality by \(D\). All resulting coefficients and right-hand sides are integers:
\(D\bigl(s_0(c)-s_0(p)\bigr)=\sum_{t\in T}\bigl(\mathbf{1}_{c\in G_1(t)}-\mathbf{1}_{p\in G_1(t)}\bigr)u_tD/(q_tk_t)\).
For the last assertion, \(q_tk_t\) divides \(D\) by construction.
Every input numerator has at most \(L\) bits. Therefore each summand in the last expression has \(O(B+L)\) bits. Summing at most \(\tau\) signed integers adds at most \(O(\log(\tau+1))\) bits. Since the support is explicitly listed, \(\tau=O(L)\), and every integer in the scaled system has \(O(B)\) bits.
A dense encoding of its coefficient matrix and right-hand side consequently has length
\(S=O\bigl((m+\tau+1)(\tau+1)B\bigr).\)
The top groups, the integer \(D\), and all entries of this system can be computed using polynomially many operations on integers of polynomial bit length. Thus the reduction itself runs in polynomial time.
Crucially, only the listed support types are used. The number of possible weak orders plays no role.
We use the standard polynomial-time linear programming theorem:
Exact LP feasibility theorem. Given an explicitly encoded finite system of linear inequalities with rational coefficients, whether it has a real solution can be decided deterministically in time polynomial in its total binary encoding length.
This theorem covers infeasible systems and feasible systems of lower dimension; it does not require a strictly feasible point. The integer-data formulation and polynomial bit-complexity guarantee are stated in [MIT’s notes on the ellipsoid method](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf).
Its hypotheses hold here: the scaled system is explicit, finite, and has integer coefficients of polynomial encoding length. Applying the theorem and the equivalence proved above gives a deterministic decision algorithm with running time
\(\bigl((m+\tau+1)(\tau+1)(L+\tau\lceil\log_2(m+1)\rceil)\bigr)^{O(1)}.\)
In particular, this is \((m+\tau+L)^{O(1)}\) bit operations and is polynomial in the stipulated explicit input length. The budget contributes through its binary encoding length inside \(L\), so the bound holds even when its numerical value is exponentially large.
The finite-voter problem requires integral selection counts, whereas the present problem permits real additions. The cited discrete hardness theorem therefore concerns a different feasible set. See [Fitzsimmons–Hemaspaandra, Theorem 8](https://comsoc-community.org/assets/proceedings/comsoc-2016/FitzsimmonsHemaspaandraCOMSOC2016.pdf).
The distinction already changes the answer on a small instance consisting entirely of unweighted voters.
Let \(C=\{p,a,b,c,d,e\}\). Take five registered voters:
Take three eligible voters, with top groups \(\{p,a\}\), \(\{p,b\}\), and \(\{p,c\}\), respectively. All remaining candidates can be ordered strictly below the indicated top groups. Set \(\kappa=1\).
Initially,
\(s_0(p)=s_0(d)=s_0(e)=2/3,\qquad s_0(a)=s_0(b)=s_0(c)=1.\)
Adding mass \(1/3\) of each eligible type costs exactly \(1\) and produces
\(s_x(p)=2/3+3(1/6)=7/6,\qquad s_x(a)=s_x(b)=s_x(c)=1+1/6=7/6.\)
The scores of \(d,e\) remain \(2/3\), so \(p\) wins.
With whole voters and budget \(1\), adding no voter leaves \(p\) behind. Adding any one eligible voter gives \(p\) score \(7/6\), while the opponent sharing that voter’s top group has score \(3/2\). Hence no whole-voter addition succeeds.
The continuous problem is therefore polynomial-time solvable despite the discrete problem’s hardness. As usual, membership in \(\mathrm{P}\) implies that it cannot be \(\mathrm{NP}\)-hard under polynomial-time many-one reductions unless \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly: the divisible-mass problem belongs to \(\mathrm{P}\). The LP equivalence, encoding bounds, theorem application, and illustrative example all withstand verification. No major or minor mathematical issues were found.
The definitions \(T=\{t:\mu_t+\nu_t>0\}\) and \(U=\{t\in T:\nu_t>0\}\) correctly use the combined support specified in the task.
Restricting variables to \(U\) loses no permitted additions: for every other type, the upper bound \(x_t\le\nu_t=0\), together with nonnegativity, forces \(x_t=0\). Thus \(n=|U|\le\tau\), and the argument never enumerates all possible weak orders.
The proof uses the required co-winner interpretation and permits arbitrary real additions within the stated bounds.
The registered scores \(s_0(c)=\sum_{t\in T}a_t(c)\mu_t\) correctly include every registered contribution.
For each opponent \(c\), the score identity
\(s_x(p)-s_x(c)=s_0(p)-s_0(c)+\sum_{t\in U}(a_t(p)-a_t(c))x_t\)
follows directly from the given scoring rule. Rearranging it yields exactly the prover’s winner inequality, with the correct sign on its right-hand side.
Both directions of the equivalence are established:
The comparison against \(p\) itself is tautological, so omitting it is valid. The constraint count is correct: \(2n\) capacity inequalities, one budget inequality, and \(m-1\) opponent inequalities, totaling \(m+2n\).
All stated boundary cases are handled correctly.
No normalization of total mass is assumed or needed.
Every top group is nonempty, so \(1\le k_t\le m\). The integer
\(D=q_\kappa\prod_{t\in T}q_t r_t k_t\)
is positive.
Its construction ensures that \(q_\kappa\), every \(r_t\), and every product \(q_tk_t\) divide \(D\). Consequently, multiplying each inequality by \(D\) preserves feasibility and produces integer coefficients and right-hand sides.
The registered-score calculation is correct:
\(D(s_0(c)-s_0(p))=\sum_{t\in T}(\mathbf{1}_{c\in G_1(t)}-\mathbf{1}_{p\in G_1(t)})u_tD/(q_tk_t)\).
The bit-length estimates also hold:
This verifies the claimed bound for all scaled entries, including capacity bounds and the budget. The dense encoding estimate
\(S=O((m+\tau+1)(\tau+1)B)\)
is a valid upper bound. Computing the entries requires only polynomially many integer operations on numbers of polynomial bit length.
The prover states the required theorem precisely: feasibility of an explicitly encoded rational system of linear inequalities over real variables is decidable deterministically in polynomial time in its binary encoding length.
The cited notes discuss arbitrary polyhedra, the treatment of lower dimensional feasible sets, and polynomial precision before stating polynomial-time feasibility for integer data. Thus the citation supports the theorem application without an additional strict-feasibility assumption. [MIT ellipsoid-method notes, slides 25–28](https://ocw.mit.edu/courses/6-251j-introduction-to-mathematical-programming-fall-2009/e13f5e6650f7be1e21101a2e7bd0d5b8_MIT6_251JF09_lec18.pdf).
The constructed system satisfies the theorem’s hypotheses. Combining its encoding bound with polynomial-time feasibility gives the displayed running time and its simplification to \((m+\tau+L)^{O(1)}\) bit operations.
Under the stipulated explicit encoding, this is polynomial in input length. The numerical value of \(\kappa\) does not enter the bound; its binary encoding does.
The cited Theorem 8 concerns whole-voter additions under average plurality for bottom orders, and therefore also weak orders. It matches the discrete result described by the prover. [Fitzsimmons–Hemaspaandra, Theorem 8](https://comsoc-community.org/assets/proceedings/comsoc-2016/FitzsimmonsHemaspaandraCOMSOC2016.pdf).
The example’s computations are correct:
The example therefore establishes the claimed difference between the two feasible sets. The final qualification concerning NP-hardness unless \(\mathrm{P}=\mathrm{NP}\) is correct.
No additional lemma, 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.