Answer: Polynomial-time solvable; every valid instance is a YES-instance.
Theorem 4 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateAlgorithm 1 provides a solution for the MaxUtil prob- lem in the weighted setting with an approximation ratio of 1 𝑘 for an odd 𝑘 and an approximation ratio of 1 𝑘−1 for an even 𝑘.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given an integer \(k\ge2\), rational type masses \(\mu\in\mathbb{Q}_{\ge0}^{\tau}\) with \(\sum_a\mu_a=1\), and a rational symmetric interaction matrix \(w\in\mathbb{Q}_{\ge0}^{\tau\times\tau}\), choose nonnegative rational masses \(y_r\) for integral coalition patterns \(r\in\mathbb{Z}_{\ge0}^{\tau}\) satisfying \(1\le\lVert r\rVert_1\le k\) and \(\sum_r r_a y_r=\mu_a\) for every type \(a\), maximizing \(\sum_r F_w(r)y_r\), where \(F_w(r)=\sum_a r_a(r_a-1)w_{aa}+2\sum_{a<b}r_ar_bw_{ab}\). Compute a feasible allocation with welfare at least \(1/k\) of optimum for odd \(k\), or at least \(1/(k-1)\) for even \(k\).
Given a finite type set \(T\), rational masses \(\mu_t\ge0\), symmetric affinities \(w:T\times T\to\mathbb{Q}_{\ge0}\), and \(k\ge3\), a coalition profile is \(\mathbf a\in\mathbb Z_{\ge0}^{T}\) with \(1\le\sum_t a_t\le k\). A type-\(t\) member's utility in \(\mathbf a\) is \(U_t(\mathbf a)=\sum_{u\in T}(a_u-\mathbf1_{u=t})w(t,u)\).
A feasible fractional partition is \(\lambda_{\mathbf a}\ge0\) with \(\sum_{\mathbf a}a_t\lambda_{\mathbf a}=\mu_t\) for every \(t\). For profile \(\mathbf b\), let \(\beta_t(\mathbf b;\lambda)=\sum_{\mathbf a:U_t(\mathbf a)<U_t(\mathbf b)}a_t\lambda_{\mathbf a}\). It is core-stable if no \(\mathbf b\) has \(\beta_t(\mathbf b;\lambda)>0\) for every \(t\) with \(b_t>0\).
Target. Is deciding whether a core-stable feasible fractional partition exists solvable in polynomial time, or is it NP-hard?
For finite-agent weighted symmetric additively separable hedonic games with coalition-size bound \(k\), deciding whether a core-stable partition exists is strongly NP-hard for every \(k\ge3\).
The decision problem is polynomial-time solvable. In fact, every valid instance admits a core-stable feasible fractional partition. This holds for every \(k\ge 1\), not merely \(k\ge 3\).
The finite-agent \(\mathrm{NP}\)-hardness result does not transfer: it requires an integral partition, whereas fractional partitions satisfy a general existence theorem based on Scarf’s lemma.
Let \(\mathcal A\) denote the finite set of admissible profiles. For a feasible fractional partition \(\lambda\), a type \(t\), and a profile \(\mathbf b\),
\[ \beta_t(\mathbf b;\lambda)=0 \]
if and only if every profile \(\mathbf a\) satisfying \(a_t\lambda_{\mathbf a}>0\) also satisfies
\[ U_t(\mathbf a)\ge U_t(\mathbf b). \]
Indeed, every summand in the definition of \(\beta_t\) is nonnegative. Hence the sum is zero exactly when no positive mass of type \(t\) is assigned to a profile giving utility strictly below \(U_t(\mathbf b)\).
Consequently, \(\lambda\) is core-stable exactly when every profile \(\mathbf b\) has some participating type \(t\), with \(b_t>0\), such that every positively used profile containing \(t\) is weakly preferred by \(t\) to \(\mathbf b\).
This is precisely the domination condition in Scarf’s lemma.
We use the following standard form of Scarf’s lemma; see [Lemma 1 in Biró, Csáji, and Schlotter](https://drops.dagstuhl.de/storage/00lipics/lipics-vol334-icalp2025/html/LIPIcs.ICALP.2025.31/LIPIcs.ICALP.2025.31.html#L125).
Let \(Q\in\mathbb R_{\ge0}^{m\times n}\) have a nonzero entry in every column, let \(d\in\mathbb R_{\ge0}^m\), and give each row \(i\) a strict ordering of the columns \(j\) for which \(Q_{ij}>0\). Then there exists \(x\ge0\) with \(Qx\le d\) such that every column \(j\) is dominated in some incident row \(i\). Explicitly, domination means
\[ Q_i x=d_i \]
and every column \(\ell\) with \(Q_{i\ell}x_\ell>0\) is weakly preferred in row \(i\) to column \(j\).
The theorem can moreover choose \(x\) to be an extreme point of the packing polytope.
First remove every type \(t\) with \(\mu_t=0\), and write
\[ T^+=\{t\in T:\mu_t>0\}. \]
Consider only profiles supported on \(T^+\), and define the matrix \(Q\), with rows indexed by \(T^+\) and columns indexed by these profiles, by
\[ Q_{t,\mathbf a}=a_t. \]
Every column is nonzero because every profile has positive total size. The polytope
\[ P=\{\lambda\ge0:Q\lambda\le\mu\} \]
is bounded: for each profile \(\mathbf a\), choose \(t\) with \(a_t>0\); then every \(\lambda\in P\) satisfies
\[ \lambda_{\mathbf a}\le \frac{\mu_t}{a_t}. \]
For each type \(t\), order all profiles containing \(t\) by decreasing \(U_t\)-utility, breaking utility ties arbitrarily. Thus
\[ \mathbf a\succeq_t\mathbf b \quad\Longrightarrow\quad U_t(\mathbf a)\ge U_t(\mathbf b). \]
Scarf’s lemma produces \(\lambda^*\in P\) that dominates every profile.
For every \(t\in T^+\), the singleton profile \(\mathbf e_t\) is admissible because \(k\ge1\). Its column has a positive entry only in row \(t\).
Since Scarf’s solution dominates every column, it must dominate \(\mathbf e_t\) in row \(t\). Domination requires row \(t\) to be tight, so
\[ \sum_{\mathbf a}a_t\lambda^*_{\mathbf a}=\mu_t. \]
This holds for every \(t\in T^+\). Set \(\lambda^*_{\mathbf a}=0\) for profiles involving a zero-mass type. The resulting vector is therefore a feasible fractional partition for the original instance.
Fix any profile \(\mathbf b\).
If \(b_t>0\) for some zero-mass type \(t\), then feasibility gives
\[ 0\le \beta_t(\mathbf b;\lambda^*) \le \sum_{\mathbf a}a_t\lambda^*_{\mathbf a} =\mu_t=0. \]
Thus \(\beta_t(\mathbf b;\lambda^*)=0\), so \(\mathbf b\) cannot block.
Otherwise, \(\mathbf b\) is supported on \(T^+\). By Scarf domination, there is some \(t\) with \(b_t>0\) such that every profile \(\mathbf a\) with \(a_t\lambda^*_{\mathbf a}>0\) satisfies
\[ \mathbf a\succeq_t\mathbf b. \]
By the construction of the ordering,
\[ U_t(\mathbf a)\ge U_t(\mathbf b). \]
Therefore no positive mass of type \(t\) receives utility strictly below \(U_t(\mathbf b)\), and hence
\[ \beta_t(\mathbf b;\lambda^*)=0. \]
Thus no profile has \(\beta_t(\mathbf b;\lambda^*)>0\) for every participating type. Hence \(\lambda^*\) is core-stable.
If all masses are zero, the identically zero vector \(\lambda=0\) is feasible and the same argument makes every \(\beta_t\) zero.
Every well-formed instance is a YES-instance. A decision algorithm can therefore return YES immediately, so the decision problem is polynomial-time solvable.
Scarf’s lemma is only being used for existence. Computing an explicit stable fractional partition is a separate search problem and need not inherit this trivial decision complexity.
The finite-agent hardness theorem concerns integrality. Scarf’s point can be fractional because the profile matrix \(Q\) is not generally totally unimodular, and there is no valid general rounding step preserving stability. Thus the finite-agent theorem supplies no hardness reduction for the fractional decision problem.
⟨structured verdict parsed — rendered above⟩
The prover’s central conclusion is correct: every valid instance admits a core-stable feasible fractional partition, so the decision problem is polynomial-time solvable by always returning YES. The application of Scarf’s lemma is substantively sound.
There is one minor overstatement: utility-based weak preference is not literally identical to domination under an arbitrarily tie-broken strict ordering. The latter is stronger. This does not affect the proof because only the implication from Scarf domination to the required utility inequality is used.
Every summand defining \(\beta_t(\mathbf b;\lambda)\) is nonnegative. Hence \(\beta_t(\mathbf b;\lambda)=0\) exactly when no used profile containing type \(t\) gives utility strictly below \(U_t(\mathbf b)\).
Negating the blocking condition correctly yields: for every profile \(\mathbf b\), some participating type \(t\) has \(\beta_t(\mathbf b;\lambda)=0\).
The stated hypotheses and domination conclusion agree with Lemma 1 in the [cited ICALP paper](https://drops.dagstuhl.de/storage/00lipics/lipics-vol334-icalp2025/html/LIPIcs.ICALP.2025.31/LIPIcs.ICALP.2025.31.html#L125): nonnegative matrix, a nonzero entry in every column, strict row orderings on incident columns, row tightness, and preference domination of every positively used incident column.
After removing zero-mass types, each retained profile has at least one positive coordinate, so every column of \(Q\) is nonzero. The profile set is finite because \(T\) and \(k\) are finite.
The boundedness calculation is correct, although boundedness is not needed for the quoted form of Scarf’s lemma.
Ordering profiles by decreasing utility and breaking ties arbitrarily gives the required strict order. If \(\mathbf a\succeq_t\mathbf b\) in this order, then \(U_t(\mathbf a)\ge U_t(\mathbf b)\).
However, the earlier assertion that the utility condition is “precisely” Scarf domination is not literal when utility ties exist: utility weak preference may hold while the arbitrary tie-breaking ranks \(\mathbf a\) below \(\mathbf b\). Scarf domination is therefore a sufficient strengthening, not an exact reformulation. No later step uses the converse.
The singleton profile \(\mathbf e_t\) is admissible and is incident only to row \(t\). Since Scarf’s point dominates every column, domination of \(\mathbf e_t\) must occur in row \(t\), forcing that row to be tight. Thus all positive-mass constraints hold with equality.
Extending the solution by assigning zero weight to profiles containing a zero-mass type preserves all positive-type equalities and satisfies every zero-type equality.
Any proposed blocking profile containing a zero-mass type has \(\beta_t=0\) for that participating type and therefore cannot block.
For a profile supported on positive-mass types, Scarf domination supplies a participating type \(t\) such that every positively used incident profile is at least as high in the tie-broken order. The construction of the order then gives the required weak utility inequality, so \(\beta_t=0\).
The zero vector is feasible, every \(\beta_t\) is zero, and no profile blocks.
Since all valid inputs are YES-instances, existence can be decided in polynomial time without computing the Scarf point. The distinction between the trivial existence decision and the potentially difficult search problem is valid.
Replace or qualify “This is precisely the domination condition in Scarf’s lemma.” The write-up should say only that domination under the chosen tie-broken orders implies the required utility condition. No additional mathematical argument is needed.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.