Answer: Polynomial-time solvable in \(O(\tau L^2)\) bit operations. The exact optimum is \(\varepsilon^*=1-\theta/(\sum_t\mu_tq_t)\), attained by \(r_t^*=q_t/(\sum_s\mu_sq_s)\).
Theorem 5 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe problems LEASTCORE, IN-LEASTCORE, and CONSTRUCT-LEASTCORE are NP-hard.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses μ_t summing to \(1\), per-unit weights \(q_t\), and a threshold θ no greater than the population's total weight, find the smallest ε and rates \(r_t\ge 0\) such that ∑_t μ_t r_t=1 and ∑_t a_t r_t\ge 1-ε for every coalition mass vector with \(0\le a_t\le μ_t\) and ∑_t q_t a_t\ge θ. The decision version asks whether such rates exist for a given ε.
A society is given by its support: a list of \(\tau\ge1\) types with positive binary-rational masses \(\mu_t\), where \(\sum_t\mu_t=1\); \(\tau\) is the support size, not the number of possible types.
Each type has a binary-rational per-unit weight \(q_t\ge0\). The binary-rational threshold satisfies \(0<\theta\le\sum_t\mu_tq_t\).
A coalition is any real mass vector \(a\) with \(0\le a_t\le\mu_t\), including partial masses of each type. Its value is \(1\) if \(\sum_tq_ta_t\ge\theta\), and \(0\) otherwise.
An imputation consists of nonnegative rational rates \(r_t\) constant within each type, with \(\sum_t\mu_tr_t=1\); coalition \(a\) receives \(\sum_ta_tr_t\).
Given a binary-rational \(\varepsilon\ge0\), continuous least-core feasibility asks whether an imputation exists satisfying \(\sum_ta_tr_t\ge1-\varepsilon\) for every winning coalition. The associated optimization minimizes \(\varepsilon\).
Let \(L\) be the total input bit length. State running times in \(\tau\) and \(L\); there is no candidate parameter \(m\) in this problem.
Is continuous least-core feasibility solvable in polynomial time in \(\tau,L\), or is it NP-hard under polynomial-time Turing reductions?
For finite weighted threshold games, least-core feasibility, membership, and construction were originally reported NP-hard. [Discrete anchor](https://www.cs.ox.ac.uk/people/paul.goldberg/papers/wtgames.pdf)
The expanded treatment identifies feasibility as coNP-hard, membership as NP-hard, and construction as NP-hard; it also gives pseudopolynomial algorithms. [Expanded treatment](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/amai2009.pdf)
No result settling this exact continuous problem with finite rational support was identified in the literature search.
Continuous least-core feasibility is polynomial-time solvable. In fact, it has an exact closed-form solution.
Define \(W=\sum_{t=1}^{\tau}\mu_tq_t\). The hypotheses imply \(0<\theta\le W\). Then the minimum feasible slack is
\(\displaystyle \varepsilon^*=1-\frac{\theta}{W},\)
and an optimal rational imputation is
\(\displaystyle r_t^*=\frac{q_t}{W}\qquad(t=1,\ldots,\tau).\)
Thus, for the given \(\varepsilon\ge0\), feasibility holds if and only if \(\varepsilon\ge1-\theta/W\). Feasibility, exact optimization, and construction of these optimal rates take \(O(\tau L^2)\) bit operations using elementary integer arithmetic.
Let \(r\) be any imputation, so \(r_t\ge0\) and \(\sum_t\mu_tr_t=1\).
Set \(\alpha=\theta/W\). Since \(0<\alpha\le1\), the vector defined by \(a_t=\alpha\mu_t\) is an admissible coalition: each coordinate satisfies \(0\le a_t\le\mu_t\). Its weight is
\(\displaystyle \sum_tq_ta_t=\alpha\sum_tq_t\mu_t=\alpha W=\theta.\)
Hence this coalition is winning. Its payment under the arbitrary imputation \(r\) is
\(\displaystyle \sum_ta_tr_t=\alpha\sum_t\mu_tr_t=\alpha=\frac{\theta}{W}.\)
Consequently, satisfying every winning-coalition constraint requires \(\theta/W\ge1-\varepsilon\), or equivalently \(\varepsilon\ge1-\theta/W\).
This proves the lower bound for every imputation, including the required rational imputations.
Define \(r_t^*=q_t/W\). These rates are rational and nonnegative because all input numbers are rational and \(W>0\). They satisfy the imputation normalization:
\(\displaystyle \sum_t\mu_tr_t^*=\frac{1}{W}\sum_t\mu_tq_t=1.\)
For every winning coalition \(a\), its defining inequality gives
\(\displaystyle \sum_ta_tr_t^*=\frac{1}{W}\sum_tq_ta_t\ge\frac{\theta}{W}=1-\varepsilon^*.\)
Therefore \(r^*\) is feasible at \(\varepsilon^*=1-\theta/W\). Since \(\theta\le W\), this slack is nonnegative, as required.
Together with the lower bound, this proves optimality. The same rates satisfy every larger slack, establishing the stated feasibility criterion. The argument also covers zero-weight types and the boundary case \(\theta=W\).
The algorithm computes \(W\) exactly and checks \(W(1-\varepsilon)\le\theta\). If feasible, it can return \(r_t=q_t/W\); for optimization, it returns these rates and \(\varepsilon^*=1-\theta/W\).
To justify the binary complexity, write the supplied numbers as \(\mu_t=p_t/d_t\) and \(q_t=u_t/v_t\), with positive denominators. No reduction to lowest terms is necessary. Set
\(\displaystyle D=\prod_{t=1}^{\tau}d_tv_t,\qquad N=\sum_{t=1}^{\tau}p_tu_t\,\frac{D}{d_tv_t}.\)
Then \(W=N/D\), and \(N>0\).
The bit length of \(D\) is \(O(L)\), since the lengths of all input denominators contribute to \(L\). Each summand defining \(N\) has \(O(L)\) bits; adding \(\tau\) such summands adds at most \(O(\log\tau)\) bits. Since \(\tau\le L\), the bit length of \(N\) is also \(O(L)\). These bounds apply to the intermediate products and partial sums.
Computing \(D\) and \(N\) requires \(O(\tau)\) integer arithmetic operations on \(O(L)\)-bit integers. Schoolbook multiplication and division each take \(O(L^2)\) bit operations. The feasibility comparison uses cross multiplication on integers of the same asymptotic size. Thus feasibility takes \(O(\tau L^2)\) bit operations.
For construction, each rate can be output as \(u_tD/(v_tN)\), with \(O(L)\)-bit numerator and denominator. Computing all rates, together with the exact optimal slack, remains within \(O(\tau L^2)\) bit operations. There is no additional candidate parameter.
The cited finite model takes coalitions to be subsets of indivisible players. [Expanded treatment, Section 2](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/amai2009.pdf)
The decisive coalition here, \(a_t=(\theta/W)\mu_t\), uses partial masses of every type. Such a coalition is permitted by the continuous model and generally unavailable in the discrete model. The proof therefore establishes the continuous result independently of the discrete hardness results.
Since this problem is in \(\mathrm{P}\), NP-hardness under polynomial-time Turing reductions would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned continuous problem correctly. The lower bound applies to every permitted imputation, the proposed rational rates attain it, and the stated \(O(\tau L^2)\) bit-complexity bound is justified. No major or minor issues were found.
The definition \(W=\sum_{t=1}^{\tau}\mu_tq_t\) agrees with the task. The assumption \(0<\theta\le W\) ensures \(W>0\), so every division by \(W\) is valid. It also gives \(0<\theta/W\le1\).
The argument uses the listed support types and permits partial masses, exactly as required. It introduces no additional parameter or restriction on coalitions.
The prover fixes an arbitrary imputation satisfying \(r_t\ge0\) and \(\sum_t\mu_tr_t=1\). With \(\alpha=\theta/W\), the coalition \(a_t=\alpha\mu_t\) satisfies all coordinate bounds because \(0<\alpha\le1\).
Its weight calculation is exact:
\[
\sum_tq_ta_t=\alpha W=\theta.
\]
Equality qualifies as winning under the task’s threshold convention.
Its payment is exactly \(\alpha\), independently of the chosen imputation:
\[
\sum_ta_tr_t=\alpha\sum_t\mu_tr_t=\theta/W.
\]
Consequently, the universal winning-coalition requirement necessarily implies \(\varepsilon\ge1-\theta/W\). There is no quantifier reversal: a single admissible coalition supplies the bound for every imputation. In particular, the argument applies to rational imputations.
The proposed rates \(r_t^*=q_t/W\) are rational and nonnegative. Their normalization follows directly from the definition of \(W\).
For an arbitrary winning real coalition, the prover’s calculation
\[
\sum_ta_tr_t^*=\frac{\sum_tq_ta_t}{W}\ge\frac{\theta}{W}
\]
is valid because \(W>0\). Thus these rates satisfy every required constraint at \(\varepsilon^*=1-\theta/W\).
The assumption \(\theta\le W\) ensures \(\varepsilon^*\ge0\). Increasing \(\varepsilon\) weakens each constraint, so the same rates establish sufficiency for every larger slack. Combined with the lower bound, this proves both the exact optimum and the claimed feasibility equivalence.
Zero-weight types receive rate zero, which is allowed; all displayed identities still hold.
When \(\theta=W\), the constructed coalition in the lower bound is the grand coalition, and the proposed rates satisfy every winning-coalition constraint with slack zero. The proof also applies when \(\tau=1\). No omitted degenerate case undermines the conclusion.
The common-denominator construction is correct: each \(d_tv_t\) divides \(D\), and \(N/D=\sum_t\mu_tq_t=W\). Hence the divisions used to compute \(N\) are exact and \(N>0\).
The denominator product has \(O(L)\) bits. Each summand has \(O(L)\) bits, and summing \(\tau\) nonnegative terms increases the bound by at most \(O(\log\tau)\). Since the explicit support encoding gives \(\tau\le L\), \(N\) and the intermediate quantities have \(O(L)\) bits.
Computing the products, exact divisions, and sums requires \(O(\tau)\) arithmetic operations. Schoolbook arithmetic therefore supports the stated \(O(\tau L^2)\) bound. The signed comparison \(W(1-\varepsilon)\le\theta\) remains valid when \(\varepsilon>1\), and cross multiplication uses positive denominators.
The output formula \(u_tD/(v_tN)\) equals \(q_t/W\). Each output numerator and denominator has \(O(L)\) bits; reduction to lowest terms is unnecessary. Construction and exact optimization consequently fit the same running-time bound.
The cited finite model defines coalitions as subsets of a finite player set, confirming the prover’s stated distinction. [Expanded treatment, Section 2](https://www.cs.ox.ac.uk/people/michael.wooldridge/pubs/amai2009.pdf)
No discrete hardness theorem is used to establish the continuous result. The final conditional statement about Turing hardness is correct: a polynomial-time algorithm for an NP-hard problem under polynomial-time Turing reductions would imply \(\mathrm{P}=\mathrm{NP}\).
No additional clarification or mathematical repair 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.