Answer: —
Theorem 18 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven a symmetric additively separable hedo- nic graph game whose underlying graph is a star, it is PLS-complete to find an in-neighbor stable feasible partition. PROOF SKETCH. With symmetric additively separable prefer- ences, we are able to test local optimality of a partition and, if it is not optimal, find an improving move in polynomial time. Hence, our problem is clearly in PLS. To prove PLS-hardness, we provide a reduction from LOCAL MAX-CUT, which is known to be PLS- complete [21].
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite types \(T=\{s\}\cup V\), rational masses \(\mu_t\ge0\) with \(\sum_t\mu_t=1\), a star communication graph \(H\), and a symmetric rational utility matrix \(U\), find a measurable partition into coalitions whose type supports are connected in \(H\), with every individual assigned to one coalition, such that no positive infinitesimal mass of type \(t\) can move between coalitions, strictly improve its utility, and be accepted by every destination neighbor \(r\) satisfying the marginal condition \(U(r,t)\ge0\).
A society is given by its support: \(T=\{s\}\cup V\), the list of its \(\tau\) positive-mass types, with binary rational masses \(\mu_t>0\) summing to \(1\). Here \(m=|V|\) and \(\tau=m+1\); support size means listed types, not possible types. Let \(L\) be the total input bit length.
The communication graph is the star \(H\) with edges \(\{s,v\}\) for \(v\in V\). Utilities are given by a symmetric rational matrix \(U\), with \(U(t,t)=0\) and unrestricted signs off the diagonal, including between nonadjacent types.
A mass partition is a finite family of nonzero vectors \(x^1,\ldots,x^k\in\mathbb Q_{\ge0}^{T}\) satisfying \(\sum_a x^a_t=\mu_t\). Types may split across coalitions; there is no prescribed bound on \(k\). Each support \(\operatorname{supp}(x^a)=\{t:x^a_t>0\}\) must induce a connected subgraph of \(H\); singleton supports are allowed. These vectors describe a measurable partition of atomless type populations, with every individual assigned.
A type-\(t\) individual in coalition \(x\) has utility \(u_t(x)=\sum_r U(t,r)x_r\).
An infinitesimal deviation from \(x^a\), where \(x^a_t>0\), may join another coalition \(y=x^b\), \(b\ne a\), or form a new coalition alone, represented by \(y=0\). It is profitable and admissible exactly when \(u_t(y)>u_t(x^a)\), \(\operatorname{supp}(y)\cup\{t\}\) is connected, and \(U(r,t)\ge0\) for every \(r\in\operatorname{supp}(y)\) adjacent to \(t\) in \(H\). Destination approval is vacuous for \(y=0\); no departure approval is required.
A partition is in-neighbor stable if it admits no such deviation. The computational problem is to find one, or determine that none exists.
Can this problem be solved in time polynomial in \(m,\tau,L\), or is it NP-hard as a search problem?
For finite individual players, finding an in-neighbor stable partition with symmetric additively separable utilities on a star is PLS-complete, and a stable partition always exists ([verified source](https://arxiv.org/pdf/1602.05342)).
No result settling this exact mass problem was located in the literature search.
The polynomial-time versus $\mathrm{NP}$-hardness classification remains partial. The following results are proved below:
These results do not establish $\mathrm{NP}$-hardness or classify search with compressed output.
Call a coalition central if its center coordinate is positive. Every noncentral coalition has singleton support: two distinct leaves induce a disconnected subgraph of the star.
Every type present in a stable coalition must have nonnegative utility. Indeed, forming a new singleton is admissible and gives utility zero.
If all center–leaf utilities are nonnegative, the center can admissibly join every existing coalition. Consequently, stability forces the center’s utility to have a common value $C$ in all central coalitions. For two distinct central coalitions, this follows by comparing deviations in both directions; with only one central coalition, define $C$ to be its center utility.
Give each of $s,a,b,c$ mass $1/4$. For a rational parameter $\varepsilon\geq 0$, use the symmetric matrix
$$
U_\varepsilon=
\begin{pmatrix}
0&1&\varepsilon&\varepsilon\\
1&0&1&-3\\
\varepsilon&1&0&4\\
\varepsilon&-3&4&0
\end{pmatrix},
$$
in the order $s,a,b,c$.
All center–leaf utilities are nonnegative. Thus every leaf can admissibly join any central coalition, and the center can admissibly join any existing coalition.
Theorem. For $\varepsilon=0$, no stable partition exists. For $\varepsilon>0$, the minimum number of coalitions in a stable partition is
$$
\left\lceil\frac{1}{2\varepsilon}\right\rceil+1.
$$
Assume a stable partition exists, and let $C$ be its common center utility.
Individual rationality gives $C\geq 0$. In every central coalition $y$,
$$
C=y_a+\varepsilon(y_b+y_c).
$$
If $C=0$, then $y_a=0$ in every central coalition. All $a$-mass therefore lies in singleton coalitions.
Choose such a singleton with mass $d>0$. A center individual can admissibly join it and obtain utility $d>0$, contradicting stability. Hence
$$
C>0.
$$
In a central coalition $y$,
$$
u_b(y)=y_a+\varepsilon y_s+4y_c.
$$
If $\varepsilon>0$, this is positive because $y_s>0$. If $\varepsilon=0$, it is positive because $y_a=C>0$.
A noncentral $b$-coalition gives utility zero, so its members would profitably join a central coalition. Thus all $b$-mass is central.
Suppose some $c$-mass lies in a singleton. Stability then requires
$$
u_c(y)=\varepsilon y_s-3y_a+4y_b\leq 0
$$
for every central coalition $y$.
Let $A$ be the total central $a$-mass. Summing over the finite family of central coalitions gives
$$
\sum_{y\text{ central}}u_c(y)
=
\frac{\varepsilon}{4}-3A+1
\geq
\frac{\varepsilon}{4}+\frac14
>0,
$$
where $A\leq 1/4$ and all $b$-mass is central. This contradicts the nonpositive summands. Therefore all $c$-mass is central.
If every central coalition contained $a$, individual rationality would give $u_a(y)\geq 0$ in every such coalition. But
$$
u_a(y)=y_s+y_b-3y_c,
$$
and hence
$$
\sum_{y\text{ central}}u_a(y)
=
\frac14+\frac14-\frac34
=
-\frac14.
$$
This is impossible. Thus some central coalition $z$ satisfies $z_a=0$.
For the coalition $z$ just obtained,
$$
C=z_a+\varepsilon(z_b+z_c)=0
$$
when $\varepsilon=0$. This contradicts $C>0$.
Therefore the instance with $\varepsilon=0$ has no stable partition. The argument applies to every finite partition, regardless of how types split.
In the central coalition $z$ containing no $a$,
$$
C=\varepsilon(z_b+z_c)\leq\frac{\varepsilon}{2}.
$$
For any central coalition $x$,
$$
x_a\leq x_a+\varepsilon(x_b+x_c)=C.
$$
A noncentral coalition containing $a$ is a singleton. If its mass is $d$, the center can join it and receive utility $d$. Stability therefore requires $d\leq C$.
Thus every coalition contains at most $\varepsilon/2$ mass of $a$. Since total $a$-mass is $1/4$, at least
$$
\left\lceil\frac{1/4}{\varepsilon/2}\right\rceil
=
\left\lceil\frac{1}{2\varepsilon}\right\rceil
$$
coalitions contain $a$. The central coalition $z$ contains no $a$, so one additional coalition is necessary.
Set
$$
N=\left\lceil\frac{1}{2\varepsilon}\right\rceil.
$$
Use one central coalition
$$
x^0=\left(\frac14,0,\frac14,\frac14\right)
$$
and $N$ singleton coalitions, each with vector
$$
x^j=\left(0,\frac{1}{4N},0,0\right),
\qquad 1\leq j\leq N.
$$
All coordinate sums equal the prescribed masses, and all supports are connected.
The central utilities are
$$
u_s(x^0)=\frac{\varepsilon}{2},
\qquad
u_b(x^0)=u_c(x^0)=1+\frac{\varepsilon}{4}.
$$
An $a$-individual receives zero in its singleton, while joining the central coalition gives
$$
u_a(x^0)=\frac14+\frac14-\frac34=-\frac14.
$$
Joining another $a$-singleton or forming a new singleton gives zero.
For $b$ and $c$, joining an $a$-singleton would produce disconnected support. Forming a new singleton gives zero, below their current utilities.
The center receives
$$
\frac{1}{4N}\leq\frac{\varepsilon}{2}
$$
by joining an $a$-singleton, where the inequality follows from $N\geq 1/(2\varepsilon)$. Forming a new singleton gives zero.
These exhaust the destinations, so the construction is stable and attains the lower bound.
Take $\varepsilon=2^{-n}$ with $n\geq 1$. The instance has fixed $m=3$ and $\tau=4$, all utility magnitudes are at most $4$, and its binary input length is $L=\Theta(n)$.
Nevertheless, every stable partition has at least
$$
2^{n-1}+1=2^{\Omega(L)}
$$
coalitions. Therefore an algorithm that explicitly writes one vector per coalition cannot run in time polynomial in $m,\tau,L$.
This is an output-size obstruction, not an $\mathrm{NP}$-hardness proof. The matching construction has a short representation using one singleton vector and its binary multiplicity.
Consider instances satisfying the following hypotheses:
Write
$$
\beta_i=U(a,i),
\qquad i\in Z,
$$
and set $B_{ii}=0$. The coefficients $\beta_i$ may have either sign.
Start with
$$
F_0=\{i\in Z:\beta_i>0\}.
$$
For a current set $F$, define
$$
d_i(F)=\beta_i\mu_a+\sum_{j\in F}B_{ij}\mu_j.
$$
Repeatedly add an element $i\notin F$ with $d_i(F)>0$, until no such element remains. Let $F$ be the resulting terminal set, and define
$$
D=\alpha\mu_s+\sum_{i\in F}\beta_i\mu_i.
$$
Theorem. A stable partition exists if and only if $D\geq 0$. When $D\geq 0$, a stable partition can be found in polynomial time without splitting any type.
Assume a stable partition exists. All center–leaf utilities are nonnegative, so the common center utility is
$$
C=\alpha x_a
$$
in every central coalition $x$.
If $C=0$, all $a$-mass is in singletons, and the center can profitably join any positive-mass $a$-singleton. Therefore $C>0$, and every central coalition has the same positive $a$-coordinate
$$
h=\frac{C}{\alpha}>0.
$$
If $\beta_i>0$, then in every central coalition $y$,
$$
u_i(y)=\beta_i h+\sum_{j\in Z}B_{ij}y_j>0.
$$
Thus no $i$-mass can remain in a singleton. This proves the assertion for $F_0$.
Proceed inductively. Suppose every type in the current set $F$ has all its mass central, and let $i\notin F$ satisfy $d_i(F)>0$.
Because $F_0\subseteq F$, we have $\beta_i\leq 0$. Let $A\leq\mu_a$ be the total central $a$-mass, and let $z_j$ denote the total central mass of type $j$. Then
$$
\begin{aligned}
\sum_{y\text{ central}}u_i(y)
&=\beta_i A+\sum_{j\in Z}B_{ij}z_j\\
&\geq \beta_i\mu_a+\sum_{j\in F}B_{ij}\mu_j\\
&=d_i(F)>0.
\end{aligned}
$$
The inequality uses $\beta_i\leq 0$, $A\leq\mu_a$, $B_{ij}\geq 0$, and $z_j=\mu_j$ for $j\in F$.
If any $i$-mass remained in a singleton, stability would require $u_i(y)\leq 0$ for every central destination. The positive sum rules this out. Thus the assertion holds after the insertion.
Every central coalition contains $a$, so individual rationality gives $u_a(y)\geq 0$ in each one.
Every type in the terminal set $F$ has all its mass central. Every type outside $F$ has $\beta_i\leq 0$. Therefore
$$
\begin{aligned}
0
&\leq \sum_{y\text{ central}}u_a(y)\\
&=\alpha\mu_s+\sum_{i\in Z}\beta_i z_i\\
&=\alpha\mu_s+\sum_{i\in F}\beta_i\mu_i
+\sum_{i\notin F}\beta_i z_i\\
&\leq D.
\end{aligned}
$$
Thus $D\geq 0$ is necessary.
Suppose $D\geq 0$. Put all masses of $s,a$, and the types in $F$ into one central coalition. Put each remaining type into its own singleton.
The center receives $\alpha\mu_a>0$, and $a$ receives $D\geq 0$.
For each $i\in F$, its central utility is $d_i(F)>0$. For initial members this follows from $\beta_i>0$. For later members it follows from the positive score at insertion, since subsequent insertions cannot decrease scores.
For each $i\notin F$, terminality gives $d_i(F)\leq 0$. Consequently, it does not profitably join the central coalition from its singleton.
Distinct-leaf singleton destinations are disconnected. The center receives zero by joining any excluded singleton, because its center edge has value zero. Singleton formation offers no strict improvement to any present type. Hence the partition is stable.
The closure takes at most $|Z|$ insertions. Maintaining the scores requires polynomially many rational operations, and all scores are sums of input products with polynomial bit length. The construction therefore runs in polynomial time.
Theorem. If
$$
U(s,v)\neq 0
\qquad\text{for every }v\in V,
$$
then a finite rational stable partition exists.
Moreover, one can construct such a partition with one central coalition and singleton coalitions, using at most $\tau$ distinct vectors when repetitions are represented by binary multiplicities.
Let
$$
P=\{v\in V:U(s,v)>0\}.
$$
Leave every leaf with $U(s,v)<0$ in a singleton. Such a leaf cannot join a central coalition, and the center cannot join its singleton: destination approval fails in either direction.
If $P$ is empty, the all-singleton partition is stable.
Otherwise, for $S\subseteq P$, define
$$
\Phi(S)=
\mu_s\sum_{i\in S}U(s,i)\mu_i
+
\sum_{\{i,j\}\subseteq S}U(i,j)\mu_i\mu_j,
$$
where the second sum is over unordered pairs of distinct elements.
Choose a set $S$ maximizing $\Phi$. It is nonempty, because
$$
\Phi(\{i\})=\mu_sU(s,i)\mu_i>0
$$
for every $i\in P$, whereas $\Phi(\varnothing)=0$.
Let $x$ contain all center mass and all masses of leaves in $S$.
For $i\in S$, maximality gives
$$
0\leq\Phi(S)-\Phi(S\setminus\{i\})=\mu_i u_i(x),
$$
so $u_i(x)\geq 0$.
For $i\in P\setminus S$, maximality gives
$$
0\geq\Phi(S\cup\{i\})-\Phi(S)=\mu_i u_i(x),
$$
so $u_i(x)\leq 0$.
These identities use the zero diagonal of $U$.
The center’s utility in $x$ is
$$
C=\sum_{i\in S}U(s,i)\mu_i>0.
$$
For each $i\in P\setminus S$, set
$$
n_i=\left\lceil\frac{U(s,i)\mu_i}{C}\right\rceil
$$
and divide its mass into $n_i$ singleton coalitions, each of mass $\mu_i/n_i$.
The center’s utility from joining any such singleton is
$$
U(s,i)\frac{\mu_i}{n_i}\leq C.
$$
Included leaves have nonnegative current utilities. Excluded positive-edge leaves have current utility zero and obtain nonpositive utility by joining $x$. Negative-edge leaves cannot join $x$ because approval fails. Distinct-leaf singleton destinations are disconnected, and same-type singleton destinations give zero. The center weakly prefers $x$ to every admissible singleton destination. Thus no profitable admissible deviation exists.
All coordinates are rational, and every $n_i$ is a finite positive integer.
Enumerating the subsets of $P$ gives a construction in time
$$
2^{|P|}\operatorname{poly}(m,L)
$$
for compressed output. The chosen vector, singleton vectors, and binary multiplicities all have polynomial encoding length. A polynomial-time search algorithm for this subclass is not established here.
In particular, a zero-valued center edge is necessary for nonexistence. The family in Section 2 shows that approaching such an edge from positive values can force the number of coalitions to diverge.
Under explicit listing, polynomial-time search is ruled out by the proved output-size lower bound. General existence is also disproved by a constant-size instance.
The remaining complexity questions require further arguments. Neither the output-size obstruction nor the existence results provide a search-hardness reduction. The complexity of deciding existence for unrestricted matrices, and of producing stable partitions with compressed multiplicities, remains open in this write-up.
⟨structured verdict parsed — rendered above⟩
The output is correct as partial progress. The nonexistence example, exact coalition-count bound, subclass algorithm, and existence theorem all withstand verification. The general search-complexity classification remains unresolved. The only major issue is incomplete coverage of the assignment, which the prover explicitly acknowledges.
All three observations are valid.
These arguments respect the requirement that an existing destination differ from the origin coalition.
Positivity of $C$. Individual rationality implies $C\geq 0$. The identity
$$
C=y_a+\varepsilon(y_b+y_c)
$$
and nonnegativity of all coordinates show that $C=0$ forces $y_a=0$ in every central coalition. Consequently, all positive $a$-mass is in singleton coalitions. Joining any such singleton gives the center strictly positive utility, with approval satisfied because $U(a,s)=1$. The contradiction is valid.
All $b$-mass is central. In every central coalition,
$$
u_b(y)=y_a+\varepsilon y_s+4y_c.
$$
For $\varepsilon>0$, the term $\varepsilon y_s$ is positive. For $\varepsilon=0$, the previously established identity gives $y_a=C>0$. Thus every central destination gives $b$ positive utility. A $b$-singleton gives zero, and admission to a central coalition is permitted because $U(s,b)=\varepsilon\geq 0$. The conclusion follows.
All $c$-mass is central. If a $c$-singleton existed, stability would require every central destination to satisfy $u_c(y)\leq 0$. Summation gives
$$
\sum_{y\text{ central}}u_c(y)
=\frac{\varepsilon}{4}-3A+1
\geq \frac{\varepsilon}{4}+\frac14>0.
$$
The constants are correct: all center mass is central, all $b$-mass has just been shown central, and $A\leq 1/4$. Admission is permitted because $U(s,c)=\varepsilon\geq 0$. This contradiction is valid.
A central coalition omits $a$. If every central coalition contained $a$, individual rationality would make every corresponding $u_a(y)$ nonnegative. However,
$$
\sum_{y\text{ central}}u_a(y)
=\frac14+\frac14-3\cdot\frac14
=-\frac14.
$$
This uses the established centrality of all $b$- and $c$-mass. The contradiction is valid.
All summations are legitimate because the partition is finite.
The central coalition omitting $a$ has center utility zero when $\varepsilon=0$. This contradicts the common value $C>0$.
The argument excludes every permitted finite rational partition, regardless of splitting or coalition count. The nonexistence claim is proved.
For the central coalition $z$ omitting $a$,
$$
C=\varepsilon(z_b+z_c)\leq \frac{\varepsilon}{2}.
$$
Every central coalition satisfies $x_a\leq C$. Every noncentral coalition containing $a$ is an $a$-singleton; its mass $d$ must satisfy $d\leq C$, or the center would profitably join it.
Consequently, every coalition contains at most $\varepsilon/2$ mass of $a$. Distributing total mass $1/4$ requires at least
$$
\left\lceil\frac{1}{2\varepsilon}\right\rceil
$$
coalitions containing $a$. The coalition $z$ is an additional coalition because it contains no $a$. The lower bound is correct for every rational $\varepsilon>0$.
The construction preserves all masses and uses connected supports. Its utility calculations are correct:
$$
u_s(x^0)=\frac{\varepsilon}{2},
\qquad
u_b(x^0)=u_c(x^0)=1+\frac{\varepsilon}{4},
\qquad
u_a(x^0)=-\frac14.
$$
The destination checks cover every possible deviation:
$$
\frac{1}{4N}\leq\frac{\varepsilon}{2}.
$$
A new singleton also gives no improvement.
The constructed coordinates are rational and all coalition vectors are nonzero. Thus the asserted minimum coalition count is proved, including parameter values for which $N=1$.
For $\varepsilon=2^{-n}$ with $n\geq 1$,
$$
\left\lceil\frac{1}{2\varepsilon}\right\rceil+1
=2^{n-1}+1.
$$
With fixed dimension and conventional explicit binary rational encoding, the input length is $L=\Theta(n)$. Hence every stable partition requires exponentially many explicitly listed coalition vectors.
This correctly rules out polynomial-time search when the output lists every coalition separately. The instances used for this conclusion have stable partitions, so an algorithm cannot avoid the output requirement by reporting nonexistence.
The prover correctly distinguishes this obstruction from a search-hardness reduction. It does not rule out polynomial-time search using a compressed output format.
Here the common center utility satisfies
$$
C=\alpha x_a.
$$
If $C=0$, all $a$-mass is in singletons, and joining one gives the center positive utility with valid approval. Thus $C>0$, and every central coalition contains the same positive amount $h=C/\alpha$ of $a$.
This is valid even if some additional $a$-mass remains outside the central coalitions.
For an initial member $i\in F_0$, the expression
$$
u_i(y)=\beta_i h+\sum_{j\in Z}B_{ij}y_j
$$
is strictly positive: the first term is positive and every other term is nonnegative. Admission to central coalitions is allowed by the zero center edge.
For a later insertion, $i\notin F$ implies $\beta_i\leq 0$, since $F_0\subseteq F$. Therefore
$$
\beta_i A\geq\beta_i\mu_a.
$$
Together with $B_{ij}\geq 0$ and the induction hypothesis, this justifies the displayed lower bound by $d_i(F)>0$.
If any mass of $i$ remained in a singleton, every central destination would have to give nonpositive utility, contradicting the positive sum. The induction is sound.
The proof applies to whichever admissible insertion order the algorithm selects; uniqueness of the terminal set is not needed for the stated test.
Every central coalition contains $a$, so its $a$-utility is nonnegative. All members of $F$ are fully central, while every excluded coefficient satisfies $\beta_i\leq 0$. Thus
$$
0\leq \sum_{y\text{ central}}u_a(y)\leq D.
$$
The direction of the last inequality is correct. Necessity of $D\geq 0$ is proved.
The proposed central coalition gives the center positive utility and gives $a$ utility $D\geq 0$.
Every included type has positive utility: initial members have $\beta_i>0$, and subsequently inserted members retain their positive insertion score because later insertions add only nonnegative contributions. The zero diagonal ensures that inserting a type does not alter its score through a self-interaction.
Every excluded type has utility zero in its singleton and nonpositive utility in the central destination. Distinct-leaf destinations are disconnected. The center obtains zero from every excluded singleton, and singleton formation improves no occupied type.
These checks exhaust the deviations, so sufficiency is proved.
There are at most $|Z|$ insertions. The scores are sums of rational input products with polynomial bit length, and exact comparisons and updates take polynomial time. The constructed output uses no splitting and has polynomial size.
The argument also covers $Z=\varnothing$ and the boundary case $D=0$.
A negative-edge leaf cannot enter a central coalition because the center would reject it. The center cannot enter that leaf’s singleton because the leaf would reject it. Other distinct-leaf destinations are disconnected.
Therefore the all-singleton partition is stable when $P=\varnothing$. This also covers the support consisting only of the center.
A maximizer of $\Phi$ exists because there are finitely many subsets of $P$. It is nonempty because every singleton subset has positive value, whereas the empty subset has value zero.
The removal and insertion identities are correct:
$$
\Phi(S)-\Phi(S\setminus\{i\})=\mu_i u_i(x),
$$
for $i\in S$, and
$$
\Phi(S\cup\{i\})-\Phi(S)=\mu_i u_i(x),
$$
for $i\in P\setminus S$.
Symmetry, the unordered-pair convention, and the zero diagonal justify these identities without a missing factor. Maximality consequently gives nonnegative utilities for included leaves and nonpositive destination utilities for excluded positive-edge leaves.
No external theorem is needed for this step.
Since $S$ is nonempty and all its center edges are positive,
$$
C=\sum_{i\in S}U(s,i)\mu_i>0.
$$
Every specified $n_i$ is therefore a finite positive integer, and
$$
U(s,i)\frac{\mu_i}{n_i}\leq C.
$$
The stability checks are complete. Included leaves have nonnegative current utility; excluded positive-edge leaves cannot improve by entering the central coalition; negative-edge leaves fail approval there; and the center cannot improve by entering any admissible singleton.
The coordinates are rational. There is one central vector and at most one singleton vector for each excluded leaf, giving at most $\tau$ distinct vectors.
The encoding and enumeration claims also hold. The values used to compute $C$ and $n_i$ have polynomial bit length, so binary multiplicities and singleton coordinates have polynomial encoding length. Exhaustive subset enumeration takes
$$
2^{|P|}\operatorname{poly}(m,L)
$$
time for compressed output.
The concluding statement that a zero center edge is necessary for nonexistence is exactly the contrapositive of the proved theorem.
Major scope issue: the general complexity question is not settled. There is no search-hardness reduction, polynomial-time compressed search algorithm, or general existence-decision algorithm.
This is an acknowledged limitation, not a false step in the proofs. The explicit-output lower bound nevertheless establishes a substantive answer: polynomial-time search is impossible under literal coalition-by-coalition output.
No clarification or repair is needed for the four proved results. To complete the original classification, a further submission must specify the output convention and provide the missing complexity argument. Any search-hardness claim must state its reduction notion and verify how valid solutions and nonexistence reports behave under that reduction.
⟨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.