Answer: Both addition and deletion are polynomial-time solvable, with bit running time \((m+\tau+L)^{O(1)}\), using exact linear programs with \(\tau+1\) variables and \(m+2\tau+3\) inequalities.
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateCAV-ALL and CDV-ALL are NP-hard even for Unconditional Minisum and for binary domain in each issue.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) binary issues, a current mass profile \(\mu_t\) over unconditional approval-ballot types, a target outcome \(p\), and quota \(q\), decide whether \(p\) can be made the unique Minisum optimum by adding available mass \(y_t\) with \(0\le y_t\le\nu_t\) and \(\sum_t y_t\le q\), or by deleting mass \(x_t\) with \(0\le x_t\le\mu_t\) and \(\sum_t x_t\le q\). For the resulting profile \(\lambda=\mu+y\) or \(\lambda=\mu-x\), the requirement is that \(S_\lambda(p)<S_\lambda(s)\) for every \(s\ne p\), where \(S_\lambda(s)=\sum_t\lambda_t\delta_t(s)\).
Let \(m\ge 1\) binary issues have outcome space \(\{0,1\}^m\). An unconditional ballot type \(t\) specifies an approval set \(A_{t,j}\subseteq\{0,1\}\) for every issue \(j\); empty sets and approval of both values are allowed. Define \(\delta_t(s)=|\{j:s_j\notin A_{t,j}\}|\) and \(S_\lambda(s)=\sum_t\lambda_t\delta_t(s)\).
A society is given by its support: the list of types with positive mass, each mass a binary rational. The parameter \(\tau\) counts supported types, not possible types; for addition, use the union of the current and available supports. Masses are finite nonnegative measures, without normalization. The current society \(\mu\) has positive total mass. Let \(L\) be the total binary input length.
The input includes a target \(p\in\{0,1\}^m\) and a nonnegative binary rational quota \(q\). Consider two separate decision problems. Addition also receives available masses \(\nu\) and permits real masses \(0\le y_t\le\nu_t\), with \(\sum_t y_t\le q\), producing \(\lambda=\mu+y\). Deletion permits real masses \(0\le x_t\le\mu_t\), with \(\sum_t x_t\le q\), producing \(\lambda=\mu-x\). Unlisted masses are zero.
In either problem, a permitted change succeeds exactly when \(S_\lambda(p)<S_\lambda(s)\) for every \(s\in\{0,1\}^m\setminus\{p\}\); ties do not count as success.
For each of these two mass-control problems, is it solvable in polynomial time or is it NP-hard? State running times in \(m\), \(\tau\), and \(L\).
For finite lists of indivisible voters, both addition and deletion control requiring a unique prescribed outcome are NP-hard even with unconditional ballots and binary issues ([Markakis–Papasotiropoulos](https://arxiv.org/pdf/2202.01660)). No result settling exactly these divisible-mass variants was located in the literature search.
Both addition and deletion with divisible masses are polynomial-time solvable. Each reduces to an exact rational linear program with \(\tau+1\) variables and \(m+2\tau+3\) inequalities. The bit running time is \((m+\tau+L)^{O(1)}\).
The proof handles arbitrary real changes, strict uniqueness, empty approval sets, approval of both values, and deletion of the entire society.
For each supported type \(t\) and issue \(j\), define
\(d_{t,j}=\mathbf{1}\{1-p_j\notin A_{t,j}\}-\mathbf{1}\{p_j\notin A_{t,j}\}\).
Thus \(d_{t,j}\in\{-1,0,1\}\). More explicitly:
| Approval set \(A_{t,j}\) | \(d_{t,j}\) |
|---|---:|
| \(\{p_j\}\) | \(1\) |
| \(\{1-p_j\}\) | \(-1\) |
| \(\varnothing\) or \(\{0,1\}\) | \(0\) |
For a nonnegative measure \(\lambda\), define its margin on issue \(j\) by
\(g_j(\lambda)=\sum_t\lambda_t d_{t,j}\).
Lemma. The prescribed outcome \(p\) is the unique minimizer of \(S_\lambda\) if and only if \(g_j(\lambda)>0\) for every issue \(j\).
Proof. For any outcome \(s\), let \(J(s)=\{j:s_j\ne p_j\}\). Because issues are binary, \(s_j=1-p_j\) for every \(j\in J(s)\). Expanding the dissatisfaction scores and cancelling the unchanged coordinates gives
\(S_\lambda(s)-S_\lambda(p)=\sum_{j\in J(s)}\sum_t\lambda_t d_{t,j}=\sum_{j\in J(s)}g_j(\lambda)\).
If every margin is positive, this sum is positive whenever \(s\ne p\), since then \(J(s)\) is nonempty.
Conversely, for any issue \(j\), consider the outcome obtained by flipping only coordinate \(j\) of \(p\). Its score difference from \(p\) is exactly \(g_j(\lambda)\). Unique optimality therefore requires \(g_j(\lambda)>0\). This proves both directions.
Let \(T\) be the union of the current and available supports for addition, and the current support for deletion. In each case \(|T|=\tau\), and unlisted masses are zero.
Define
\(b_j=\sum_{t\in T}\mu_t d_{t,j}\)
and
\(M=\sum_{t\in T}\mu_t>0\).
Since \(d_{t,j}\ge -1\) and \(\mu_t\ge0\), we have \(b_j\ge-M\).
Use real variables \(y_t\), for \(t\in T\), and a real margin variable \(\epsilon\). Maximize \(\epsilon\) subject to:
Denote its optimal value by \(\epsilon_{\mathrm{add}}^*\).
Use real variables \(x_t\), for \(t\in T\), and a real margin variable \(\epsilon\). Maximize \(\epsilon\) subject to:
Denote its optimal value by \(\epsilon_{\mathrm{del}}^*\).
Both programs are feasible: choose zero change and \(\epsilon=-M\). Both feasible regions are closed and bounded, because all change variables have finite bounds and \(\epsilon\in[-M,1]\). Consequently, both maxima are attained.
Proposition. Addition succeeds exactly when \(\epsilon_{\mathrm{add}}^*>0\), and deletion succeeds exactly when \(\epsilon_{\mathrm{del}}^*>0\).
Proof. For either operation, suppose a permitted change succeeds and produces \(\lambda\). By the lemma, all \(m\) margins are positive. Since \(m\) is finite and positive,
\(\eta=\min_{1\le j\le m}g_j(\lambda)>0\).
The change, together with \(\epsilon=\min\{1,\eta\}\), is feasible for its linear program. Thus its optimal value is positive.
Conversely, an optimal solution with \(\epsilon^*>0\) gives a permitted change whose resulting margins satisfy \(g_j(\lambda)\ge\epsilon^*>0\) for every issue. The lemma implies that \(p\) is the unique minimizer.
In particular, an optimal value of zero is rejected: ties do not count as success. Deleting all mass cannot create a false positive, since the zero measure has every margin equal to zero.
We use the standard rational linear-programming theorem: a linear program with rational data can be solved exactly in time polynomial in its binary encoding length; when a finite optimum exists, an optimal rational solution and its value can be returned. This is the polynomial-time solvability theorem for linear programming originating with [Khachiyan](https://www.mathnet.ru/eng/dan42319).
Its hypotheses hold here:
The exact rational optimum can therefore be compared with zero without a numerical tolerance.
The table \(d_{t,j}\) requires \(O(m\tau)\) ballot inspections. Computing the \(b_j\) requires \(O(m\tau)\) rational arithmetic operations, and computing \(M\) requires \(O(\tau)\).
For completeness, the constructed rational numbers have polynomial encoding length. Write the current masses as \(\mu_t=a_t/c_t\), with integer numerators and positive integer denominators. A common denominator is \(D_\mu=\prod_t c_t\). Its bit length is \(O(L)\), and
\(D_\mu b_j=\sum_t d_{t,j}a_t(D_\mu/c_t)\).
Each summand has \(O(L)\) bits, and adding at most \(\tau\) summands produces an integer with \(O(L+\log(\tau+1))\) bits. The same argument applies to \(M\).
Thus, even using a dense matrix representation, the LP encoding length is
\(B=O\bigl((m+\tau+1)(\tau+L+\log(\tau+1))\bigr)\).
Exact rational LP optimization consequently gives, for each problem, bit running time
\((m+\tau+L)^{O(1)}\).
A stronger arithmetic bound is also available. Every constraint-matrix entry belongs to \(\{-1,0,1\}\). [Tardos’s algorithm](https://pubsonline.informs.org/doi/10.1287/opre.34.2.250) therefore gives \((m+\tau)^{O(1)}\) arithmetic operations, independent of the magnitudes of the masses and quota, with polynomially bounded intermediate encoding lengths. If integer right-hand sides are required, multiply all right-hand sides and scale all variables by the product of the input denominators; this leaves the constraint matrix unchanged and preserves the sign of the optimal margin.
The finite-voter hardness results concern indivisible choices; see Theorems 8 and 9 of [Markakis–Papasotiropoulos](https://arxiv.org/pdf/2202.01660). Here every amount within its allowed interval is permitted, so the linear programs describe the admissible changes exactly. No integrality restriction remains.
⟨structured verdict parsed — rendered above⟩
The prover’s output correctly resolves both problems: addition and deletion with divisible masses are polynomial-time solvable. The reduction, treatment of strict uniqueness, and binary encoding bounds are sound. I found no major or minor mathematical issues.
The sign of \(d_{t,j}\) agrees with the dissatisfaction difference between choosing \(1-p_j\) and choosing \(p_j\). All four possible approval sets are covered correctly. In particular, empty approval sets contribute equally to both choices, while approval of both values contributes zero dissatisfaction to both; either case gives \(d_{t,j}=0\).
The sums use precisely the relevant finite support. No enumeration of all possible ballot types is required.
The displayed identity
\[
S_\lambda(s)-S_\lambda(p)=\sum_{j\in J(s)}g_j(\lambda)
\]
follows directly from the additive definition of dissatisfaction and the binary outcome domain. Unchanged coordinates cancel, and every changed coordinate takes the complementary value.
If every margin is positive, every competing outcome has a strictly larger score because its set of changed coordinates is nonempty. Conversely, uniqueness must hold against each outcome differing from \(p\) in exactly one coordinate, forcing every individual margin to be positive. This checks the full quantifier over competing outcomes.
For addition, the bounds and quota are exactly the prescribed restrictions on \(y\), and the margin expression is \(g_j(\mu+y)\). Types supported only by the current society have available mass zero, so their addition variables are correctly forced to zero.
For deletion, the bounds ensure that \(\mu-x\) remains nonnegative, the quota is correct, and the margin expression is \(g_j(\mu-x)\).
Each program has \(\tau+1\) variables and
\[
2\tau+1+m+2=m+2\tau+3
\]
inequalities, as claimed. The definition of \(\tau\) agrees with the task for each operation.
The inequality \(b_j\ge -M\) follows from \(d_{t,j}\ge -1\) and nonnegative current masses. Thus zero change with \(\epsilon=-M\) satisfies every margin constraint. It also satisfies the quota because \(q\ge0\), and satisfies the upper margin bound because \(M>0\).
All variables have finite bounds. The feasible regions are nonempty, closed, and bounded, and the objective is continuous; therefore both optima are finite and attained.
The upper bound \(\epsilon\le1\) does not obstruct detecting success: the prover explicitly caps any positive achievable minimum margin at \(1\). The lower bound likewise does not exclude that positive witness.
A successful real-valued change has finitely many strictly positive issue margins. Since \(m\ge1\), their minimum exists and is positive. The prover’s choice \(\epsilon=\min\{1,\eta\}\) satisfies every auxiliary bound and margin constraint.
Conversely, an attained positive optimum supplies a permitted change with every margin strictly positive, so the lemma applies. No assumption that permitted changes are rational is introduced.
Rejecting an optimum of zero is correct. Complete deletion produces zero margins and therefore cannot satisfy strict uniqueness. Zero quota and empty available support also cause no failure in the argument.
The prover states the relevant rational linear-programming theorem sufficiently precisely: rational input admits polynomial-time exact optimization, including an exact rational optimal value when a finite optimum exists. The programs satisfy all stated hypotheses. The attribution to [Khachiyan’s polynomial-time linear-programming result](https://www.mathnet.ru/eng/dan42319) is appropriate.
The common-denominator calculation is correct. The product of the current-mass denominators has bit length \(O(L)\); the scaled summands have \(O(L)\) bits; summing at most \(\tau\) terms increases the bound by at most \(O(\log(\tau+1))\). This applies to both \(b_j\) and \(M\), including signed margins and zero unlisted masses.
The dense coefficient matrix has \(O((m+\tau+1)(\tau+1))\) entries of constant encoding length. The right-hand sides have the polynomial encoding lengths established in the output. Consequently, the stated bound
\[
B=O\bigl((m+\tau+1)(\tau+L+\log(\tau+1))\bigr)
\]
is valid, and exact optimization yields bit running time \((m+\tau+L)^{O(1)}\). Comparing the exact optimum with zero correctly avoids any numerical-tolerance assumption.
Every constraint-matrix entry is indeed in \(\{-1,0,1\}\). This satisfies the small-integer-matrix condition underlying the stated application of [Tardos’s algorithm](https://pubsonline.informs.org/doi/10.1287/opre.34.2.250), whose arithmetic-operation bound is independent of the right-hand-side and objective magnitudes. The intermediate encoding bound is understood relative to the full input length.
The suggested simultaneous scaling of variables and right-hand sides preserves the matrix and multiplies the optimal margin by a positive denominator product, preserving its sign.
The references to Theorems 8 and 9 are accurate: they concern deletion and addition of indivisible voters, respectively, with a unique prescribed outcome, unconditional ballots, and binary issues. Those results do not contradict the divisible-mass classification. [Markakis–Papasotiropoulos](https://arxiv.org/pdf/2202.01660)
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.