Answer: Polynomial-time solvable in \(m,\tau,k,L\) under the standard binary-rational encoding of resource weights.
Theorem 8 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven a TTG G = (N; w; t) and an outcome (CS, x) of the corresponding OCF game ˇG, it is strongly coNP-complete to decide whether (CS, x) is in the r-core of ˇG.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite type set \(A\), rational masses \(\mu\), per-agent weights \(w_a\), rational task types \(t_j=(T_j,u_j)\), and a finite-support outcome \(\mathcal O\) assigning each type a complete contribution/payoff signature across named old streams, decide whether a measurable deviating submass \(q_a\le\mu_a\), possibly partitioned across deviation patterns, can form or modify overlapping task streams with feasible resource and threshold constraints such that nondeviators preserve their contributions and each deviating unit keeps an old stream's payoff exactly when its contribution there is unchanged, while every deviating unit receives strictly higher payoff.
A society is given by its support: a list of \(\tau\) types \(a\in A\) with positive binary-rational masses \(\mu_a\); \(\tau\) is the support size, not the number of possible types. Realize type \(a\) as an atomless interval of length \(\mu_a\), with resource weight \(w_a>0\) per unit of mass; masses need not sum to one.
There are \(m\ge1\) task types with binary-rational thresholds and utilities satisfying \(0<T_1<\cdots<T_m\) and \(0\le u_1<\cdots<u_m\). Arbitrarily many copies of each task type are available.
A coalition structure is a finite list of streams with measurable contribution fractions \(r_\ell(z)\ge0\), satisfying \(\sum_\ell r_\ell(z)\le1\) almost everywhere. Stream \(\ell\) has resource \(R_\ell=\int w(z)r_\ell(z)\,dz\) and value \(V(R_\ell)=\max(\{0\}\cup\{u_j:T_j\le R_\ell\})\); each stream earns this fixed value, without fractional task completion.
An outcome assigns integrable real payoff densities \(x_\ell(z)\), with \(x_\ell(z)=0\) where \(r_\ell(z)=0\), \(\int x_\ell(z)\,dz=V(R_\ell)\), and nonnegative total payoff almost everywhere. Transfers occur only within streams; individual rationality uses the zero value attainable by an atomless singleton.
The input is a feasible outcome \(\mathcal O\) with \(k\) named old streams, specified by binary-rational contribution and payoff densities constant on each type. Types therefore include their complete old contribution/payoff signatures; \(L\) is the total input bit length.
A deviation chooses a measurable set \(D\) of positive mass, with type submasses \(0\le q_a\le\mu_a\), and another feasible finite-stream outcome. Members of a type may follow different measurable deviation patterns.
The old and new streams involving positive nondeviator contribution must admit a bijection preserving every nondeviator's contribution almost everywhere; all remaining new streams involve deviators only. Deviators may decrease or increase contributions, subject to their resource budgets.
For each matched pair, every deviator retains exactly its old payoff density if the entire stream contribution profile is unchanged almost everywhere; otherwise every deviator receives zero from that matched stream. Payoffs on streams involving only deviators may be redistributed freely. Nondeviator payoffs need only satisfy outcome feasibility.
A deviation is profitable when each deviating unit receives strictly higher total payoff almost everywhere on \(D\).
Is deciding whether such a profitable deviation exists solvable in time polynomial in \(m,\tau,k,L\), or is it NP-hard?
For finitely many agents, refined-core membership is strongly coNP-complete, equivalently profitable-deviation existence is strongly NP-complete ([verified result](https://arxiv.org/pdf/1401.3856)).
No result settling this exact atomless, support-encoded decision problem was identified in the literature search.
Profitable-deviation existence is polynomial-time solvable in \(m,\tau,k,L\).
I use the standard bit-model interpretation that the resource weights \(w_a\) are rational input numbers. Without an encoding for these weights, a bit-complexity question is not defined.
The key fact is that failure of one particular deviation test forces every positive old stream to operate at the same maximal utility per unit of resource. After that, testing deviations that release at most two old streams suffices.
Write \(r_{\ell a}\) and \(x_{\ell a}\) for the old contribution and payoff densities. Define
\(p_a=\sum_{\ell=1}^{k}x_{\ell a}\),
\(W=\sum_a\mu_aw_a\),
\(R_\ell=\sum_a\mu_aw_ar_{\ell a}\), and
\(P=\sum_a\mu_ap_a=\sum_\ell V(R_\ell)\).
Feasibility gives \(p_a\geq0\).
For nonnegative resource and cost densities \(c_a,y_a\), with \(y_a=0\) whenever \(c_a=0\), define
\(C_{c,y}(t)=\min\left\{\sum_a y_aq_a:\ 0\leq q_a\leq\mu_a,\ \sum_a c_aq_a=t\right\}\).
Set this minimum to infinity when \(t>\sum_a\mu_ac_a\).
This calculation is polynomial-time solvable. For each type with \(c_a>0\), its available resource is \(\mu_ac_a\), at cost \(y_a/c_a\) per resource unit. Sort these ratios, take resource from types in that order, and use a fraction of the final type.
To justify optimality, suppose an allocation uses resource from a more expensive type while a cheaper type still has unused capacity. Moving an equal amount of resource from the former to the latter preserves feasibility and cannot increase cost. Repeating this exchange gives the stated allocation.
We will use
\(C_{\mathrm{all}}(t)=C_{w,p}(t)\).
For a set \(S\) of old streams, we will also use
\(c_a^S=w_a\sum_{\ell\in S}r_{\ell a}\),
\(y_a^S=\sum_{\ell\in S}x_{\ell a}\), and
\(C_S(t)=C_{c^S,y^S}(t)\),
after establishing that the old stream payoff densities are nonnegative.
If \(C_{\mathrm{all}}(T_j)<u_j\), a profitable deviation exists.
Take a minimizing vector \(q\), and select measurable subintervals of these masses as the deviating set \(D\). Every deviator withdraws from every old stream and contributes fully to one new stream. Its resource is exactly \(T_j\), so its value is \(u_j\).
Let \(M_D=\sum_aq_a>0\). Give each deviating unit of type \(a\) the new payoff density
\(p_a+\varepsilon\), where
\(\varepsilon=\left(u_j-\sum_ap_aq_a\right)/M_D>0\).
These payoffs integrate to \(u_j\), and every deviator strictly improves.
For each old stream with positive nondeviator contribution, preserve those contributions and give its entire resulting value to its nondeviating contributors, using nonnegative densities. Remove old streams without nondeviator contribution. This respects the required matching. If an old profile happens to remain unchanged, its old contribution on \(D\) was zero, and therefore its old payoff on \(D\) was also zero. The retention rule is consequently satisfied.
Suppose all old stream payoff densities are nonnegative. If \(C_S(T_j)<u_j\), a profitable deviation exists.
Choose \(D\) from a minimizing vector \(q\), omitting types with \(c_a^S=0\). On \(D\), withdraw from streams in \(S\), preserve contributions and payoffs on all other old streams, and contribute
\(\sum_{\ell\in S}r_{\ell a}\)
to one new deviator-only stream. This fraction respects every unit’s budget. The new stream has resource \(T_j\).
Give each deviator its lost payoff density \(y_a^S\), plus the positive uniform increment
\(\varepsilon=\left(u_j-\sum_ay_a^Sq_a\right)/M_D\).
Together with its retained payoffs, its new total payoff is \(p_a+\varepsilon\).
Nondeviator feasibility requires checking both kinds of old streams:
If an unchanged stream has no nondeviating contributors, retain it as a deviator-only stream with its original payoffs. Thus every required stream and payoff constraint is satisfied.
These constructions use at most \(k+1\) new streams.
Consider the task types with \(T_j\leq W\), and let
\(\delta=\max_{j:T_j\leq W}u_j/T_j\).
If no attainable task has positive utility, every feasible outcome has total value zero. Its nonnegative total payoff density must therefore be zero almost everywhere, so no profitable deviation exists.
Assume henceforth that \(\delta>0\). Choose an attaining task with smallest threshold, denoted \(t_*\). Its utility is \(\delta t_*\).
Every old stream satisfies \(V(R_\ell)\leq\delta R_\ell\). Consequently,
\(P\leq\delta\sum_\ell R_\ell\leq\delta W\).
The uniformly selected submasses \(q_a=(t_*/W)\mu_a\) are feasible in the definition of \(C_{\mathrm{all}}(t_*)\). Hence
\(C_{\mathrm{all}}(t_*)\leq(t_*/W)P\leq\delta t_*\).
If the first inequality test detects \(C_{\mathrm{all}}(t_*)<\delta t_*\), Section 2 supplies a profitable deviation.
Otherwise all these bounds are equalities. In particular,
\(P=\delta W\),
\(\sum_\ell R_\ell=W\), and
\(V(R_\ell)=\delta R_\ell\) for every old stream.
Since all contribution fractions are nonnegative and their sum is at most one, equality of the total resource implies
\(\sum_\ell r_{\ell a}=1\)
for every type \(a\).
Discard zero-resource streams; they have zero contributions and hence zero payoff densities. Let \(\kappa\) be the number of remaining streams.
Every remaining stream has positive value and resource at least \(t_*\). Indeed, if its value is \(u_j\), then
\(u_j=\delta R_\ell\), \(T_j\leq R_\ell\), and \(u_j/T_j\leq\delta\).
These relations force \(R_\ell=T_j\) and \(u_j/T_j=\delta\). The definition of \(t_*\) gives \(R_\ell\geq t_*\).
Under the conclusions of Section 3, suppose \(x_{\ell a}<0\).
Choose a sufficiently small positive submass \(q<\mu_a\) of type \(a\). These deviators withdraw only from stream \(\ell\), retaining their contributions and old payoffs on every other stream. Their new total payoff density is
\(p_a-x_{\ell a}>p_a\).
Every remaining old stream still has nondeviating contributors: the deviating set is a proper submass of one type.
For an unchanged stream \(h\), choose \(q\) small enough that \(q x_{ha}\leq V(R_h)\) whenever \(x_{ha}>0\). This is possible because there are finitely many streams and each has positive value. Its value remaining after retained deviator payments is then nonnegative. Allocate that remainder nonnegatively to nondeviators. On the changed stream, allocate its resulting value nonnegatively to nondeviators.
The deviators’ total payoffs are nonnegative and strictly improved. Thus any negative old stream payoff density is a polynomial-time recognizable certificate of a profitable deviation.
We may therefore assume below that \(x_{\ell a}\geq0\) for every remaining stream and type.
Consider an arbitrary profitable deviation, allowing different measurable patterns within each type.
Let \(U\) contain the old streams matched to new streams whose entire contribution profiles are unchanged. Let \(S\) be the complementary set of positive old streams. In particular, old streams having no nondeviating contributors belong to \(S\).
Write \(q_a\) for the deviating submasses and define
\(H=\sum_ac_a^Sq_a\), and
\(Y=\sum_ay_a^Sq_a\).
Every deviator retains exactly its old payoff from \(U\), and receives zero from changed matched streams. Let \(B\) be the total value of the new deviator-only streams. Since all their payoffs go to deviators, integrating strict improvement gives
\(B>Y\).
Here strict improvement almost everywhere on a set of positive mass implies a strictly positive integral: an integrable function positive almost everywhere on such a set cannot have integral zero.
Original resource budgets are saturated by Section 3. Preserving contributions on \(U\) leaves at most resource \(H\) for the deviator-only streams; contributions to changed matched streams can only reduce that amount.
List the positive-valued deviator-only streams, and let \(j_\nu\) be the task type giving stream \(\nu\) its value. Then
\(B=\sum_\nu u_{j_\nu}\), and
\(\sum_\nu T_{j_\nu}\leq H\).
In particular, \(H>0\). There must be some \(\nu\) satisfying
\(u_{j_\nu}>(T_{j_\nu}/H)Y\).
Otherwise summing the reverse inequalities would give \(B\leq Y\).
For this task, the vector
\(q'_a=(T_{j_\nu}/H)q_a\)
satisfies \(0\leq q'_a\leq\mu_a\), has resource exactly \(T_{j_\nu}\) under \(c^S\), and costs \((T_{j_\nu}/H)Y\). Therefore,
\(C_S(T_{j_\nu})<u_{j_\nu}\).
Thus any profitable deviation with released set \(S\) implies one of the single-task tests for that same set. This argument uses only the type submasses, so it covers arbitrary measurable within-type deviation patterns.
For each positive old stream define its imbalance vector by
\(d_{\ell a}=x_{\ell a}-\delta w_ar_{\ell a}\).
Take two streams \(i,h\), and put \(S=\{i,h\}\). Their combined resource is
\(R_S=R_i+R_h\geq2t_*>t_*\),
and their combined payoff is \(\delta R_S\).
Suppose \(d_i+d_h\neq0\). Equivalently, \(y^S\neq\delta c^S\). Since their total payoff equals \(\delta\) times their total resource, there are types \(a,b\) with positive \(c_a^S,c_b^S\) such that
\(y_a^S/c_a^S<\delta<y_b^S/c_b^S\).
Start with \(q_a=\theta\mu_a\), where \(\theta=t_*/R_S\in(0,1)\). This selects resource \(t_*\) at cost \(\delta t_*\).
Move resource amount \(\eta\) from type \(b\) to type \(a\), replacing their submasses by
\(q_a+\eta/c_a^S\), and
\(q_b-\eta/c_b^S\).
Choose
\(0<\eta<\min\{(1-\theta)\mu_ac_a^S,\theta\mu_bc_b^S\}\).
The new submasses remain feasible, resource is unchanged, and cost decreases by the positive amount
\(\eta(y_b^S/c_b^S-y_a^S/c_a^S)\).
Consequently,
\(C_S(t_*)<\delta t_*\),
which is a profitable-deviation test from Section 2.
Suppose \(\kappa\geq3\) and every pair test fails. The preceding argument gives
\(d_i+d_h=0\)
for every pair of distinct streams.
For any three distinct streams, these equations imply all three imbalance vectors are zero: the first two pair equations give \(d_h=d_j=-d_i\), and the third gives \(-2d_i=0\). Pairing with these streams then gives \(d_\ell=0\) for every remaining stream.
Thus
\(x_{\ell a}=\delta w_ar_{\ell a}\)
for every stream and type.
For any arbitrary released set \(S\), this implies \(Y=\delta H\). Every new stream has value at most \(\delta\) times its resource, so the notation of Section 5 gives
\(B\leq\delta H=Y\),
contradicting the strict improvement requirement \(B>Y\). No profitable deviation exists.
If \(\kappa\leq2\), every possible nonempty released set already has size at most two. Section 5 therefore proves directly that failure of all its single-task tests excludes every profitable deviation.
The empty released set cannot yield a deviation: unchanged old contributions exhaust the deviators’ budgets, leaving no resource for deviator-only streams and no change in their payoffs.
The complete algorithm is:
Sections 2 and 4 prove soundness of every affirmative answer. Sections 3, 5, and 6 prove completeness of every negative answer.
There are \(O(k^2)\) stream sets. For each, sort at most \(\tau\) resource-price ratios once; then evaluate the cost function at the already ordered \(m\) thresholds using cumulative capacities and costs. This requires \(O(k^2(\tau\log\tau+m+\tau))\) rational arithmetic operations, in addition to reading and preparing the input. All intermediate numbers have polynomial bit length, so the bit complexity is polynomial in \(m,\tau,k,L\).
The supplied finite-agent hardness result therefore does not extend to this atomless model. The decisive operation is selecting a common fractional submass of every type, followed by small resource-preserving exchanges between types.
⟨structured verdict parsed — rendered above⟩
The argument is sound under its explicitly stated assumption that the resource weights are binary-rational input numbers. I found no major mathematical gap or false step. The only minor qualification concerns the input encoding, which the task leaves unspecified for the weights.
The calculation of \(C_{c,y}(t)\) is correct for the nonnegative densities used in the proof.
For a type with \(c_a>0\), the substitution of resource quantity for selected mass gives capacity \(\mu_a c_a\) and price \(y_a/c_a\). The stated exchange argument correctly establishes that selecting resource in increasing price order minimizes cost. Ties do not affect optimality, and fractional selection of the final type is permitted by atomlessness.
Types with \(c_a=0\) have \(y_a=0\) under the stated hypothesis and can be omitted. Thresholds exceeding total capacity correctly have cost infinity.
The applications meet these hypotheses:
Both constructions are valid.
Abandoning all old participation. A minimizing selection at positive threshold has positive mass. Its selected old payoff is strictly below the new stream’s value, so the stated uniform increment is positive and the new payments integrate to exactly that value.
Every retained old stream has positive nondeviator contribution and can allocate its resulting nonnegative value among those contributors. Old streams without nondeviator contribution may be removed.
The retention-rule check is correct: if withdrawing the deviators leaves an old contribution profile unchanged, those deviators previously contributed zero to that stream almost everywhere. Its old payoff density on them was therefore also zero.
Releasing a specified set. The new contribution fraction is exactly the sum withdrawn from the selected streams, so individual contribution budgets remain satisfied. The new stream’s resource is the tested threshold.
The payment construction replaces each deviator’s lost payoff and adds a positive increment. Because old stream payoff densities are nonnegative, retaining deviator payments on an unchanged stream never exceeds its total value. Changed streams assign deviators zero, as required.
An unchanged old stream wholly contained in the deviating set may be retained as a deviator-only stream with its original contributions and payments. This respects feasibility and does not require matching it to a stream with nondeviator contribution.
The bound of at most \(k+1\) new streams is correct.
The definition of \(\delta\) uses only attainable tasks. This suffices because every old or new stream has resource at most the society’s total resource \(W\).
If no attainable task has positive utility, every feasible outcome has total value zero. Its nonnegative total payoff density must then vanish almost everywhere. Strict improvement on a positive-mass set is impossible. This also covers the case in which no task is attainable.
For positive \(\delta\), the bounds
\[
P\leq\delta\sum_\ell R_\ell\leq\delta W
\]
are valid. The uniformly selected submasses are feasible because \(0<t_*\leq W\).
If the strict test fails, the displayed chain of inequalities indeed forces equality throughout. Consequently:
The last conclusion follows from positive masses and weights and the nonnegative slack in each type’s budget.
Zero-resource streams have zero contributions and consequently zero payoff densities. Every remaining stream has positive value. The inequalities involving its attained task force its resource to equal that task’s threshold and its utility-to-threshold ratio to equal \(\delta\). Its resource is therefore at least \(t_*\).
No unjustified equality or domain restriction occurs here.
This deviation construction is correct.
A negative payoff density implies positive old contribution to that stream. Withdrawing a positive submass therefore changes its profile, so assigning those deviators zero from that matched stream complies with the rule.
Choosing a proper submass of one type leaves nondeviating contributors in every positive old stream. For each unchanged stream, the stated smallness condition ensures that retained deviator payments do not exceed its positive value. Negative retained payments cause no obstruction, since only total payoff must be nonnegative.
The deviators’ new total payoff is \(p_a-x_{\ell a}>p_a\geq0\). Nondeviator payments can be chosen nonnegative. Thus the affirmative test is sound.
This necessity argument correctly handles arbitrary measurable deviation patterns within a type.
The partition into \(U\) and \(S\) is appropriate. Old streams without nondeviator contribution belong to \(S\), even if a deviator-only replacement preserves their old profile. Their replacement values are then included in \(B\).
Integrating strict improvement gives \(B>Y\): unchanged matched streams retain exactly the old deviator payments, changed matched streams give deviators zero, and all payments from deviator-only streams integrate to their total value.
The resource bound is also valid. Original budgets are saturated, and contributions to \(U\) remain unchanged. Hence the resource available for deviator-only streams is at most \(H\), regardless of how deviators redistribute contributions elsewhere.
The extraction of a task with
\[
u_{j_\nu}>(T_{j_\nu}/H)Y
\]
is correct. Here the already established nonnegativity of old stream payoff densities supplies \(Y\geq0\), which is needed when using the bound on the sum of thresholds.
The scaling factor lies in \((0,1]\), so the scaled submasses satisfy their capacity bounds. Their resource and cost are exactly those stated. The resulting strict single-task test follows.
The pair argument is correct.
The combined resource exceeds \(t_*\), so the uniform selection lies strictly inside every positive resource capacity. Nonzero combined imbalance, together with equality of aggregate payoff and \(\delta\) times aggregate resource, supplies both a price below \(\delta\) and a price above it.
The stated upper bound on \(\eta\) is positive and preserves both selected-mass bounds. The resource remains unchanged, and the displayed cost decrease has the correct sign. Thus a nonzero pair imbalance yields a profitable-deviation test.
For at least three streams, failure of every pair test forces every pairwise imbalance sum to vanish. The ensuing vector algebra correctly forces each imbalance vector to be zero.
Then every released set has \(Y=\delta H\), while the resource and value bounds give \(B\leq\delta H\). This contradicts the necessary strict inequality.
For one or two positive streams, every nonempty released set is already tested. The empty released set cannot support strict improvement because unchanged contributions exhaust the deviators’ budgets and retain their old payments.
These cases exhaust the possibilities.
The affirmative answers are justified by explicit feasible constructions. The negative answers are justified by the efficiency reduction, the arbitrary-deviation necessity argument, and the pair analysis.
The number of tested sets is quadratic in \(k\). Sorting resource prices once per set and scanning the ordered thresholds gives the stated arithmetic-operation bound, apart from the separately acknowledged input preparation.
Under binary-rational encoding of the weights, all quantities are formed through polynomially many sums, products, divisions, and comparisons of input rationals. The particular quantities used here have polynomial bit length. Thus the polynomial bit-complexity claim is justified.
The atomless fractional selections and exchanges used in the argument are permitted by the task. They do not establish a corresponding finite-agent algorithm, so there is no contradiction with the supplied finite-agent hardness result.
Minor — encoding of resource weights. The task specifies positive weights but does not explicitly specify their encoding. The prover supplies the natural binary-rational interpretation and states this assumption openly. The mathematical argument is valid under that interpretation.
The minimum clarification is to add to the task that each weight is a positive binary-rational input number whose encoding length is included in \(L\). No mathematical repair is otherwise 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.