Answer: Polynomial-time solvable. Every valid input admits a rational stable partition with at most \(2m-1\) productive compositions, constructible in \(O((\tau\log(2+\tau)+m\tau)L^3)\) bit operations.
Theorem 5 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateLet $N\in{\cal N}$ such that $|N|>\theta$ and $(c,E)\in{\cal P}_{\theta}^{N}$. Consider the coalition formation problem with agent set $N$ induced by $((c,E),CEL)$. Then, the partition obtained by the $\theta$-CEL algorithm is stable.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite set of complete claims types \(T\), rational claims \(c_t>0\), rational shares \(\mu_t\) summing to \(1\), a scale \(H>\theta\), and \(\alpha\in(0,1)\), set \(\rho=\theta/H\). Find a finite-support measure \(\nu\) over productive coalition compositions \(z\in\mathbb{R}_{\ge 0}^{T}\) with \(\sum_t z_t=\rho\), and residual masses \(r_t\ge 0\), such that \(\int z_t\,d\nu(z)+r_t=\mu_t\). For each productive composition \(z\), define its CEL payoff \(u_t(z)=\max(0,c_t-\lambda_z)\), where \(\sum_t z_t u_t(z)=\alpha\sum_t z_t c_t\); residual mass receives payoff \(0\). Let \(A_t(y)=\int z_t\mathbf{1}[u_t(z)<y]\,d\nu(z)+r_t\mathbf{1}[0<y]\). Is there a stable such partition, meaning no composition \(w\ge 0\) with \(\sum_t w_t\ge\rho\) satisfies \(w_t\le A_t(u_t(w))\) for every \(t\)? Construct one or report that none exists.
A society is given by its support: a nonempty list \(T\) of \(\tau\) 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. A type is completely specified by its positive binary-rational claim \(c_t\). Let \(m=|\{c_t:t\in T\}|\).
Inputs also include \(\theta\in\mathbb{Z}_{>0}\), binary-rational \(H>\theta\), and binary-rational \(\alpha\in(0,1)\); set \(\rho=\theta/H\), and let \(L\) be the total input bit length.
For every composition \(v\in\mathbb{R}_{\ge0}^{T}\) with \(\sum_t v_t\ge\rho\), its endowment is \(\alpha\sum_t v_tc_t\), and its CEL payoff is \(u_t(v)=\max\{0,c_t-\lambda_v\}\), where the unique \(\lambda_v\ge0\) satisfies \(\sum_t v_tu_t(v)=\alpha\sum_t v_tc_t\). Smaller coalitions have zero endowment and zero payoffs.
A partition is a finite nonnegative measure \(\nu=\sum_{j=1}^{k}a_j\delta_{z^j}\), with \(a_j>0\), \(z^j\in\mathbb{R}_{\ge0}^{T}\), \(\sum_tz_t^j=\rho\), and residual masses \(r_t\ge0\), satisfying \(\sum_j a_jz_t^j+r_t=\mu_t\). The measure need not be a probability measure; residual mass may be divided among subthreshold coalitions and receives zero.
Define \(A_t(y)=\sum_j a_jz_t^j\mathbf{1}\{u_t(z^j)<y\}+r_t\mathbf{1}\{0<y\}\). Higher payoffs are preferred, equal payoffs are indifferent, and blocking requires strict improvement by every participating agent.
The partition is stable if no \(w\in\mathbb{R}_{\ge0}^{T}\) with \(\sum_t w_t\ge\rho\) satisfies \(w_t\le A_t(u_t(w))\) for every \(t\). These inequalities permit taking any available fraction of a type, including fractions from existing productive coalitions.
The computational problem is to construct a stable partition or report that none exists. Feasibility allows real coordinates; finite outputs use exact real-algebraic encodings, with rational values encoded in binary.
Is this continuous stable-partition problem solvable in polynomial time, or is it NP-hard? State running times in \(m,\tau,L,\theta,H\), accounting for the binary encoding of numerical parameters.
For finitely listed agents with positive claims, positive proportional funding below total claims, and more agents than the integer productivity threshold, CEL admits a stable partition constructible in polynomial time. [Verified discrete result](https://arxiv.org/html/2311.03950v2).
No result settling this exact finite-support mass formulation was located in the literature search.
The problem is solvable in polynomial time. Every valid input admits a stable partition.
A stable partition can be represented using at most \(2m-1\) productive compositions, all with rational coordinates and positive integer coefficients. A conservative bit complexity bound is
\(O\!\left((\tau\log(2+\tau)+m\tau)L^3\right)\),
with output length \(O(m\tau L)\). In particular, the algorithm does not iterate \(\lfloor H/\theta\rfloor\) times.
The construction follows the ordering used by the discrete CEL algorithm in [Theorem 5 of the supplied paper](https://arxiv.org/html/2311.03950v2). The proof below establishes stability directly for divisible masses and fractional blocking.
Write \(\beta=1-\alpha\). For a nonzero nonnegative composition \(v\), define
\(F_v(\ell)=\sum_t v_t\bigl((c_t-\ell)_+-\alpha c_t\bigr)\),
where \(x_+=\max\{0,x\}\). Let \(C_v=\max\{c_t:v_t>0\}\).
We have \(F_v(0)=\beta\sum_t v_tc_t>0\) and \(F_v(C_v)=-\alpha\sum_t v_tc_t<0\). The function is continuous and strictly decreasing on \([0,C_v]\): a type with claim \(C_v\) has positive mass, and its positive-part term strictly decreases throughout this interval. Consequently, \(F_v\) has a unique zero \(\lambda_v\).
Two properties will be useful.
First, for every \(s>0\),
\(F_{sv}(\ell)=sF_v(\ell)\), hence \(\lambda_{sv}=\lambda_v\).
Thus scaling a productive composition while keeping it productive preserves every payoff.
Second,
\(\lambda_v\leq\beta C_v\).
Indeed, for every \(c_t\leq C_v\),
\((c_t-\beta C_v)_+\leq\alpha c_t\).
For \(c_t\leq\beta C_v\), this follows from nonnegativity of \(\alpha c_t\). Otherwise it is equivalent to \(\beta c_t\leq\beta C_v\). Summing gives \(F_v(\beta C_v)\leq0\), proving the bound.
Replacement lemma. Let \(z\) have mass \(\rho\), and put \(C=C_z\). Suppose
\(v=z-b+d\),
where \(0\leq b\leq z\), \(\sum_t d_t=\sum_t b_t\), and every type with \(d_t>0\) has claim at least \(C\). Then \(\lambda_v\geq\lambda_z\).
Proof. Suppose instead that \(\ell=\lambda_v<\lambda_z\). The preceding bound gives \(\ell<\beta C<C\).
Define \(g_\ell(c)=(c-\ell)_+-\alpha c\). Then
\(g_\ell(C)=\beta C-\ell>0\).
For \(c\leq C\), we have \(g_\ell(c)\leq g_\ell(C)\). To check this, if \(c\leq\ell\), then \(g_\ell(c)=-\alpha c<0\); if \(c>\ell\), then \(g_\ell(c)=\beta c-\ell\leq\beta C-\ell\).
For \(c\geq C\), we have \(g_\ell(c)=\beta c-\ell\geq g_\ell(C)\). Therefore,
\(F_v(\ell)-F_z(\ell)=\sum_t d_tg_\ell(c_t)-\sum_t b_tg_\ell(c_t)\geq g_\ell(C)\left(\sum_t d_t-\sum_t b_t\right)=0\).
But \(\ell<\lambda_z\) implies \(F_z(\ell)>0\), whereas \(F_v(\ell)=0\). This contradiction proves the lemma.
The condition on added claims is essential to this argument: they must be at least the original coalition’s maximum claim.
Aggregate types having equal claims. Write the distinct claims as
\(d_1<d_2<\cdots<d_m\),
and define their masses and cumulative masses by
\(M_i=\sum_{t:c_t=d_i}\mu_t,\qquad S_0=0,\qquad S_i=\sum_{h=1}^{i}M_h\).
Represent the society by the interval \([0,1]\), assigning claim \(d_i\) to \([S_{i-1},S_i]\). Endpoints have zero mass and do not affect any composition.
Set
\(N=\lfloor1/\rho\rfloor=\lfloor H/\theta\rfloor\).
For each \(j\in\{1,\ldots,N\}\), take the interval
\(I_j=[(j-1)\rho,j\rho]\).
Its mass of claim \(d_i\) is
\(q_i^j=\max\!\left\{0,\min(S_i,j\rho)-\max(S_{i-1},(j-1)\rho)\right\}\).
Distribute this mass among the original types of that claim proportionally:
\(z_t^j=q_i^j\,\mu_t/M_i\qquad\text{when }c_t=d_i\).
Assign the remaining interval \([N\rho,1]\) to residual mass. Specifically, define
\(R_i=\max\{0,S_i-\max(S_{i-1},N\rho)\}\),
and put \(r_t=R_i\mu_t/M_i\) for \(c_t=d_i\).
Each \(z^j\) has mass \(\rho\), and the construction satisfies
\(\sum_{j=1}^{N}z_t^j+r_t=\mu_t\).
Moreover,
\(\sum_t r_t=1-N\rho<\rho\).
Thus \(\sum_{j=1}^{N}\delta_{z^j}\), together with \(r\), is a feasible partition. Its residual mass is itself subthreshold.
The decisive ordering property is this: if \(C_j=\max\{c_t:z_t^j>0\}\), then every claim appearing in a later block, or in the residual, is at least \(C_j\). This follows directly from the increasing claim order along \([0,1]\).
At this stage the construction is conceptual; Section 4 computes its compressed representation without enumerating all \(N\) blocks.
Suppose the constructed partition has a blocking composition \(w\) of mass at least \(\rho\).
Replace \(w\) by \(\rho w/\sum_t w_t\). Its loss parameter and payoffs remain unchanged by scaling, and its coordinates only decrease. Hence it still satisfies the blocking inequalities. We may therefore assume
\(\sum_t w_t=\rho\).
For each type, the available mass is a finite sum of contributions from productive blocks and residual mass. The inequalities defining blocking consequently allow a decomposition
\(w=\sum_{j=1}^{N}p^j+p^r\),
where \(0\leq p^j\leq z^j\) and \(0\leq p^r\leq r\), with these additional properties:
Such a decomposition can be obtained separately for each type by taking its required mass from the eligible contributions until its coordinate of \(w\) is filled.
Since residual mass totals less than \(\rho\), some productive block contributes positive mass. Let \(j\) be the earliest such block.
Choose a type with \(p_t^j>0\). Strict improvement gives
\((c_t-\lambda_w)_+>(c_t-\lambda_{z^j})_+\),
which implies \(\lambda_w<\lambda_{z^j}\): if the opposite inequality held, the positive-part payoff could not increase.
On the other hand, write
\(w=z^j-b+d\),
where
\(b=z^j-p^j,\qquad d=\sum_{h>j}p^h+p^r\).
There are no contributions from earlier blocks by the definition of \(j\). Both \(w\) and \(z^j\) have mass \(\rho\), so \(b\) and \(d\) have equal total mass. Every claim appearing in \(d\) is at least \(C_j\), by the ordering property.
The replacement lemma therefore implies
\(\lambda_w\geq\lambda_{z^j}\),
contradicting strict improvement. Thus the constructed partition is stable.
This proof permits arbitrary participating fractions from every existing coalition, exactly as required by the stated blocking definition.
Call a block *mixed* if it contains positive masses of at least two distinct claims. Every mixed block contains some boundary \(S_i\), with \(1\leq i<m\), strictly inside it. Each boundary lies strictly inside at most one block. Hence there are at most \(m-1\) mixed blocks.
Their indices are precisely the distinct values
\(j=\lfloor S_i/\rho\rfloor+1\)
for boundaries satisfying \(S_i/\rho\notin\mathbb Z\) and \(j\leq N\). Compute these indices, deduplicate them, and calculate their compositions using the intersection formula above. Give each coefficient \(1\).
All other productive blocks are homogeneous. For claim \(d_i\), their number is
\(h_i=\max\!\left\{0,\min\!\left(N,\lfloor S_i/\rho\rfloor\right)-\lceil S_{i-1}/\rho\rceil\right\}\).
Indeed, a block of index \(j\) lies wholly in the claim interval exactly when
\((j-1)\rho\geq S_{i-1},\qquad j\rho\leq S_i,\qquad j\leq N\).
The displayed formula counts precisely these integers.
If \(h_i>0\), output one composition defined by
\(z_t^{(i)}=\rho\,\mu_t/M_i\quad\text{for }c_t=d_i\),
with all other coordinates zero, and coefficient \(a_i=h_i\).
There are at most \(m\) such homogeneous compositions. Together with the mixed ones, this gives at most \(2m-1\) productive compositions.
Combining identical homogeneous blocks preserves both the feasibility equations and every availability function \(A_t\): coefficient \(h_i\) accounts for exactly the mass of the \(h_i\) identical blocks. Thus the compressed partition is stable as well.
Sorting and aggregating the \(\tau\) listed types uses \(O(\tau\log(2+\tau))\) comparisons and arithmetic operations.
Thereafter:
Since \(m\leq\tau\), the total is
\(O(\tau\log(2+\tau)+m\tau)\)
exact arithmetic operations.
All intermediate reduced rationals have \(O(L)\) bits. To justify this bound, a common denominator for the input masses can be chosen as the product of their denominators; its bit length is bounded by their total input length. Prefix sums therefore have \(O(L)\)-bit numerators and denominators. Each subsequent formula uses only a bounded number of arithmetic operations on these sums, \(\rho\), block indices, and input masses. Also,
\(\log(2+N)=O(\log(2+H/\theta))=O(L)\).
Using elementary integer arithmetic and rational reduction gives the conservative bit complexity
\(O\!\left((\tau\log(2+\tau)+m\tau)L^3\right)\).
The dense output has \(O(m\tau)\) rational coordinates, each of \(O(L)\) bits, so its length is \(O(m\tau L)\). Rational output already satisfies the permitted exact real-algebraic encoding requirement.
The construction depends on the numerical parameters \(\theta,H\) only through \(\rho=\theta/H\); their encoding lengths are included in \(L\). It uses neither a loop of length \(H/\theta\) nor a discretization into finitely many agents. It also requires no payoff computations involving \(\alpha\): the same ordered construction is stable for every \(\alpha\in(0,1)\).
Every valid instance admits the rational stable partition constructed above, and its compressed representation is computable in polynomial time in the binary input length.
⟨structured verdict parsed — rendered above⟩
The prover resolves the continuous problem in substance: its construction yields a stable partition for every valid input, with the stated polynomial bit complexity. I found one minor omission in the replacement lemma’s formal hypotheses. There are no blocking issues.
The construction addresses the specified finite-support mass formulation. It allows arbitrary real blocking compositions, participating fractions from existing coalitions, repeated claims, and coefficients whose sum need not equal one.
The reference to the discrete algorithm is accurate: [Theorem 5 of the supplied paper](https://arxiv.org/html/2311.03950v2) establishes stability for its discrete CEL construction, which successively groups lowest-claim agents. The prover does not apply that theorem to continuous masses; Sections 1–3 supply a separate argument. Consequently, no transfer of discrete hypotheses to the continuous setting is needed.
The endpoint evaluations of \(F_v\) are correct. Positivity of claims, nonzero nonnegative \(v\), and \(0<\alpha<1\) give the stated strict signs.
Strict decrease on \([0,C_v]\) is justified: a positive-mass type attaining \(C_v\) has a strictly decreasing positive-part term throughout that interval, and all other terms are nonincreasing. Continuity and the endpoint signs therefore establish a unique zero in \((0,C_v)\). Beyond \(C_v\), the function remains strictly negative, so there are no additional nonnegative zeros.
The scaling identity is correct. Its application to payoffs is restricted to compositions that remain productive, as required.
The bound \(\lambda_v\leq\beta C_v\) also checks out. The pointwise inequality holds for every claim in the support of \(v\); zero-mass types do not affect the sum. Monotonicity then gives the asserted bound.
Under the intended interpretation that \(d\) is nonnegative added mass, the argument is correct:
Minor issue: The lemma explicitly requires \(0\leq b\leq z\), but does not explicitly require \(d\geq0\). Its proof treats \(d\) as nonnegative added mass.
Minimum clarification: Add \(d\in\mathbb{R}_{\geq0}^{T}\) to the lemma’s hypotheses. This is an expositional clarification: the later application defines \(d\) as a sum of nonnegative participation vectors and already satisfies it.
The condition involving the original coalition’s maximum claim is correctly stated and is satisfied in the application.
All aggregated masses \(M_i\) are positive, so proportional allocation among original types is well-defined. Aggregation is legitimate because equal-claim types have identical CEL payoffs within every composition.
The interval-intersection formula correctly calculates \(q_i^j\). Each productive interval lies in \([0,1]\) and has length \(\rho\), so every \(z^j\) has total mass \(\rho\).
The residual formula correctly calculates the intersection of each claim interval with \([N\rho,1]\). Together, the productive intervals and residual interval account for each original type’s entire mass. Endpoints have zero mass and introduce no overlap in these calculations.
Since \(0<\rho<1\), \(N\geq1\). The residual total satisfies
\(0\leq1-N\rho<\rho\), including zero residual when \(1/\rho\) is integral.
The ordering property is correct. Every positive-mass claim in a later block or the residual is at least the maximum positive-mass claim in an earlier block. Equality is allowed when a claim interval crosses a block boundary.
Every step of the blocking argument is valid.
Thus the argument excludes all blockers permitted by the task, including those taking arbitrary fractions from multiple productive coalitions.
The bound on mixed blocks is correct. Every mixed block contains an internal claim boundary, and each boundary is strictly interior to at most one block. Hence there are at most \(m-1\) mixed blocks.
The mixed-block index formula handles both relevant edge cases correctly:
Deduplication correctly handles several claim boundaries inside one block.
The homogeneous-block count also checks out. Its admissible indices satisfy
\(j\geq\lceil S_{i-1}/\rho\rceil+1\) and
\(j\leq\min(N,\lfloor S_i/\rho\rfloor)\), giving exactly the displayed count after truncation at zero.
Homogeneous blocks of one claim have identical original-type compositions. Replacing them by one atom with coefficient \(h_i\) preserves both assigned masses and every availability function. Stability therefore survives compression.
The bound \(2m-1\) includes \(m=1\), where there are no mixed blocks and one homogeneous composition suffices.
The arithmetic-operation bound is justified. The mixed-boundary indices are nondecreasing in boundary order, so deduplication can be done by a linear scan. Computing mixed compositions costs \(O(m^2)\), which is absorbed by \(O(m\tau)\) because \(m\leq\tau\).
The \(O(L)\) bit-size claim is supported by the formulas:
Elementary exact rational arithmetic with reduction therefore supports the conservative bound
\(O((\tau\log(2+\tau)+m\tau)L^3)\).
The dense rational output has length \(O(m\tau L)\), including coefficients and residual coordinates.
There is no enumeration of all \(N\) conceptual blocks in the implemented construction. The dependence on \(\theta,H\) is through \(\rho\) and binary encoding lengths. The proof also supports the asserted independence of the construction from \(\alpha\), throughout its required domain.
No mathematical repair or further lemma is needed. The only requested clarification is the explicit nonnegativity hypothesis for \(d\).
⟨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.