Answer: \(\mathrm{NP}\)-hard
Theorem 7 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateFlip-Bribery is NP-complete for each of Phragmén, MES-Cost and MES-Apr, even if all projects have the same unit cost. GreedyCost is in P in this case. For GreedyCost, our hardness result requires binary encoding, but works already for a single voter.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a project set \(C\), unit costs, budget \(B\), tie-breaking order, target \(p\), rational approval-set masses \(\mu_S\), and radius \(\rho\), is there a transfer \(x_{S,S'}\geq 0\) with total outflow from \(S\) at most \(\mu_S\), Hamming cost \(\sum_{S,S'}d_H(S,S')x_{S,S'}\leq\rho\), and resulting distribution \(\mu'\) under which MES-Apr funds \(p\)?
Definitions. Let \(C\) contain \(m\geq1\) indivisible projects of cost \(1\), with target \(p\in C\), a fixed strict tie-breaking order, budget \(B\in\mathbb Z_{>0}\), and radius \(\rho\in\mathbb Q_{\geq0}\).
A society is given by its support: the list of the \(\tau\) approval types \(S\subseteq C\) with positive mass, each mass a binary rational, with \(\sum_S\mu_S=1\). Here \(\tau\) is the support size, not \(2^m\); absent types have mass zero. Empty approval sets are allowed. Let \(L\) be the total input bit length, including binary-encoded \(B\).
Transfers are real numbers \(x_{S,T}\geq0\), indexed by \(S,T\subseteq C\), satisfying \(\sum_Tx_{S,T}\leq\mu_S\) and \(\sum_{S,T}|S\triangle T|x_{S,T}\leq\rho\). Set \(\mu'_T=\mu_T-\sum_Ux_{T,U}+\sum_Sx_{S,T}\); destinations may be outside the original support.
Continuous MES-Apr starts with \(W=\varnothing\) and balance per unit mass \(b_T=B\) for each positive-mass resulting type. For each \(c\notin W\), its price is the least finite \(q\geq0\) satisfying \(\sum_{T\ni c}\mu'_T\min\{b_T,q\}=1\), if such a price exists.
Select the project with smallest price, resolving equal prices by the given order; add it to \(W\) and replace \(b_T\) by \(b_T-\min\{b_T,q\}\) for every approving type. Stop when no remaining project has a finite price; apply no completion procedure.
Target. Is deciding whether an admissible transfer makes continuous MES-Apr fund \(p\) solvable in time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
Nearest known results. Discrete MES-Apr approval-flip bribery is \(\mathrm{NP}\)-complete even with unit project costs and fixed order-based tie-breaking, and is polynomial-time solvable for a single voter ([source](https://arxiv.org/pdf/2305.08125)). No complexity classification for this exact continuous mass-transfer problem was located in the literature search.
The decision problem is \(\mathrm{NP}\)-hard, even when all initial masses are dyadic rationals and the budget is polynomially bounded in the size of the reduction.
The proof below allows arbitrary admissible real transfers, including transfers to approval types outside the original support.
We reduce from Exact Cover by 3-Sets, the standard \(\mathrm{NP}\)-complete problem: given a universe \(E\) of size \(3n\) and triples \(A_1,\ldots,A_\ell\subseteq E\), decide whether \(n\) of these triples partition \(E\). Its \(\mathrm{NP}\)-completeness is recorded, for example, in [Yamakami (2022)](https://arxiv.org/abs/2206.10389).
We assume \(n\geq2\) and \(\ell\geq1\). These restrictions preserve hardness: add two triples of new elements, with each new element occurring only in its corresponding new triple.
It is convenient to describe the constructed society using raw weights summing to an integer \(N\). A cohort of raw weight \(r\) has actual mass \(r/N\), and we set \(B=N\).
Write \(\beta=b/N\) for its rescaled balance and \(q\) for a rescaled price, so the actual price is \(Nq\). The affordability equation becomes
\(\displaystyle \sum_g r_g\min\{\beta_g,q\}=1.\)
Every rescaled initial balance equals \(1\). Selection comparisons and balance updates are unchanged by this rescaling.
Choose the dyadic rational
\(\displaystyle v=2^{-\lceil\log_2(100n)\rceil},\qquad a=2n,\qquad w=100+v,\qquad u=3nw.\)
In particular, \(0<v\leq1/(100n)\leq1/200\).
Define
\(\displaystyle l=\frac{a}{1-2v},\qquad r=\frac{a(1-v)}{1-3v}.\)
Their separation is
\(\displaystyle r-l=\frac{2av^2}{(1-3v)(1-2v)}\geq2av^2.\)
Choose a dyadic rational \(d\) satisfying
\(\displaystyle \left|d-\frac{l+r}{2}\right|\leq\frac{av^2}{10}.\)
This can be done with \(O(\log n)\) bits after the binary point. Consequently,
\(\displaystyle d-l\geq\frac{9av^2}{10},\qquad r-d\geq\frac{9av^2}{10},\qquad a<d<2.1n.\)
Next set
\(\displaystyle h=\left\lceil\frac{100n}{1-\frac{3}{2d}}\right\rceil,\qquad \beta_H=1-\frac{100n}{h},\qquad t=d\beta_H.\)
These parameters satisfy
\(\displaystyle 100n<h\leq161n,\qquad \frac32\leq t<\frac85.\)
Indeed, if \(h_* =100n/(1-3/(2d))\), then \(h_*\leq160n\), and rounding upward gives the asserted bound on \(h\). Moreover,
\(\displaystyle t-\frac32=\frac{100nd(h-h_*)}{hh_*}<\frac{d}{100n}<0.021.\)
Choose \(N\) to be the smallest power of two strictly greater than \(a+u+h\). Thus \(N=O(n)\).
The four prices governing the reduction are
\(\displaystyle q_s=\frac{1-3v}{a},\qquad q_d=\frac{1-v}{d},\qquad q_p=\frac1d,\qquad q_1=\frac{1-2v}{a}.\)
They satisfy
\(\displaystyle q_s<q_d<q_p<q_1.\)
We need quantitative separation. Define
\(\displaystyle \gamma=\frac{v^2}{10n}.\)
Using the bounds on \(d-l\) and \(r-d\),
\(\displaystyle q_d-q_s=\frac{(1-3v)(r-d)}{ad}\geq\gamma,\)
\(\displaystyle q_1-q_p=\frac{(1-2v)(d-l)}{ad}\geq\gamma,\)
and
\(\displaystyle q_p-q_d=\frac vd\geq\gamma.\)
For example, the first two differences exceed \(0.4v^2/n\), since \(d<2.1n\) and \(v\leq1/200\).
Create the following unit-cost projects:
The fixed tie-breaking order places \(p\) before every blocker \(z_e\). All other comparisons in that order may be arbitrary.
The society consists of the following cohorts.
| Cohort | Raw weight | Approval set |
|---|---:|---|
| \(G_A\) | \(a\) | All set projects |
| \(G_D\) | \(d\) | All \(H\)-projects, \(p\), and all blockers |
| \(G_H\) | \(h-d\) | All \(H\)-projects |
| \(G_e\), for each \(e\in E\) | \(w\) | All \(U\)-projects, \(z_e\), and every \(s_i\) with \(e\in A_i\) |
| \(G_\varnothing\) | \(N-a-u-h\) | Empty set |
All raw weights are positive and dyadic. Since \(N\) is a power of two, their actual masses are also dyadic. The support has \(3n+4\) types.
We first analyze executions on this initial society that may choose any project of minimum price when prices tie. These reference executions are an analytical device. The manipulated society always uses the specified fixed tie-breaking order.
Every remaining \(U\)-project has price \(1/u\). Before the last such project is selected, its approving cohorts have balance at least \(1/u+v/w\), so this price is finite throughout the phase.
Every \(H\)-project has price \(1/h\).
A set project's total approving raw weight is \(a+3w\leq153n\), and a blocker's is \(d+w\leq53n\). Any project with approving weight \(R\) has price at least \(1/R\), because its contribution at price \(q\) is at most \(Rq\).
Therefore every non-\(U\) project has price at least \(1/(161n)\), whereas \(1/u\leq1/(300n)\). The gap is greater than \(1/(400n)\), and hence greater than \(\gamma\).
Thus all \(300n\) \(U\)-projects are selected first. Afterwards each element cohort has balance
\(\displaystyle \beta_e=1-\frac{300n}{u}=\frac{v}{w}.\)
Its total remaining money is exactly \(w\beta_e=v\).
During this phase, the \(G_A\) balance remains \(1\), and the \(G_D\) balance remains at least \(\beta_H=t/d\).
Notice that
\(\displaystyle \beta_e=\frac{v}{w}<q_s.\)
Thus the three element cohorts supporting a set project each contribute their entire remaining money \(v\). Its price is \(q_s\).
Similarly, a blocker has price \(q_d\), and \(p\) has price \(q_p\). The \(G_D\) cohort can pay these prices because \(\beta_H\geq3/(2d)>q_p\).
Each remaining \(H\)-project has price \(1/h\leq1/(100n)\), while \(q_s>0.49/n\). Hence all \(100n\) \(H\)-projects are selected next, again with a gap greater than \(\gamma\).
Afterwards the \(G_D\) and \(G_H\) balances are \(\beta_H\).
Suppose \(k\) pairwise disjoint set projects have been selected.
Every element in their union has balance zero. Every uncovered element still has balance \(\beta_e\). The \(G_A\) balance is
\(\displaystyle 1-kq_s\geq1-nq_s>\frac12.\)
If a remaining triple contains exactly \(j\) covered elements, its price is
\(\displaystyle \frac{1-(3-j)v}{a}.\)
This formula is valid because uncovered element cohorts exhaust their balances, and the \(G_A\) cohort can pay every price up to \(1/a\leq1/4\).
Consequently:
Since \(q_s<q_d<q_p<q_1\), reference executions continue selecting disjoint triples until none remains.
If these triples form an exact cover, all blockers tie with \(p\) at price \(q_p\). The given order then selects \(p\).
If they do not form an exact cover, an uncovered element exists, and its blocker is selected before \(p\). That blocker obtains \(v\) from its element cohort and \(1-v\) from \(G_D\). Afterwards the total remaining money of \(G_D\) is
\(\displaystyle t-1+v<\frac35+\frac1{200}<1.\)
Therefore \(p\) is subsequently unaffordable.
This already establishes the intended combinatorial behavior. The next section proves that sufficiently small arbitrary transfers cannot circumvent it.
Set
\(\displaystyle R=401n+1,\qquad \delta=\frac1{10}\min\left\{\gamma,\frac vw,\frac1N\right\},\)
\(\displaystyle \varepsilon=\frac{\delta}{100(N+1)^{R+2}},\qquad \rho=\frac{\varepsilon}{N}.\)
These are positive rationals with polynomial encoding length.
Fix any admissible transfer. Completing its rows by retaining untransferred mass gives a coupling between the initial and resulting societies.
Let \(\eta\) be the total raw weight sent to a different approval type. Since each such transfer has Hamming cost at least \(1\),
\(\displaystyle \eta\leq N\rho=\varepsilon.\)
We can therefore regard the resulting society as unchanged portions of the original cohorts, together with altered portions of total raw weight at most \(\varepsilon\).
Consider any reference prefix before its first blocker or target selection.
Every remaining project has a finite reference price \(q\) satisfying
\(\displaystyle \frac1N\leq q\leq\frac1a\leq\frac14.\)
Furthermore, at that price it has an approving reference cohort, or collection of cohorts, with:
Here is the verification:
The weights of these approving groups are respectively \(u,h,a,d\), all at least \(4\).
Suppose the manipulated and reference executions have selected the same prefix of projects. Let \(E\) bound the difference between their balances on every unchanged original cohort.
For a remaining project, write \(F(q)\) for its reference contribution function and \(\widehat F(q)\) for its manipulated contribution function. For \(0\leq q\leq1\),
\(\displaystyle |\widehat F(q)-F(q)|\leq NE+2\varepsilon.\)
Indeed, unchanged portions contribute an error at most \(NE\), because \(b\mapsto\min\{b,q\}\) is \(1\)-Lipschitz. Removed original portions and altered portions each have total raw weight at most \(\varepsilon\), and their balances are at most \(1\).
Put \(K=NE+2\varepsilon\), and suppose \(K<\delta\). On the interval \([q-K,q+K]\), the reference approving group identified above remains unsaturated. Its weight is at least \(4\). Since \(F(q)=1\),
\(\displaystyle F(q-K)\leq1-4K,\qquad F(q+K)\geq1+4K.\)
Thus
\(\displaystyle \widehat F(q-K)<1,\qquad \widehat F(q+K)>1.\)
The interval lies inside \([0,1]\), because \(q\geq1/N\), \(q\leq1/4\), and \(K<\delta\leq1/(10N)\).
By continuity and monotonicity, the manipulated project's least price is finite and differs from its reference price by at most \(K\). This argument handles least prices explicitly; it does not assume that an arbitrary solution of the affordability equation is the least one.
If both executions select the same project, the balance update on an approving unchanged cohort is
\(\displaystyle \beta\longmapsto\max\{0,\beta-q\}.\)
Hence its new balance error is at most \(E+K\). Starting from \(E_0=0\), we obtain
\(\displaystyle E_{j+1}\leq(N+1)E_j+2\varepsilon,\qquad E_j\leq2\varepsilon(N+1)^j.\)
Consequently, for every \(j\leq R\),
\(\displaystyle K_j=NE_j+2\varepsilon\leq4\varepsilon(N+1)^{j+1}<\delta.\)
In particular, \(E_j<\delta\).
At every reference state considered above, the cheapest project class is separated from all other classes by at least \(\gamma\). Since every candidate price changes by less than \(\delta\) and \(2\delta<\gamma\), the manipulated execution must select a member of that same cheapest class.
Within a tied reference class, choose the same project that the manipulated execution selects. This produces a reference prefix to which the argument applies at the next step.
Thus, inductively, every admissible manipulated execution follows the reference phase structure up to its first blocker or target selection:
There are at most \(400n+n+1<R+1\) selections in this prefix, so the error bounds cover all of it.
Suppose \(I\subseteq\{1,\ldots,\ell\}\) indexes an exact cover.
Transfer raw weight
\(\displaystyle \theta=\frac{\varepsilon}{2\ell}\)
from \(G_A\) to an approval type approving exactly the set projects indexed by \(I\).
The actual transferred mass is \(\theta/N\). Its cost is
\(\displaystyle \frac{(\ell-n)\theta}{N}\leq\frac{\varepsilon}{2N}<\rho.\)
If \(\ell=n\), no change is needed.
The preparation phases are unchanged. During the subsequent selection of cover projects, both portions of \(G_A\) approve every selected project and therefore have identical balances.
An unselected cover project has price \(q_s\). A project outside the cover has approving \(G_A\) weight at most \(a-\theta\), so its price is at least
\(\displaystyle \frac{1-3v}{a-\theta}>q_s.\)
The blockers and target retain their original prices, all greater than \(q_s\). Thus the \(n\) cover projects are selected first, independently of their internal order.
They exhaust every element cohort. Afterwards \(p\) and all blockers have price \(q_p\), while any remaining set project has price at least \(1/a>q_p\). The fixed tie-breaking order selects \(p\).
Suppose the triples admit no exact cover, and fix any admissible real transfer.
By Section 4, the manipulated execution selects all preparation projects and then follows a reference sequence of pairwise disjoint triples.
When no further disjoint triple remains, some element is uncovered: otherwise the selected triples would constitute an exact cover. An uncovered element's blocker has reference price \(q_d\), while \(p\) has reference price \(q_p\), with \(q_p-q_d\geq\gamma\).
Therefore the manipulated execution selects an uncovered-element blocker before \(p\).
Immediately after that selection, the reference \(G_D\) money is \(t-1+v\). Only \(G_D\) originally approves \(p\). The unchanged portion of this cohort can have at most \(N E_j\) additional money relative to the reference amount, and all altered portions together can contribute at most \(\eta\leq\varepsilon\).
The manipulated total money approving \(p\) is therefore at most
\(\displaystyle t-1+v+NE_j+\eta <\frac35+\frac1{200}+\frac1{10}+\frac1{10} =\frac{161}{200}<1.\)
Here we used \(E_j<\delta\), \(N\delta\leq1/10\), and \(\eta\leq\varepsilon<1/10\).
Thus \(p\) is unaffordable. Balances only decrease during subsequent selections, so it remains unaffordable forever.
This proves soundness for every admissible transfer, regardless of its destinations or whether its amounts are rational.
The construction has
\(\displaystyle m=400n+\ell+3n+1,\qquad \tau=3n+4,\qquad B=N=O(n).\)
The initial masses are dyadic with polynomial encoding length. The exponent \(R+2\) is \(O(n)\), and \(N=O(n)\), so the radius \(\rho\) has \(O(n\log n)\) bits. All parameters and approval lists can be constructed in polynomial time.
We have proved the equivalence:
\(\displaystyle \text{The triples admit an exact cover}\quad\Longleftrightarrow\quad \text{an admissible transfer makes continuous MES-Apr fund }p.\)
Therefore the stated continuous mass-transfer problem is \(\mathrm{NP}\)-hard. A polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The reduction establishes the claimed \(\mathrm{NP}\)-hardness. The parameter bounds, reference execution, perturbation estimates, and both directions of the reduction are sound. There is one minor inconsistency concerning tie-breaking in the analytical reference executions; it does not invalidate the reduction.
The stated source problem is Exact Cover by 3-Sets, with a universe of size \(3n\) and sets of cardinality three. Its \(\mathrm{NP}\)-completeness is consistent with the cited [Yamakami paper](https://arxiv.org/abs/2206.10389).
Adding two triples on fresh elements preserves the answer: both new triples must belong to every exact cover of the augmented universe. Thus the restrictions \(n\geq2\) and \(\ell\geq1\) preserve hardness.
The rescaling is correct. Substituting mass \(r_g/N\), balance \(N\beta_g\), and actual price \(Nq\) into the affordability equation gives \(\sum_g r_g\min\{\beta_g,q\}=1\). Initial rescaled balances are one, and both price comparisons and balance updates are preserved.
The parameter calculations check out:
The quantitative price gaps also hold. For example, the stated estimates give \(q_d-q_s\geq0.985(0.9)v^2/(2.1n)>0.4v^2/n>\gamma\). The bound for \(q_1-q_p\) is at least as strong, and \(q_p-q_d=v/d\geq\gamma\).
No sign, denominator, or small-instance problem arises at \(n=2\).
All raw weights are positive. In particular, \(h-d>0\), and the empty cohort has positive weight because \(N>a+u+h\). Their sum is \(N\).
The initial masses are dyadic: every raw weight is dyadic, and \(N\) is a power of two. The approval types are distinct, giving the stated support size \(3n+4\).
For the first preparation phase:
For the second preparation phase, the element cohorts saturate at set and blocker prices, while \(G_D\) remains able to pay those prices. Each remaining \(H\)-project has price \(1/h\), strictly below every competing price by more than \(\gamma\). The final balances of \(G_D\) and \(G_H\) are correctly computed as \(\beta_H\).
After \(k\) disjoint triples have been selected, the claimed balances are correct. The bound \(1-kq_s>1/2\) holds because \(k\leq n\).
The formula \((1-(3-j)v)/a\) for a remaining set containing \(j\) covered elements is valid: uncovered element cohorts exhaust their balances, while \(G_A\) remains unsaturated.
The stated prices of uncovered blockers, covered blockers, and the target follow directly. Therefore:
The only issue here concerns the wording about arbitrary reference ties, discussed below.
The coupling argument correctly bounds the altered raw weight by \(\eta\leq N\rho=\varepsilon\). Diagonal transfers have no effect and can be included in the retained portion.
The conceptual subdivision into unchanged and altered portions is consistent with MES: portions with identical resulting approval types start with identical balances and receive identical updates.
The price-stability argument is valid:
The balance recurrence \(E_{j+1}\leq(N+1)E_j+2\varepsilon\) follows from the stated update map. Its derived bounds hold throughout the required prefix. Since \(2\delta<\gamma\), perturbations cannot reverse any strict interclass comparison used in the reduction.
Choosing the manipulated selection within a tied reference minimum produces a valid reference prefix. This does not assume that arbitrary reference ties follow the fixed order.
The proposed transfer is admissible:
Preparation prices are unaffected. During cover selection, both portions of \(G_A\) have identical balances. An unselected cover project retains price \(q_s\), whereas every project outside the cover has strictly greater price by the stated lower bound.
After the cover is selected, all element cohorts are exhausted. The target and blockers have equal price, and the actual fixed order selects the target. Thus completeness is established.
Without an exact cover, the reference disjoint family leaves an uncovered element. Stability forces the manipulated execution to select an uncovered blocker before the target.
The error estimate remains applicable immediately after that selection through the balance-update recurrence. The upper bound \(t-1+v+NE_j+\eta<161/200<1\) is valid.
Only unchanged portions of \(G_D\) and altered portions can contribute money to the target. Their combined money is therefore insufficient. Subsequent selections only decrease balances, so the target remains unaffordable.
This covers arbitrary real transfers and destinations outside the original support.
The project count, support size, and budget bounds are correct. All parameters have polynomial encoding length; in particular, the exponent in the radius contributes only \(O(n\log n)\) bits.
The construction is polynomial in the explicit X3C input size. The two proved directions establish the claimed reduction. No membership in \(\mathrm{NP}\) is asserted or needed.
Minor — Section 3.3, exact-cover case. Reference executions were defined to permit any minimum-price tie choice. Such an execution may select a blocker instead of the target after an exact cover. Consequently, “The given order then selects \(p\)” applies to an execution using that order, not to every reference execution.
The minimum clarification is to explicitly restrict that sentence to executions respecting the specified tie-breaking order. Section 5.1 already establishes this behavior for the actual manipulated execution, so no additional mathematics is needed.
⟨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.