Answer: Continuous CS-core membership is in \(\mathrm{P}\).
Theorem 3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateThe problem INCSCORE is coNP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational masses \(x_r\), weights \(w_r\), payoff densities \(a_r\), a quota \(q\), and a block assignment for finitely many cells \(r\), with the candidate outcome satisfying each block’s feasibility and payoff condition, decide whether every measurable coalition of weight at least \(q\) receives payoff at least \(1\). Equivalently, decide whether the minimum of \(\sum_r a_r z_r\), subject to \(\sum_r w_r z_r \ge q\) and \(0 \le z_r \le x_r\), is at least \(1\).
A society is given by its support: a list of \(\tau\) types with positive binary rational masses \(x_r\). Here \(\tau\) is the support size, not the number of possible types; total mass is arbitrary and finite.
Type \(r\) represents an atomless cell of mass \(x_r\), with constant rational weight density \(w_r\ge0\), payoff density \(a_r\ge0\), and block label \(b_r\in\{1,\ldots,m\}\). Every block has positive mass. The rational quota satisfies \(0<q\le\sum_r w_rx_r\).
A measurable coalition may select any real mass \(z_r\in[0,x_r]\) from each cell, across any blocks. Its weight and assigned payoff are \(W(z)=\sum_r w_rz_r\) and \(A(z)=\sum_r a_rz_r\); its value is \(1\) when \(W(z)\ge q\), and \(0\) otherwise.
The supplied outcome is promised to be an imputation for its block partition: for every \(j\), \(\sum_{r:b_r=j}a_rx_r=\mathbf{1}\{\sum_{r:b_r=j}w_rx_r\ge q\}\).
Continuous CS-core membership asks whether every measurable winning coalition receives assigned payoff at least \(1\), equivalently whether \(\min\{\sum_r a_rz_r:\sum_r w_rz_r\ge q,\ 0\le z_r\le x_r\}\ge1\).
Is continuous CS-core membership in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? State running times in \(m\), \(\tau\), and the total binary input length \(L\).
For finite indivisible agents, CS-core membership is \(\mathrm{coNP}\)-complete and admits a pseudopolynomial algorithm in the number of agents, total integer weight, and payoff bit length. [Verified source](https://comsoc-community.org/assets/proceedings/comsoc-2008/Chalkiadakis.pdf).
No result settling exactly this continuous membership problem was identified in the literature search.
Continuous CS-core membership is in \(\mathrm{P}\). An exact algorithm uses \(\mathrm{O}(\tau\log(\tau+1))\) rational arithmetic operations and comparisons. Including an optional check of the imputation promise, a conservative bit-operation bound is
\(\mathrm{O}\bigl((m+\tau\log(\tau+1))L^2\bigr)\).
The algorithm is a fractional-knapsack computation. We prove its correctness and the bit bound below.
If \(w_r=0\), selecting mass from cell \(r\) contributes no weight and contributes nonnegative payoff. Setting \(z_r=0\) therefore preserves feasibility and cannot increase payoff. Such cells can be omitted from the minimization.
Let \(n\le\tau\) be the number of remaining cells. For each remaining cell, define its weight capacity and payoff per unit of weight by
\(h_r=w_rx_r>0,\qquad \rho_r=a_r/w_r\ge0.\)
Writing \(u_r=w_rz_r\), the minimum winning-coalition payoff becomes
\(C^*=\min\left\{\sum_{r=1}^{n}\rho_ru_r:\ \sum_{r=1}^{n}u_r\ge q,\quad 0\le u_r\le h_r\right\}.\)
This change of variables is bijective on each retained cell because \(w_r>0\). The hypothesis \(q\le\sum_r w_rx_r\) guarantees feasibility and \(n\ge1\).
Relabel the retained cells so that
\(\rho_1\le\rho_2\le\cdots\le\rho_n,\)
breaking ties arbitrarily. Put \(H_0=0\) and \(H_i=\sum_{r=1}^{i}h_r\). Let \(k\) be the smallest index with \(H_k\ge q\). Then
\(0<q-H_{k-1}\le h_k.\)
Define a candidate coalition in weight units by
\(u_r^*=h_r\) for \(r<k\), \(u_k^*=q-H_{k-1}\), and \(u_r^*=0\) for \(r>k\).
It respects every capacity and has total weight exactly \(q\). Its payoff is
\(C_{\mathrm{greedy}}=\sum_{r<k}\rho_rh_r+\rho_k(q-H_{k-1}).\)
To prove optimality, take any feasible \(u\). We have
\(\sum_{r=1}^{n}\rho_ru_r=\rho_k\sum_{r=1}^{n}u_r+\sum_{r<k}(\rho_r-\rho_k)u_r+\sum_{r>k}(\rho_r-\rho_k)u_r.\)
Each term admits the following bound:
Consequently,
\(\sum_{r=1}^{n}\rho_ru_r\ge\rho_kq+\sum_{r<k}(\rho_r-\rho_k)h_r=\sum_{r<k}\rho_rh_r+\rho_k(q-H_{k-1}).\)
The candidate attains this bound. Therefore the exact minimum is
\(C^*=\sum_{r<k}a_rx_r+\frac{a_k}{w_k}\left(q-\sum_{r<k}w_rx_r\right).\)
Zero payoff densities and tied ratios cause no difficulty: the proof uses non-strict inequalities throughout.
Returning to cell masses gives \(z_r^*=x_r\) for \(r<k\), \(z_k^*=(q-H_{k-1})/w_k\), and zero for all other cells. These masses are permitted by the atomless selection hypothesis.
Hence membership holds if and only if \(C^*\ge1\). If \(C^*<1\), the constructed coalition is an explicit witness of nonmembership.
The algorithm is:
Sorting costs \(\mathrm{O}(\tau\log(\tau+1))\) comparisons; the remaining computation uses \(\mathrm{O}(\tau)\) rational operations. Block labels do not enter this minimization because coalitions may select mass across arbitrary blocks.
For the bit bound, represent every input rational by a binary numerator and positive denominator. Their combined encoding length is at most \(L\).
Each capacity \(w_rx_r\), full-cell payoff \(a_rx_r\), and ratio \(a_r/w_r\) has bit length bounded by a constant times the encoding lengths of its operands. A prefix sum can be represented over the product of its summands’ denominators. Since each input denominator appears only a bounded number of times in these products, their bit lengths are \(\mathrm{O}(L)\). The numerators also have \(\mathrm{O}(L)\) bits: each summand has magnitude at most \(2^{\mathrm{O}(L)}\), and \(\log\tau=\mathrm{O}(L)\).
The final formula and ratio comparisons likewise involve only \(\mathrm{O}(L)\)-bit integers. Using elementary integer arithmetic, each rational operation or comparison therefore costs at most \(\mathrm{O}(L^2)\) bit operations. The promised-input membership algorithm runs in
\(\mathrm{O}\bigl(L+\tau\log(\tau+1)L^2\bigr)\).
If desired, the imputation promise can also be checked by accumulating, for every block \(j\), its mass, weight, and payoff, then checking the stated equality. This adds \(\mathrm{O}(m+\tau)\) rational operations, giving the bound claimed above. Since every block contains a support cell, \(m\le\tau\le L\), so this is polynomial in \(L\). No bound on the numerical magnitudes of the masses, weights, or quota is required.
The cited finite-agent result establishes \(\mathrm{coNP}\)-completeness for membership with indivisible agents. [Chalkiadakis, Elkind, and Jennings](https://comsoc-community.org/assets/proceedings/comsoc-2008/Chalkiadakis.pdf).
Here, the partially selected cell is allowed. That permits the exact quota-filling construction proved optimal above; with indivisible agents, that construction need not be feasible.
⟨structured verdict parsed — rendered above⟩
The prover resolves the assigned problem correctly: continuous CS-core membership is in \(\mathrm{P}\), with the stated arithmetic-operation and conservative bit-operation bounds. No major or minor mathematical issues were found.
For any feasible coalition, setting \(z_r=0\) whenever \(w_r=0\) leaves its weight unchanged and cannot increase its payoff, because \(a_r\ge0\). Conversely, a feasible selection on the retained cells extends to the original instance by selecting zero mass from discarded cells. Thus the minimum is preserved.
The assumptions \(q>0\) and \(q\le\sum_r w_rx_r\) ensure that at least one positive-weight cell remains. There is no unhandled empty-instance case.
On each retained cell, \(w_r>0\) and \(x_r>0\), so \(h_r=w_rx_r>0\), and the substitution \(u_r=w_rz_r\) bijectively maps the interval \([0,x_r]\) to \([0,h_r]\). The objective transforms correctly because
\[
a_rz_r=\frac{a_r}{w_r}u_r=\rho_ru_r.
\]
The transformed feasibility constraint and all capacity constraints are therefore exact. Division by zero is excluded before ratios are formed.
Sorting by nondecreasing \(\rho_r\) is permitted even when ratios coincide. Positive capacities make the prefix sums strictly increasing, and feasibility guarantees an index \(k\) with \(H_k\ge q\). Minimality of \(k\), together with \(H_0=0<q\), gives
\[
0<q-H_{k-1}\le h_k.
\]
Consequently, the proposed candidate respects every capacity and has total weight exactly \(q\).
This covers \(k=1\), \(k=n\), and quota equality with a prefix sum. In particular, equality \(q=H_k\) simply makes the selected amount from cell \(k\) equal to its full capacity.
The displayed decomposition of the objective is an exact algebraic identity. Each subsequent inequality has the required sign:
Their sum gives the stated lower bound, and the candidate attains it. Thus the proof establishes the global minimum, including feasible coalitions whose weight exceeds \(q\). It does not assume without justification that every optimum fills the quota exactly.
Substituting \(\rho_rh_r=a_rx_r\) yields the claimed formula for \(C^*\). Zero payoff densities and tied ratios preserve all inequalities, including when \(\rho_k=0\).
The reconstructed mass from cell \(k\) lies in \([0,x_k]\), since its selected weight lies in \([0,h_k]\). The other reconstructed masses also satisfy their bounds. Their realizability follows directly from the task’s atomless selection assumption.
The attained minimum therefore decides the universal winning-coalition condition exactly: membership holds precisely when \(C^*\ge1\). When \(C^*<1\), the constructed coalition wins and receives payoff strictly below \(1\).
Ignoring block labels during minimization is justified by the task’s permission to select across arbitrary blocks. The imputation requirement is already promised.
Sorting uses \(\mathrm{O}(\tau\log(\tau+1))\) comparisons. Forming capacities and ratios, scanning prefixes, and evaluating the objective use \(\mathrm{O}(\tau)\) rational operations.
The bit-length argument correctly accounts for cumulative denominator growth. In the described product-denominator representations, each input denominator contributes only a bounded number of times, so denominator lengths remain \(\mathrm{O}(L)\). The magnitude bound and \(\log\tau=\mathrm{O}(L)\) likewise keep numerators at \(\mathrm{O}(L)\) bits. The final expression and ratio comparisons retain this bound.
Elementary exact arithmetic consequently supports the claimed \(\mathrm{O}(L^2)\) cost per operation or comparison. The promised-input bound
\[
\mathrm{O}\bigl(L+\tau\log(\tau+1)L^2\bigr)
\]
is valid. Accumulating block quantities and checking the imputation equalities adds \(\mathrm{O}(m+\tau)\) operations, yielding the stated conservative bound
\[
\mathrm{O}\bigl((m+\tau\log(\tau+1))L^2\bigr).
\]
Positive mass in every block implies \(m\le\tau\), and the explicitly listed support implies \(\tau\le L\). Hence this is polynomial in total binary input length, without a restriction on numerical magnitudes.
The cited finite-agent membership result is stated in Theorem 3 of [Chalkiadakis, Elkind, and Jennings](https://comsoc-community.org/assets/proceedings/comsoc-2008/Chalkiadakis.pdf). The prover correctly identifies that partial selection of a cell is permitted here and may fail for indivisible agents. The continuous proof is self-contained and does not apply the finite-agent hardness theorem to the continuous setting.
No additional clarification or 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.