Answer: Existence is \(\mathrm{NP}\)-complete, even for \(\tau=1\). Explicit stable partitions can require \(2^{\Omega(L)}\) output length even for \(\tau=1\) and \(k=3\). Construction is possible in \(2^{\operatorname{poly}(\tau,k,L)}+O(\ell_{\mathrm{out}})\) time, or with polynomial preprocessing using an \(\mathrm{NP}\) oracle followed by \(O(\ell_{\mathrm{out}})\) expansion. Deterministic construction polynomial in input plus output length exists if and only if \(\mathrm{P}=\mathrm{NP}\).
Theorem 3 — class: other
PDF text-layer excerpt — equations and symbol order may be approximateFor games whose preference profiles satisfy the common ranking property, a core stable partition that is also individually stable and contractually individually stable exists. Moreover, we exhibit an algorithm to compute such a partition.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational type masses \(\mu_t\) and an explicitly represented rational piecewise-linear common score \(U(q)\) on feasible nonzero coalition-mass vectors \(0 \le q \le \mu\), decide whether there is a finite list of nonzero rational vectors \(q^1,\ldots,q^r\) with \(\sum_j q^j=\mu\) that is core stable, and output one if it exists. Core stability means there is no nonzero \(b \le \mu\) and decomposition \(b=\sum_j b^j\), with \(0 \le b^j \le q^j\), such that every group supplying positive mass strictly prefers the blocking coalition: \(b^j \ne 0 \Rightarrow U(b)>U(q^j)\).
A society is given by its support: a list of \(\tau\geq 1\) types with positive masses \(\mu_t\in\mathbb{Q}_{>0}\), encoded in binary. Here \(\tau\) is the support size, not the number of possible types; total mass is arbitrary and need not equal \(1\).
A coalition is a vector in \(D=\{q\in\mathbb{R}^{\tau}:0\leq q\leq\mu,\ q\neq 0\}\), with inequalities interpreted coordinatewise. Mass of each type is freely divisible.
The input specifies a continuous piecewise-affine common score \(U:D\to\mathbb{R}\) by \(k\) rational polyhedra covering \(D\), each given by explicit linear inequalities and a rational affine formula; formulas agree on overlaps in \(D\). Scores may have either sign. Every member ranks coalitions by \(U\), with equal scores giving indifference.
A partition is a finite list \(q^1,\ldots,q^r\in D\cap\mathbb{Q}^{\tau}\) satisfying \(\sum_{j=1}^{r}q^j=\mu\); no bound on \(r\) is prescribed.
It is core stable if there do not exist real vectors \(b\in D\) and \(b^1,\ldots,b^r\) satisfying \(b=\sum_{j=1}^{r}b^j\), \(0\leq b^j\leq q^j\), and \(b^j\neq 0\Rightarrow U(b)>U(q^j)\) for every \(j\).
The computational problem is to decide whether such a partition exists and output one whenever it does. Let \(L\) be the total binary input length; state running times in \(\tau,k,L\), and output length where relevant. There is no separate candidate or alternative parameter \(m\).
Is deciding existence of a finite rational core-stable partition in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard? What is the computational complexity of outputting such a partition when one exists?
For finite societies with a common ranking of nonempty coalitions, a core-stable partition that is also individually and contractually individually stable always exists and can be computed. [Suksompong](https://arxiv.org/pdf/1804.03315)
Polynomial-time construction is known for finite common-ranking games represented by explicit lists of individually rational coalitions and their common scores. [Caskurlu and Kizilkaya](https://arxiv.org/pdf/2205.11939)
No verified result located settles the continuous problem specified here.
Deciding existence is \(\mathrm{NP}\)-complete, even when \(\tau=1\). The requirement to output an explicit partition introduces a separate output-size obstruction:
\(\displaystyle 2^{\operatorname{poly}(\tau,k,L)}+O(\ell_{\mathrm{out}})\),
where \(\ell_{\mathrm{out}}\) is the length of the list produced.
Here and below, “polyhedron” has its usual meaning: an intersection of finitely many non-strict linear inequalities.
Existence is not automatic. For example, with one type and \(U(q)=-q\), every coalition is blocked by a smaller part of itself.
Write the input pieces as
\(\displaystyle P_i=\{x:A_i x\leq d_i\}\),
with affine formulas
\(\displaystyle f_i(x)=a_i\cdot x+c_i\),
for \(1\leq i\leq k\).
Consider a partition whose distinct scores, in decreasing order, are
\(\displaystyle s_1>s_2>\cdots>s_h\).
Let
\(\displaystyle R_\ell=\sum_{j:U(q^j)\leq s_\ell}q^j\)
be the total mass in its score level \(\ell\) and all lower levels.
Lemma 1. The partition is core stable if and only if, for every \(\ell\),
\(\displaystyle U(b)\leq s_\ell\quad\text{for every }0\neq b\text{ with }0\leq b\leq R_\ell.\)
Proof. Suppose that \(b\leq R_\ell\) and \(U(b)>s_\ell\). For each coordinate separately, distribute \(b_t\) among the coalitions contributing to \(R_\ell\), without exceeding their available masses. This gives vectors \(b^j\) satisfying all the decomposition requirements. Every participating coalition has score at most \(s_\ell<U(b)\), so \(b\) blocks.
Conversely, suppose that \(b\), decomposed as \(b=\sum_j b^j\), blocks. Let \(s_\ell\) be the largest score of a coalition with \(b^j\neq0\). Then \(U(b)>s_\ell\), and all participating coalitions contribute to \(R_\ell\). Thus \(b\leq R_\ell\), contradicting the displayed condition. \(\square\)
This also gives a polynomial-time verification algorithm, including the exclusion of the zero coalition.
For a piece \(i\), residual \(R\), and threshold \(s\), solve the linear program with variables \(b\) and \(\varepsilon\):
\(\displaystyle \max\varepsilon\)
subject to
\(\displaystyle A_i b\leq d_i,\quad 0\leq b\leq R,\quad 0\leq\varepsilon\leq1,\)
\(\displaystyle \varepsilon\leq\sum_t b_t,\qquad
\varepsilon\leq a_i\cdot b+c_i-s.\)
Its optimum is positive exactly when there is a nonzero \(b\in P_i\) with \(b\leq R\) and \(U(b)>s\). Indeed, such a \(b\) admits a positive \(\varepsilon\); conversely, a feasible positive \(\varepsilon\) guarantees both nonzeroness and strict improvement.
Thus verification uses \(hk\) linear programs, each with \(\tau+1\) variables. Its running time is polynomial in \(\tau,k,L\) and the candidate’s binary length.
The same applies to a multiplicity representation
\(\displaystyle (q^1,n_1),\ldots,(q^g,n_g),\)
where each positive integer \(n_j\), encoded in binary, denotes \(n_j\) copies of \(q^j\). Compute total masses and residuals using \(n_jq^j\); expansion is unnecessary.
Let
\(\displaystyle 0<d_1<\cdots<d_v\leq M\)
be positive rational numbers. Set the single type’s mass to \(\mu=M\), and define
\(\displaystyle U(q)=-\min_{d\in\{0,d_1,\ldots,d_v\}}|q-d|,\qquad 0<q\leq M.\)
This is continuous and piecewise affine, with an explicit representation using \(2v+1\) intervals. Put \(d_0=0\). Between consecutive permitted sizes, its formulas are
\(\displaystyle U(q)=d_i-q\quad\text{on }\left[d_i,\frac{d_i+d_{i+1}}2\right],\)
and
\(\displaystyle U(q)=q-d_{i+1}\quad\text{on }\left[\frac{d_i+d_{i+1}}2,d_{i+1}\right].\)
After \(d_v\), use \(U(q)=d_v-q\).
The formulas agree at every endpoint. On the actual domain, the score is zero exactly at \(d_1,\ldots,d_v\), and negative elsewhere.
Lemma 2. A partition is core stable exactly when every coalition has size in \(\{d_1,\ldots,d_v\}\).
Proof. If a coalition has size \(q\) with \(U(q)<0\), choose
\(\displaystyle 0<\varepsilon<\min\{q,d_1/2,-U(q)\}.\)
Then \(U(\varepsilon)=-\varepsilon>U(q)\), so a part of that coalition blocks.
If every coalition has score zero, blocking would require a positive score. No coalition has one. \(\square\)
Consequently, existence is equivalent to
\(\displaystyle \sum_{i=1}^v n_i d_i=M,\qquad n_i\in\mathbb Z_{\geq0}.\)
We give a direct reduction from the standard \(\mathrm{NP}\)-complete SUBSET SUM problem. Its input consists of positive binary integers \(w_1,\ldots,w_n\) and a nonnegative integer target \(W\). We may assume \(n\geq2\).
Choose an integer
\(\displaystyle B>\max\{n,n\max_i w_i,W\},\)
and put
\(\displaystyle C=B^{n+1}.\)
For each item, introduce two permitted sizes
\(\displaystyle d_i^0=C+B^i,\qquad d_i^1=C+B^i+w_i.\)
Set
\(\displaystyle M=nC+\sum_{i=1}^n B^i+W.\)
All \(2n\) permitted sizes are distinct. They lie below \(2C\), whereas \(M\geq2C\), so they belong to the coalition domain. Their binary lengths are \(O(n\log B)\). The score construction above has \(\tau=1\), \(k=4n+1\), and total encoding length polynomial in the SUBSET SUM input length.
Suppose a partition uses only permitted sizes, and let \(r\) be its number of coalitions. Each size exceeds \(C\), while
\(\displaystyle M<(n+1)C.\)
Therefore \(r\leq n\).
There are no carries among the lower base-\(B\) digits:
Comparing the digit at \(B^{n+1}\) gives \(r=n\). Comparing the digit at each \(B^i\) then shows that exactly one of \(d_i^0,d_i^1\) is used. Finally, the units digit gives
\(\displaystyle \sum_{i:d_i^1\text{ is used}}w_i=W.\)
Conversely, a subset summing to \(W\) supplies a partition: choose \(d_i^1\) for selected items and \(d_i^0\) for the others.
By Lemma 2, this is a polynomial reduction to stable-partition existence. It proves \(\mathrm{NP}\)-hardness with one type. Moreover, every stable partition in the reduction has exactly \(n\) coalitions, each of polynomial binary length.
The unrestricted list length prevents us from proving membership in \(\mathrm{NP}\) merely by guessing the explicit partition. We now establish a short multiplicity representation.
For a nonempty support set \(S\subseteq\{1,\ldots,\tau\}\), define
\(\displaystyle Q_{i,S}=P_i\cap[0,\mu]\cap\{x:x_t=0\text{ for }t\notin S\}.\)
When this set is nonempty, define the fixed value
\(\displaystyle v_{i,S}=\max_{x\in Q_{i,S}}f_i(x).\)
The set is compact, so this maximum exists. It is rational and has polynomial binary length: a linear objective on a nonempty bounded rational polyhedron attains its optimum at a rational vertex, whose coordinates have polynomial encoding length by determinant bounds. This bound is uniform over all \(i,S\).
Consider a score level \(s\) in a stable partition. Let \(R\) be its residual from Lemma 1 and \(S=\{t:R_t>0\}\).
Lemma 3. If \(q\in P_i\) is a coalition at this level and
\(\displaystyle q_t<R_t\quad\text{for every }t\in S,\)
then \(s=v_{i,S}\).
Proof. Since \(q\in Q_{i,S}\), we have \(s\leq v_{i,S}\). If this inequality were strict, choose \(z\in Q_{i,S}\) attaining \(v_{i,S}\). For sufficiently small positive \(\eta\), the vector
\(\displaystyle q_\eta=(1-\eta)q+\eta z\)
is nonzero and lies in \(P_i\cap[0,R]\). The upper bounds hold because \(q_t<R_t\) on every coordinate of \(S\); outside \(S\), both vectors vanish.
By affinity,
\(\displaystyle U(q_\eta)=(1-\eta)s+\eta v_{i,S}>s,\)
contradicting Lemma 1. \(\square\)
Call a level fixed if its score belongs to \(\{v_{i,S}:Q_{i,S}\neq\varnothing\}\), using its current residual support \(S\).
At a level that is not fixed, every coalition must satisfy \(q_t=R_t>0\) for some type \(t\), by Lemma 3. Such a coalition consumes all remaining mass of that type. Two coalitions in the level cannot consume the same type, and that type cannot be consumed again at a later level. Hence the total number of coalitions in levels that are not fixed is at most \(\tau\).
Residual supports form a decreasing chain of nonempty subsets, containing at most \(\tau\) distinct sets. For any one support, fixed levels have at most \(k\) distinct scores. Thus
\(\displaystyle h\leq k\tau+\tau.\)
At each fixed level, assign its coalitions to pieces containing them. Within one assigned piece, replace the coalitions by equally many copies of their average. Convexity preserves piece membership, affinity preserves their common score, and their total vector is unchanged. Therefore every residual is unchanged, so Lemma 1 preserves stability.
There are at most \(k\) groups per fixed level. Together with the at most \(\tau\) other coalitions, the resulting multiplicity representation has at most
\(\displaystyle G=\tau(k^2+1)\)
entries.
A group at a fixed score \(s\), assigned to piece \(i\), has multiplicity \(n\) and aggregate vector \(y\). Its repeated vector is \(y/n\). Include the domain inequalities \(0\leq q\leq\mu\) among that piece’s inequalities. The group conditions are
\(\displaystyle A_i y\leq n d_i,\qquad
a_i\cdot y=n(s-c_i),\qquad y\geq0,\quad y\neq0.\)
Every aggregate satisfies \(y\leq\mu\).
Choose an integer \(H=\operatorname{poly}(\tau,L)\) bounding the numerator and denominator binary lengths of all input coefficients, masses, and values \(v_{i,S}\). Such a uniform bound exists by the determinant argument above. In particular,
\(\displaystyle |a_i\cdot y|\leq\tau2^{2H},\)
and the same bound holds for the absolute value of each row product \(A_i y\).
Set
\(\displaystyle N=\tau2^{4H}+1.\)
If \(s\neq c_i\), then \(|s-c_i|\geq2^{-2H}\), so the score equality gives \(n<N\).
If a row has \(d_{i,j}<0\), its inequality implies
\(\displaystyle n|d_{i,j}|\leq |(A_i y)_j|,\)
and again \(n<N\).
Thus, if an original multiplicity exceeds \(N\), necessarily \(s=c_i\) and every row right-hand side is nonnegative. Replace that multiplicity by \(N\), keeping \(y\) unchanged:
\(\displaystyle Nd_{i,j}\geq\tau2^{3H}\geq |(A_i y)_j|,\)
so its inequality holds.
This replacement preserves the group’s aggregate and score, hence all residuals and stability.
Consequently, every yes-instance has such a representation with
\(\displaystyle 1\leq n_j\leq N.\)
The total number of explicit coalitions is at most \(GN\), which is singly exponential in a polynomial of the input parameters.
It remains to bound the binary lengths of the aggregate vectors and of scores at levels that are not fixed.
Fix the following discrete choices from the representation just obtained:
Membership, score equalities, positivity, strict score ordering, residual supports, and the total-mass equation are then rational linear constraints on aggregate vectors and the remaining score variables.
We must also express stability by linear constraints with polynomial-size coefficients.
For each level and each piece, use the blocking linear program from Section 2. Write its constraints as
\(\displaystyle W_i z\leq h_i(R,s),\)
where \(z=(b,\varepsilon)\). Its matrix \(W_i\) depends only on the input piece; its right-hand side is affine in \(R,s\). Its objective vector \(e\) selects \(\varepsilon\).
Absence of a blocker has one of two certificates:
\(\displaystyle \lambda\geq0,\quad W_i^{\mathsf T}\lambda=0,\quad
\lambda\cdot h_i(R,s)<0.\)
Normalize \(\sum_j\lambda_j=1\). Minimizing the last expression over this compact multiplier polytope gives a vertex with negative value.
\(\displaystyle \lambda\geq0,\quad W_i^{\mathsf T}\lambda=e,\quad
\lambda\cdot h_i(R,s)\leq0.\)
An optimal dual vertex can be chosen: the dual feasible polyhedron lies in a nonnegative orthant and therefore contains no line.
In either case, the chosen multiplier vertex has polynomial binary length by determinant bounds applied to the fixed matrix. Once those rational multipliers are fixed, their inequalities are linear in \(R,s\). There are at most \(hk\) such certificates.
We therefore obtain a feasible rational linear system of polynomial encoding length, allowing strict inequalities. Its continuous variables are bounded: nonnegative aggregates sum to \(\mu\), and each variable score is an affine score of a coalition in \([0,\mu]\).
To obtain a small rational solution, rewrite every strict inequality as \(g(z)>0\), introduce \(0\leq\delta\leq1\), and impose \(g(z)\geq\delta\). The existing solution admits a positive \(\delta\), because there are finitely many strict inequalities. Maximizing \(\delta\) over the resulting compact rational polyhedron gives a positive optimum at a vertex of polynomial binary length.
This vertex supplies polynomial-size rational aggregates and scores. Dividing aggregates by their bounded binary multiplicities gives polynomial-size rational coalition vectors. The fixed certificates guarantee stability.
We have proved that every yes-instance has a polynomial-size multiplicity representation with at most \(G\) entries. Section 2 verifies it in polynomial time. Therefore existence belongs to \(\mathrm{NP}\), completing the proof of \(\mathrm{NP}\)-completeness.
Let \(\tau=1\), \(\mu=1\), and \(a=2^{-h}\), where \(h\geq1\). Use three pieces:
\(\displaystyle U(q)=-q\quad\text{for }0<q\leq a/2,\)
\(\displaystyle U(q)=q-a\quad\text{for }a/2\leq q\leq a,\)
\(\displaystyle U(q)=a-q\quad\text{for }a\leq q\leq1.\)
This is the permitted-size construction with the single permitted size \(a\). Lemma 2 shows that every stable coalition has size \(a\). Thus every stable partition contains exactly
\(\displaystyle 1/a=2^h\)
coalitions.
The input length is \(\Theta(h)\). Hence every explicit stable partition has length \(2^{\Omega(L)}\); under ordinary binary vector encoding its length is \(\Theta(h2^h)\). This obstruction holds even with \(k=3\).
The certificate proof gives a fixed polynomial bound on the length of a successful multiplicity representation. Enumerating all representations up to that bound and applying the polynomial verifier decides existence and finds one in
\(\displaystyle 2^{\operatorname{poly}(\tau,k,L)}\)
time. Expanding the multiplicities then costs \(O(\ell_{\mathrm{out}})\).
Alternatively, the usual witness-prefix search with an \(\mathrm{NP}\) oracle finds a short representation in polynomial time. Expansion again costs \(O(\ell_{\mathrm{out}})\).
If \(\mathrm{P}=\mathrm{NP}\), the same witness search is deterministic polynomial time, yielding a construction polynomial in input plus output length.
Conversely, the reduction in Section 3 has polynomial output length for every stable partition. An algorithm polynomial in input plus output length would therefore solve SUBSET SUM in polynomial time. This remains true for a search algorithm guaranteed to run within such a bound only on yes-instances: run it for the resulting polynomial time bound and verify any proposed partition. Thus output-sensitive polynomial construction would imply \(\mathrm{P}=\mathrm{NP}\).
The finite common-ranking results concern a different setting. Their greedy constructions choose a highest-ranked remaining coalition and terminate because the player set is finite; see [Suksompong, Theorem 3](https://arxiv.org/pdf/1804.03315) and [Caskurlu–Kizilkaya, Theorem 5](https://arxiv.org/pdf/2205.11939). Here freely divisible mass permits arbitrarily small improving coalitions, and finite termination is itself constrained by exact sums of permitted sizes.
⟨structured verdict parsed — rendered above⟩
The argument establishes the claimed \(\mathrm{NP}\)-completeness and construction bounds. I found no major or minor mathematical issues. The polynomial-size certificate argument addresses both potentially unbounded multiplicities and potentially large rational denominators.
In the forward direction of Lemma 1, the coordinatewise decomposition is valid because coalition mass is freely divisible. Every coalition receiving a nonzero contribution belongs to the residual and therefore has score strictly below the blocking coalition’s score.
In the converse direction, a nonzero blocking coalition has at least one participating partition coalition. Thus the largest participating score exists. All participating coalitions belong to the residual associated with that score, which gives the required contradiction.
The criterion correctly handles ties: only strict improvement blocks, and each residual includes every coalition at its threshold score.
A feasible solution with \(\varepsilon>0\) guarantees both \(b\neq0\) and strict score improvement. Conversely, a nonzero improving coalition permits a positive \(\varepsilon\), since both quantities bounding it are positive.
The feasible region is bounded by the residual box and the bounds on \(\varepsilon\). An infeasible program contributes no blocker; Section 4.3 explicitly accounts for this possibility.
Computing scores, checking the partition constraints, sorting score levels, and computing residuals all require polynomial time in the candidate’s binary length. For multiplicity representations, binary multiplication and summation likewise have polynomial bit complexity. Expansion is unnecessary for verification.
The interval formulas represent the negative distance to the designated sizes, including the auxiliary size zero. They agree at midpoints and permitted sizes. Restricting the first closed interval to the actual domain excludes zero, as required.
In Lemma 2, the chosen \(\varepsilon\) lies in the first affine segment and satisfies
\[
U(\varepsilon)=-\varepsilon>U(q).
\]
It is a valid nonzero part of the original coalition. Conversely, a partition whose coalitions all have score zero cannot be blocked because the score function never takes a positive value.
Therefore the equivalence with the nonnegative integer sum equation is exact, despite allowing arbitrary rational coalition sizes initially.
The choice of \(B\) ensures that the weights occupy only the units digit and cannot collide with the identifier digits. The permitted sizes are distinct and belong to the domain. Their binary lengths, the target mass’s binary length, and the piecewise-affine representation all remain polynomial in the source input length.
The inequality \(M<(n+1)C\), together with every permitted size exceeding \(C\), correctly gives \(r\leq n\). Consequently, the stated bounds exclude carries both from the weight contributions and from the identifier coefficients.
The subsequent digit comparisons establish exactly what is claimed: \(r=n\), exactly one size for each item, and selected weights summing to \(W\). The reverse implication supplies a stable partition by Lemma 2.
The reduction also establishes the stronger output-length property: every stable partition contains exactly \(n\) coalitions, each equal to one of the explicitly constructed integers. Thus every such partition has polynomial length under ordinary binary encoding.
Each nonempty \(Q_{i,S}\) is a closed, bounded rational polyhedron. Its affine maximum exists and has polynomial binary length by the stated rational-vertex determinant bounds.
Including zero in this auxiliary polyhedron causes no domain error. Lemma 3 evaluates \(U\) only at nonzero mixtures inside the actual coalition domain; it does not assume that \(U(0)\) is defined.
The strict inequalities \(q_t<R_t\) provide precisely the slack needed for the mixture in Lemma 3 to remain inside the residual box. Convexity preserves piece membership, and affinity gives the strict improvement claimed.
At a nonfixed level, every coalition therefore exhausts at least one residual coordinate. Such exhaustion cannot be shared by another coalition at that level or repeated at a later level. The bound of \(\tau\) on the total number of these coalitions follows.
Residual supports form a decreasing chain with at most \(\tau\) distinct nonempty sets. For each support, there are at most \(k\) possible fixed scores. Hence the bound \(h\leq k\tau+\tau\) is valid.
Averaging within an assigned piece preserves nonzeroness, rationality, piece membership, score, and aggregate mass. Lemma 1 therefore preserves stability. The resulting bound \(G=\tau(k^2+1)\) follows.
The aggregate inequalities are the original coalition inequalities multiplied by a positive integer, so their directions are preserved.
The bound on row products follows from the coefficient and mass bounds. When \(s\neq c_i\), the denominator bound supplies the stated lower bound on \(|s-c_i|\), and the score equality gives \(n<N\). A negative right-hand side likewise forces \(n<N\).
Consequently, a multiplicity exceeding \(N\) can occur only in the identified case \(s=c_i\), with all right-hand sides nonnegative. Replacing that multiplicity by \(N\) preserves the score equality and every zero-right-hand-side constraint. The displayed estimate for positive right-hand sides is sufficient to preserve the remaining inequalities.
The aggregate and score remain unchanged, so the residuals and stability remain unchanged. The new coalition vector remains nonzero and rational. Nonfixed coalitions already have multiplicity one.
After fixing the listed discrete choices and multiplicities, the coalition constraints, score equations, residual conditions, and ordering conditions are linear. In particular, fixing multiplicities removes the potential product between a score variable and a multiplicity variable.
The two stability-certificate cases are valid:
In both cases, the defining matrices have polynomial encoding length and are independent of the unknown residuals and scores. Their multiplier vertices consequently have polynomial binary length. Once fixed, the certificate inequalities are linear in the remaining variables.
The final strict-inequality treatment is also sound. The existing feasible solution satisfies finitely many strict inequalities, so it admits a common positive \(\delta\). Aggregates remain bounded by the mass equation and nonnegativity, while scores remain bounded by their affine score equations. Thus the resulting closed feasible region is compact.
Maximizing \(\delta\) produces a positive rational vertex solution of polynomial binary length. Dividing by the bounded, fixed multiplicities preserves polynomial binary length. The fixed certificates guarantee stability of the resulting partition.
This establishes the polynomial-size witness required for membership in \(\mathrm{NP}\).
The three formulas in Section 5.1 agree at their shared endpoints and have zero score only at \(a\) within the coalition domain. Lemma 2 therefore forces every stable coalition to have size \(a\).
With mass one and \(a=2^{-h}\), every stable partition has exactly \(2^h\) coalitions. The input length is \(\Theta(h)\), and repeating the ordinary binary encoding of \(a\) gives the stated explicit output length \(\Theta(h2^h)\).
The established polynomial witness-length bound permits exhaustive search in \(2^{\operatorname{poly}(\tau,k,L)}\) time. Verification is polynomial, and expansion can be performed in time proportional to the produced list length.
The oracle claim correctly uses witness-prefix search for the polynomially bounded, polynomially verifiable multiplicity representation. Under \(\mathrm{P}=\mathrm{NP}\), that search becomes deterministic polynomial time.
The converse uses the stronger property of the reduction that every successful output has polynomial length. Hence an algorithm polynomial in input plus output length would decide SUBSET SUM in polynomial time. The timeout argument also correctly covers algorithms whose running-time guarantee applies only to yes-instances.
The cited finite results have the stated scope: common-ranking finite games in [Suksompong’s Theorem 3](https://arxiv.org/pdf/1804.03315), and polynomial construction under the explicit individually rational coalition-list representation in [Caskurlu and Kizilkaya’s Theorem 5](https://arxiv.org/pdf/2205.11939). The prover uses these as background, not as an unsupported transfer to the continuous setting.
No repair is required. The output resolves both existence and explicit construction for the specified representation, without introducing a separate candidate parameter or assuming normalized mass, nonnegative scores, or bounded partition length.
⟨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.