Answer: Polynomial-time solvable for \(m=1\), with running time \(O(\tau L^2)\) bit operations. Feasibility holds exactly when \(\sum_t\mu_t w_t\leq q(1+\Delta)\).
Theorem 18 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateSuper-Imputation-Stability-WVG and Cost-of-Stability-WVG are both coNP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finitely many types with rational masses \(\mu_t>0\), voting weights \(w_t\), a quota \(q\), and a subsidy bound \(\Delta\), decide whether there are nonnegative per-capita payments \(p_t\) such that \(1\leq\sum_t\mu_t p_t\leq1+\Delta\) and \(\sum_t p_t x_t\geq1\) for every mass coalition \(x\) with \(0\leq x_t\leq\mu_t\) and \(\sum_t w_t x_t\geq q\).
A society is given by its support: a list of the \(\tau\geq1\) types with positive masses \(\mu_t\), each a binary rational; \(\tau\) is the support size, not the number of possible types. Total mass need not equal \(1\).
Each type has a nonnegative integer voting weight \(w_t\); the integer quota satisfies \(0<q\leq\sum_t\mu_t w_t\). The subsidy bound \(\Delta\geq0\) is rational, and all numerical inputs are encoded in binary.
A mass coalition is any real vector \(x\) with \(0\leq x_t\leq\mu_t\); it earns \(1\) if \(\sum_t w_t x_t\geq q\), and \(0\) otherwise. A payment \(p_t\in\mathbb R_{\geq0}\) is paid per unit mass of type \(t\).
The decision problem asks whether payments exist satisfying \(1\leq\sum_t\mu_t p_t\leq1+\Delta\) and \(\sum_t p_t x_t\geq1\) for every winning mass coalition \(x\).
There is one voting-weight coordinate, so \(m=1\); state running times in \(m,\tau,L\), where \(L\) is the total input bit length.
Is this continuous subsidy-feasibility problem solvable in polynomial time, or is it NP-hard?
For finite indivisible players, deciding whether a subsidy bound permits stable payments is coNP-complete with binary integer weights and quota, and is in P with unary weights. [Verified discrete results](https://doi.org/10.1613/jair.1.11270).
No prior result settling exactly this continuous problem was identified in the literature search.
Result. The continuous problem is solvable in polynomial time. Define the total voting weight by \(W=\sum_{t=1}^{\tau}\mu_t w_t\). The exact minimum subsidy is \(\Delta_{\min}=W/q-1\), so feasibility is equivalent to \(W\leq q(1+\Delta)\).
Lower bound. Let \(p\) be any payment vector satisfying every winning-coalition constraint, and let \(P=\sum_t\mu_t p_t\) denote its total payment.
By the premises, \(0<q\leq W\). Consequently, the vector defined by \(x_t^*=(q/W)\mu_t\) satisfies \(0\leq x_t^*\leq\mu_t\) for every type. Its voting weight is exactly the quota:
\(\displaystyle \sum_t w_t x_t^*=\frac{q}{W}\sum_t w_t\mu_t=q.\)
Thus \(x^*\) is a winning mass coalition. Its payment must be at least \(1\), giving
\(\displaystyle 1\leq\sum_t p_t x_t^*=\frac{q}{W}P.\)
Since \(q/W>0\), this implies \(P\geq W/q\). In particular, feasibility requires \(W/q\leq1+\Delta\).
Attaining the bound. Set \(p_t=w_t/q\) for every type. These payments are nonnegative, including for types with zero voting weight. For any winning mass coalition \(x\),
\(\displaystyle \sum_t p_t x_t=\frac{1}{q}\sum_t w_t x_t\geq1.\)
Their total payment is
\(\displaystyle P=\sum_t\mu_t p_t=\frac{W}{q}.\)
The assumption \(W\geq q\) ensures \(P\geq1\). Therefore, whenever \(W/q\leq1+\Delta\), this vector satisfies every required condition. Together with the lower bound, this proves both the feasibility criterion and the exact minimum subsidy.
Algorithm and bit complexity. Compute \(W\) exactly and accept precisely when \(W\leq q(1+\Delta)\). Here \(\tau\) counts only the explicitly listed support types; no enumeration of other possible types is needed.
For an explicit bound, write \(\mu_t=a_t/b_t\) and \(\Delta=c/d\), with positive integer denominators. Define
\(\displaystyle D=\prod_{t=1}^{\tau}b_t,\qquad N=\sum_{t=1}^{\tau}a_t w_t(D/b_t).\)
Then \(W=N/D\), and the acceptance test is the integer comparison
\(\displaystyle Nd\leq qD(c+d).\)
Each product appearing in a summand uses numerical inputs whose combined bit length is at most \(L\). Summing \(\tau\) such terms adds at most \(O(\log\tau)\) bits. Hence all intermediate integers have \(O(L)\) bits, since the explicit support encoding implies \(\tau\leq O(L)\).
The construction and comparison use \(O(\tau)\) integer arithmetic operations. With schoolbook multiplication and division, the running time is \(T(1,\tau,L)=O(\tau L^2)\) bit operations, and therefore also \(O(L^3)\). This is a polynomial bound for the stipulated single coordinate \(m=1\).
The decisive continuous feature is the admissibility of the coalition \(x^*=(q/W)\mu\). A coalition taking the same arbitrary fraction of every type is generally unavailable for indivisible players, so the lower-bound argument does not transfer to that model.
⟨structured verdict parsed — rendered above⟩
Verdict: proved. The output resolves the assigned continuous problem. The feasibility criterion, exact minimum subsidy, and polynomial running time are justified. No mathematical or complexity issues were found.
The quantity \(W=\sum_{t=1}^{\tau}\mu_t w_t\) is well-defined and rational. The premise \(0<q\leq W\) ensures \(W>0\), so every division by \(W\) or \(q\) in the proof is valid.
The proof uses the explicitly listed support types only and does not assume that total mass equals \(1\).
Since \(0<q/W\leq1\), the vector \(x_t^*=(q/W)\mu_t\) satisfies every coalition bound \(0\leq x_t^*\leq\mu_t\).
The voting-weight calculation is exact:
\[ \sum_t w_t x_t^*=\frac{q}{W}W=q. \]
Thus this coalition is winning, including at equality with the quota. Applying its stability constraint gives
\[ 1\leq\frac{q}{W}P, \]
and hence \(P\geq W/q\). This establishes the claimed necessary condition \(W/q\leq1+\Delta\).
The argument applies to every admissible payment vector; it makes no additional assumption about its structure.
The proposed payments \(p_t=w_t/q\) are nonnegative because \(w_t\geq0\) and \(q>0\).
For every winning coalition, its defining inequality directly yields
\[ \sum_t p_t x_t=\frac{1}{q}\sum_t w_t x_t\geq1. \]
The total payment is exactly \(W/q\). The premise \(W\geq q\) supplies the required lower bound of \(1\); the acceptance condition supplies the upper bound of \(1+\Delta\).
Consequently, the construction satisfies all constraints whenever the necessary condition holds.
The universal lower bound and its attained value establish that the minimum total payment is \(W/q\). Because this value is at least \(1\), the minimum subsidy is indeed \(\Delta_{\min}=W/q-1\).
The reasoning covers zero-weight types, a support of size \(1\), the boundary case \(W=q\), and a zero subsidy bound. No omitted edge case changes the conclusion.
For the stated rational representations, \(D\) is positive, each \(D/b_t\) is an integer, and the expression for \(N\) gives \(W=N/D\). Multiplication by the positive denominators correctly transforms the feasibility condition into
\[ Nd\leq qD(c+d). \]
Each summand of \(N\) multiplies numerators, weights, and denominators whose combined input bit length is bounded by \(L\). Summation increases the bit length by at most \(O(\log\tau)\). The remaining comparison products also have \(O(L)\) bits. The explicit support encoding justifies \(\tau=O(L)\).
Computing the denominator product, the exact quotients, the summands, their sum, and the final comparison requires \(O(\tau)\) integer arithmetic operations. Schoolbook multiplication and division on these integers justify \(T(1,\tau,L)=O(\tau L^2)\), and therefore \(O(L^3)\). The bound is correctly restricted to the stipulated \(m=1\).
The explanation concerning indivisible players correctly identifies why the particular fractional coalition need not be available there. The continuous proof relies on no external theorem or discrete complexity result.
Required clarification or repair: none.
⟨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.