Answer: Polynomial-time solvable under both conventions, in \(\operatorname{poly}(L)+t\,\operatorname{poly}(m+\tau+L)\) time.
Theorem 8 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateCB for majority judgment is NP-hard, even when there are only two grades. PROOF. Let I = (H = {c1, c2, ..., c3κ}, S = {s1, s2, ..., s3κ}) be an instance of X3C. We create an instance EI = (C, G, , V, p ∈ C, k = κ) as follows. Candidates. For each ci ∈H, we create a candidate.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite candidate set \(C\), an ordered finite grade set \(G\), a target \(p\in C\), a rational distribution \(\mu\) over supported complete grade vectors \(r\in G^C\), a budget \(\beta\in[0,1]\), and a unique-winner or co-winner convention, is there a nonnegative mass transfer \(x_{r,s}\) from supported input types \(r\) to output vectors \(s\in G^C\), with \(\sum_s x_{r,s}\le\mu_r\) for every \(r\) and \(\sum_{r\ne s}x_{r,s}\le\beta\), such that \(p\) wins? Define candidate \(c\)'s majority grade as the least \(g\in G\) for which \(\sum_{r:r(c)\preceq g}\mu'_r\ge\tfrac12\), where \(\mu'\) is the resulting distribution.
Let \(C\) be a nonempty finite candidate set, \(m=|C|\), and let \(G\) be an explicitly listed nonempty finite grade set with a strict linear order \(\prec\), higher being better; write \(t=|G|\).
A society is given by its support \(R\subseteq G^C\): the list of the \(\tau=|R|\) complete grade vectors with positive binary-rational masses \(\mu_r\), summing to \(1\). Here \(\tau\) is the support size, not the number \(t^m\) of possible types.
The input also specifies \(p\in C\), a binary-rational budget \(\beta\in[0,1]\), and either the unique-winner or co-winner convention. Let \(L\) be the total input bit length; state running times in \(m,\tau,t,L\).
An admissible change consists of real masses \(x_{r,s}\ge0\), indexed by \(r\in R\) and \(s\in G^C\), satisfying \(\sum_s x_{r,s}\le\mu_r\) and \(\sum_{r\in R}\sum_{s\ne r}x_{r,s}\le\beta\). Changing a complete vector costs its changed mass, regardless of how many candidate grades change; output vectors need not belong to \(R\).
Extend \(\mu\) by zero outside \(R\). The resulting distribution is \(\mu'_u=\mu_u-\mathbf{1}_{u\in R}\sum_s x_{u,s}+\sum_{r\in R}x_{r,u}\) for \(u\in G^C\).
For any distribution \(\nu\), define \(M_c(\nu)=\min_{\prec}\{g\in G:\sum_{u:u(c)\preceq g}\nu_u\ge\tfrac12\}\). Winners have the highest majority grade, with no further tie-breaking: success means \(M_p(\mu')\succ M_c(\mu')\) for every \(c\ne p\) in the unique-winner convention, and \(M_p(\mu')\succeq M_c(\mu')\) in the co-winner convention. Promise that \(p\) initially fails the selected success condition.
Is deciding whether an admissible change makes \(p\) successful polynomial-time solvable, or NP-hard, under each winner convention?
Discrete constructive bribery, charging one unit per changed complete vote, is NP-hard even with two grades, under both winner conventions ([Yang, 2017](https://www.ifaamas.org/Proceedings/aamas2017/pdfs/p1169.pdf)). No result settling this exact mass-transfer problem was located.
The decision problem is polynomial-time solvable under both the unique-winner and the co-winner convention.
The algorithm solves at most \(t\) rational linear programs, each with at most \(\tau\) variables and \(2\tau+m\) constraints. Its running time is
\( \operatorname{poly}(L)+t\,\operatorname{poly}(m+\tau+L) \).
In particular, it never enumerates the \(t^m\) possible output vectors.
List the grades as \(g_1\prec\cdots\prec g_t\). Define the complete vector \(w\) by
\(w(p)=g_t\) and \(w(c)=g_1\) for every \(c\ne p\).
Lemma. Every admissible change can be replaced by an admissible change of no greater cost that sends all changed mass to \(w\). If the original change makes \(p\) successful, the replacement does too, under either convention.
Proof. Consider an admissible change \(x\), producing distribution \(\nu\). Transfers \(x_{r,r}\) cancel in the resulting distribution and incur no cost, so discard them. Write
\(q_r=\sum_{s\ne r}x_{r,s}\).
Then \(0\le q_r\le\mu_r\), and
\[
\]
\( \displaystyle
\nu=\sum_{r\in R}(\mu_r-q_r)\delta_r
+\sum_{r\in R}\sum_{s\ne r}x_{r,s}\delta_s,
\)
where \(\delta_u\) denotes unit mass at vector \(u\).
Replace every destination by \(w\), obtaining
\( \displaystyle
\eta=\sum_{r\in R}(\mu_r-q_r)\delta_r
+\left(\sum_{r\in R}q_r\right)\delta_w.
\)
This distribution is implemented by transferring \(q_r\) from \(r\) to \(w\) for each \(r\ne w\). If \(w\in R\), its term in the displayed expression is simply \(\mu_w\delta_w\), so no transfer from \(w\) is necessary. The replacement therefore costs
\( \sum_{r\in R,\ r\ne w}q_r\le\sum_r q_r\le\beta \).
For a candidate \(c\) and grade \(h\), define its cumulative mass by
\(F_c^\rho(h)=\sum_{u:u(c)\preceq h}\rho_u\).
Direct subtraction gives
\( \displaystyle
F_c^\eta(h)-F_c^\nu(h)
=\sum_{r\in R}\sum_{s\ne r}x_{r,s}
\left(\mathbf 1_{w(c)\preceq h}-\mathbf 1_{s(c)\preceq h}\right).
\)
For \(p\), every summand is nonpositive because \(w(p)\) is the highest grade. For a rival, every summand is nonnegative because \(w(c)\) is the lowest grade. Consequently,
\(F_p^\eta(h)\le F_p^\nu(h)\) and
\(F_c^\eta(h)\ge F_c^\nu(h)\) for every rival \(c\).
For every grade below \(M_p(\nu)\), the cumulative mass for \(p\) under \(\nu\) is strictly below \(\tfrac12\); it remains so under \(\eta\). Hence \(M_p(\eta)\succeq M_p(\nu)\).
At \(h=M_c(\nu)\), the rival’s cumulative mass under \(\eta\) is at least \(\tfrac12\), so \(M_c(\eta)\preceq M_c(\nu)\).
Both success conditions are therefore preserved. \(\square\)
Let \(S=R\setminus\{w\}\). By the lemma, it suffices to choose masses \(y_r\), indexed by \(r\in S\), satisfying
\( \displaystyle
0\le y_r\le\mu_r,\qquad
\sum_{r\in S}y_r\le\beta.
\)
Transfer \(y_r\) from \(r\) to \(w\), and denote the resulting distribution by \(\nu_y\).
Define the initial cumulative masses
\( \displaystyle
A_{c,j}=\sum_{r\in R:r(c)\preceq g_j}\mu_r
\quad(1\le j\le t),
\)
and set \(A_{c,0}=0\).
For each \(1\le i\le t\), define
\( \displaystyle
B_i(y)=\sum_{r\in S:r(p)\prec g_i}y_r.
\)
In particular, \(B_1(y)=0\).
For \(i\ge2\), the destination gives \(p\) a grade strictly above \(g_{i-1}\), so
\( \displaystyle
F_p^{\nu_y}(g_{i-1})=A_{p,i-1}-B_i(y).
\)
By the definition of the lower median,
\( \displaystyle
M_p(\nu_y)\succeq g_i
\quad\Longleftrightarrow\quad
B_i(y)>A_{p,i-1}-\tfrac12.
\)
This equivalence also holds for \(i=1\): the left side is automatic, and the right side reads \(0>-\tfrac12\).
For every rival \(c\) and \(1\le k\le t\), changing a portion already graded at most \(g_k\) leaves its cumulative contribution unchanged. Changing a portion graded above \(g_k\) adds that portion to the cumulative mass. Thus
\( \displaystyle
F_c^{\nu_y}(g_k)
=A_{c,k}+\sum_{r\in S:r(c)\succ g_k}y_r.
\)
Consequently,
\( \displaystyle
M_c(\nu_y)\preceq g_k
\quad\Longleftrightarrow\quad
A_{c,k}+\sum_{r\in S:r(c)\succ g_k}y_r\ge\tfrac12.
\)
These equivalences retain the strict inequality required for raising \(p\)’s lower median.
If \(m=1\), \(p\) is already successful under either convention. Such an instance cannot satisfy the initial-failure promise. Hence assume \(m\ge2\).
For the co-winner convention, consider every \(i\in\{1,\ldots,t\}\) and put \(k=i\).
For the unique-winner convention, consider every \(i\in\{2,\ldots,t\}\) and put \(k=i-1\). The lowest grade cannot be the majority grade of a unique winner when a rival exists.
For each considered pair \((i,k)\), solve the following ordinary, closed linear program:
\( \displaystyle \text{maximize } B_i(y) \)
subject to
\( \displaystyle 0\le y_r\le\mu_r\quad(r\in S), \)
\( \displaystyle \sum_{r\in S}y_r\le\beta, \)
\( \displaystyle A_{c,k}+\sum_{r\in S:r(c)\succ g_k}y_r \ge\tfrac12 \quad(c\ne p). \)
If it is infeasible, discard this pair. Otherwise, let its optimal value be \(z_i\). Accept the instance exactly when some considered pair satisfies
\( \displaystyle z_i>A_{p,i-1}-\tfrac12. \)
The feasible region is closed and bounded by the coordinate bounds. Whenever it is nonempty, the maximum is attained. Therefore the strict comparison is equivalent to the existence of a feasible mass transfer with the required strict median inequality.
Suppose a pair passes the test, and take an optimal feasible solution \(y\).
Section 2 gives \(M_p(\nu_y)\succeq g_i\) and \(M_c(\nu_y)\preceq g_k\) for every rival.
For co-winners, \(k=i\), so \(p\)’s majority grade is at least every rival’s.
For unique winners, \(k=i-1\), so
\(M_p(\nu_y)\succeq g_i\succ g_{i-1}\succeq M_c(\nu_y)\).
The constructed transfer is admissible and successful.
Suppose some admissible change succeeds. By Section 1, there is a successful change using only destination \(w\), represented by a feasible vector \(y\).
Write \(M_p(\nu_y)=g_i\).
Under the co-winner convention, every rival has majority grade at most \(g_i\). Thus \(y\) satisfies the program with \(k=i\).
Under the unique-winner convention, necessarily \(i\ge2\), and every rival has majority grade at most \(g_{i-1}\). Thus \(y\) satisfies the program with \(k=i-1\).
In either case,
\(B_i(y)>A_{p,i-1}-\tfrac12\).
The optimal value is at least \(B_i(y)\), so the corresponding pair passes the test. This proves completeness.
The algorithm uses the standard theorem that rational linear programming admits polynomial-time feasibility testing and exact optimization in the binary encoding length. This includes feasible regions of lower dimension; no interior-point assumption is needed. See [MIT’s notes on polynomial-time linear programming](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html).
All its hypotheses hold here:
A dense encoding of one program therefore has size
\(O((m+\tau)(\tau+L))\).
The cumulative masses can be computed using \(O(m(t+\tau))\) rational additions after identifying grade ranks. Constructing and solving at most \(t\) programs takes
\( \operatorname{poly}(L)+t\,\operatorname{poly}(m+\tau+L) \)
bit operations.
Exact rational comparison handles the strict threshold. Indeed, when feasible, each program has a rational optimal vertex of polynomial encoding length. An accepted program therefore also supplies a rational successful transfer.
Consider two grades \(\ell\prec h\), two candidates \(p,c\), and initial mass \(1\) on the vector \((p:\ell,c:h)\).
Transferring mass \(q\) to \((p:h,c:\ell)\) makes \(p\) a co-winner exactly when \(q\ge\tfrac12\), and a unique winner exactly when \(q>\tfrac12\).
At budget \(\beta=\tfrac12\), both candidates have lower median \(\ell\). Co-winner success is possible, but unique-winner success is impossible. The algorithm distinguishes these cases because it compares the attained optimum strictly with the threshold.
Thus both conventions are settled, including their boundary behavior.
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved: the argument establishes polynomial-time solvability under both winner conventions. I found no mathematical errors, substantive gaps, or necessary clarifications.
Discarding \(x_{r,r}\) preserves the resulting distribution and cost while relaxing the source constraint. The remaining outgoing masses satisfy \(0\le q_r\le\mu_r\) and \(\sum_r q_r\le\beta\).
Both displayed distributions correctly account for retained and transferred mass. When \(w\in R\), retaining its original mass implements the replacement: the subtraction of \(q_w\) and its contribution to the incoming mass at \(w\) cancel. Thus the implementation requires transfers only from \(r\ne w\), respects every source capacity, and costs at most the original change.
The cumulative-mass subtraction formula is correct. Since \(w(p)=g_t\), its indicator is at most the corresponding indicator for every destination \(s\). Since \(w(c)=g_1\) for every rival, its indicator is at least the corresponding indicator for \(s\). These statements hold at every grade, including the endpoints.
The subsequent median comparisons follow directly from the lower-median definition. The replacement cannot lower \(p\)’s majority grade or raise a rival’s. It consequently preserves both strict superiority and weak superiority. The lemma applies to arbitrary real admissible masses and does not assume that destinations belong to the original support.
Every vector \(y\) satisfying the stated capacity and budget constraints implements an admissible transfer to \(w\). Conversely, the lemma ensures that every successful admissible change has a successful representative of this form.
This is the equivalence needed for deciding existence; the proof does not claim that every attainable distribution has this form.
For \(i\ge2\), exactly the transferred mass originally giving \(p\) a grade below \(g_i\) is removed from its cumulative mass at \(g_{i-1}\). Hence
\(F_p^{\nu_y}(g_{i-1})=A_{p,i-1}-B_i(y)\) is correct.
Under the specified lower median, \(M_p(\nu_y)\succeq g_i\) holds exactly when that cumulative mass is strictly below \(\tfrac12\). The resulting strict inequality for \(B_i(y)\) is therefore necessary and sufficient. The separately stated interpretation for \(i=1\) is also correct.
For a rival, transferring mass originally above \(g_k\) adds it to the cumulative mass at \(g_k\); transferring mass already at or below \(g_k\) leaves that contribution unchanged. The rival formula and its non-strict threshold are correct, including \(k=t\).
For co-winner success, a successful distribution with \(M_p=g_i\) has every rival’s majority grade at most \(g_i\), precisely the pair \(k=i\).
For unique-winner success with a rival present, \(i\ge2\), and the strict linear ordering makes “below \(g_i\)” equivalent to “at most \(g_{i-1}\).” Thus \(k=i-1\) captures exactly the necessary rival bounds.
The discussion of \(m=1\) is correct: both success conditions are vacuous, so initial failure is impossible under the promise.
Each feasible region is closed and bounded. A nonempty region therefore has an attained maximum of the stated linear objective. Consequently, the test
\(z_i>A_{p,i-1}-\tfrac12\) is equivalent to the existence of a feasible transfer satisfying the strict condition for \(p\).
Equality correctly results in rejection for that pair. There is no substitution of an unattained supremum for an attainable successful transfer, and no numerical tolerance is assumed.
In soundness, the accepted optimal solution satisfies the budget, source capacities, and rival thresholds. The strict objective comparison supplies the required lower bound on \(p\)’s majority grade. The selected pair then gives the appropriate winner condition.
In completeness, the destination-vector lemma supplies a successful feasible \(y\). Choosing the index of its actual majority grade for \(p\) places it in one of the enumerated programs. Its objective already exceeds the threshold, so that program’s optimum exceeds the threshold as well.
Neither direction assumes that \(p\)’s final majority grade equals the enumerated grade in every feasible solution; the lower bound used in soundness is sufficient.
The invoked theorem concerns polynomial-time feasibility and exact optimization for explicitly encoded rational linear programs. The hypotheses hold: the coefficients are rational, the programs have polynomial encoding length, and every feasible program has a finite attained optimum. Lower-dimensional feasible regions are allowed. The cited [MIT notes](https://courses.csail.mit.edu/6.854/21/Notes/n14-LP_algorithms.html) support polynomial-time rational LP solving and discuss lower-dimensional feasibility and recovery of exact optimal vertices.
With \(n=|S|\), the count \(2n+m\) is correct: there are \(2n\) coordinate inequalities, one budget inequality, and \(m-1\) rival inequalities.
The cumulative sums and derived right-hand sides have \(O(L)\) bits. Summing input rationals does not require exponentially many encoding bits relative to their total input length. The stated dense program-size bound is sufficient.
The preprocessing addition count and at most \(t\) LP solves yield the claimed
\(\operatorname{poly}(L)+t\,\operatorname{poly}(m+\tau+L)\) bit complexity. Because the grades are explicitly listed, this is polynomial in the input length. No enumeration of \(t^m\) vectors occurs.
The claim about polynomial-length rational optimal vertices is applicable to these bounded rational polyhedra. It also justifies the asserted rational successful transfer despite the task permitting arbitrary real masses.
With \(t=1\), co-winner initial failure is impossible. For unique winners with \(m\ge2\), success is impossible, and the algorithm correctly rejects because it considers no pairs.
An empty \(S\) causes no mathematical difficulty: the variable vector is empty and its objective is zero. Zero-variable feasibility is simply evaluation of the constant constraints.
The two-grade example is correct. At transferred mass \(\tfrac12\), both candidates have lower median \(\ell\); above \(\tfrac12\), their lower medians are respectively \(h\) and \(\ell\). The stated co-winner and unique-winner thresholds follow.
No repair feedback is necessary. The polynomial-time classification is established for the exact mass-transfer problem under both conventions.
⟨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.