Answer: \(\mathrm{polynomial\text{-}time\ solvable}\)
Theorem 5.3 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateComputing a Nash stable outcome in hedonic skill games with singleton tasks is a PLS-complete problem when 𝑞= 2.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite skill set \(S\), rational masses \(\mu_\theta\) over nonempty skill-set types \(\theta\subseteq S\), rational positive weights \(w_s\) for singleton tasks, and two coalitions, compute a mass allocation \(x_{\theta,j}\ge0\) satisfying \(\sum_{j=1}^{2}x_{\theta,j}=\mu_\theta\) such that every type with \(x_{\theta,j}>0\) satisfies \(u_{\theta,j}\ge u_{\theta,3-j}\), where \(M_{s,j}=\sum_{\theta\ni s}x_{\theta,j}\) and \(u_{\theta,j}=\sum_{s\in\theta}w_s/M_{s,j}\), with a zero denominator interpreted as \(+\infty\).
Definitions. Let \(S\) be a finite skill set. Each skill \(s\in S\) has a singleton task of weight \(w_s>0\). The explicitly listed types \(A\in\mathcal A\subseteq 2^S\) have rational masses \(\mu_A\). Split each type between two coalitions using \(x_{A,j}\ge0\) with \(x_{A,1}+x_{A,2}=\mu_A\). Define \(M_{j,s}=\sum_{A\ni s}x_{A,j}\) and \(u_A(j;x)=\sum_{s\in A}w_s/M_{j,s}\), with \(w_s/0:=+\infty\). A split is Nash stable if \(x_{A,j}>0\Rightarrow u_A(j;x)\ge u_A(3-j;x)\).
Target. Is computing a Nash-stable split \(x\) for this two-coalition nonatomic singleton-task skill game polynomial-time solvable, or is it PLS-hard?
Nearest known results. In the finite-agent singleton-task version with two coalitions, computing a Nash-stable outcome is PLS-complete. Such discrete instances always have a Nash-stable outcome because better-response dynamics converges.
Computing a Nash-stable split is polynomial-time solvable. In fact, every valid instance admits the explicit symmetric split
\[ x_{A,1}=x_{A,2}=\frac{\mu_A}{2} \]
for every \(A\in\mathcal A\).
Because \(\mu_A\) is a mass, assume \(\mu_A\geq 0\). Define the total mass possessing skill \(s\) by
\[ T_s=\sum_{\substack{A\in\mathcal A\\s\in A}}\mu_A. \]
Under the proposed split, for each coalition \(j\in\{1,2\}\) and skill \(s\in S\),
\[ M_{j,s} =\sum_{\substack{A\in\mathcal A\\s\in A}}x_{A,j} =\sum_{\substack{A\in\mathcal A\\s\in A}}\frac{\mu_A}{2} =\frac{T_s}{2}. \]
Consequently,
\[ M_{1,s}=M_{2,s} \]
for every \(s\in S\).
Fix a type \(A\in\mathcal A\).
If \(\mu_A=0\), then \(x_{A,1}=x_{A,2}=0\). Both implications in the definition of Nash stability have false antecedents, so this type imposes no condition.
Suppose instead that \(\mu_A>0\). Then \(x_{A,1}>0\) and \(x_{A,2}>0\). Moreover, for every \(s\in A\),
\[ T_s\geq \mu_A>0, \]
so both relevant skill masses are positive. Therefore,
\[ u_A(1;x) =\sum_{s\in A}\frac{w_s}{M_{1,s}} =\sum_{s\in A}\frac{2w_s}{T_s} =\sum_{s\in A}\frac{w_s}{M_{2,s}} =u_A(2;x). \]
Thus both Nash-stability inequalities hold:
\[ u_A(1;x)\geq u_A(2;x) \qquad\text{and}\qquad u_A(2;x)\geq u_A(1;x). \]
This applies to every positive-mass type. Hence the symmetric split is Nash stable.
For each explicitly listed type \(A\), the algorithm outputs two copies of the rational number \(\mu_A/2\). If \(\mu_A=p_A/q_A\) is given in binary, one may output \(p_A/(2q_A)\), whose encoding length exceeds that of \(\mu_A\) by at most one bit. The running time and output size are therefore linear, up to ordinary rational-encoding costs, in the explicit input size.
The finite-agent \(\mathrm{PLS}\)-completeness result does not transfer: a discrete agent generally cannot be divided equally between the two coalitions, whereas nonatomic type mass can. Thus the search problem belongs to \(\mathrm{FP}\); it could be \(\mathrm{PLS}\)-hard under standard reductions only if \(\mathrm{FP}=\mathrm{PLS}\).
⟨structured verdict parsed — rendered above⟩
The prover fully resolves the target. The symmetric split
\[
x_{A,1}=x_{A,2}=\frac{\mu_A}{2}
\]
is feasible and Nash stable, and it can be computed in polynomial—indeed linear—time in the explicit input size.
\[
x_{A,1}=x_{A,2}=\frac{\mu_A}{2}\geq 0
\]
and
\[
x_{A,1}+x_{A,2}=\mu_A.
\]
Thus the proposed output satisfies all split constraints.
\[
M_{j,s}=\sum_{A\ni s}\frac{\mu_A}{2}=\frac{T_s}{2}
\]
is correct. Hence \(M_{1,s}=M_{2,s}\) for every skill \(s\).
\[
T_s\geq \mu_A>0,
\]
so the utility denominators associated with this type are nonzero. This correctly excludes any ambiguity involving \(+\infty\).
\[
u_A(1;x)=\sum_{s\in A}\frac{2w_s}{T_s}=u_A(2;x).
\]
Equality implies both required weak inequalities. The argument also remains valid when \(A=\varnothing\), since both utilities are then empty sums equal to zero.
No unjustified steps, false claims, missing lemmas, or relevant edge-case failures were found.
⟨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.