Answer: \(\mathrm{NP}\)-hard, even when \(m=3\), \(G=K_3\), and \(\sigma=1\).
Theorem 6.2 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGiven a social Schelling game $I$ and a rational value $s$, it is {\em NP}-complete to decide whether $I$ admits an assignment with social welfare at least $s$. The hardness result holds even if all agents are strategic and even if $G$ is a graph of maximum degree $2$.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a finite role-type set \(\Theta\), rational mass distribution \(\mu\in\mathbb{Q}_{\ge0}^{\Theta}\) with \(\sum_{\theta}\mu_\theta=1\), binary friendship matrix \(W_{\theta,\theta'}\), finite undirected topology \(G=(V,E)\), rational capacities \(b_v\), and threshold \(\sigma\), decide whether there exists \(x_{\theta,v}\ge0\) satisfying \(\sum_v x_{\theta,v}=\mu_\theta\) and \(\sum_\theta x_{\theta,v}\le b_v\), with total welfare \(\sum_{\theta,v}x_{\theta,v}u_{\theta,v}(x)\ge\sigma\), where \(u_{\theta,v}(x)\) is the neighboring friend-mass fraction.
A society is given by its support: a list \(\Theta\) of \(\tau\) role types with positive binary rational masses \(\mu_\theta\), where \(\sum_\theta\mu_\theta=1\). Here \(\tau\) is the support size, not the number of possible types. All mass is strategic and freely assignable.
Input also includes a symmetric matrix \(W\in\{0,1\}^{\Theta\times\Theta}\), a simple undirected topology \(G=(V,E)\) with \(m=|V|\ge3\), positive binary rational capacities \(b_v\) with \(\sum_v b_v>1\), and a binary rational threshold \(\sigma\). The entry \(W_{\theta,\theta'}\) specifies friendship between individuals of the indicated roles; diagonal entries may be either value.
An assignment consists of real masses \(x_{\theta,v}\ge0\) satisfying \(\sum_vx_{\theta,v}=\mu_\theta\) and \(\sum_\theta x_{\theta,v}\le b_v\); roles may split and share vertices.
Define \(d_v(x)=\sum_{w:\{v,w\}\in E}\sum_{\theta'}x_{\theta',w}\) and \(f_{\theta,v}(x)=\sum_{w:\{v,w\}\in E}\sum_{\theta'}W_{\theta,\theta'}x_{\theta',w}\). Set \(u_{\theta,v}(x)=f_{\theta,v}(x)/d_v(x)\) when \(d_v(x)>0\), and \(u_{\theta,v}(x)=0\) otherwise. Mass at the same vertex contributes neither to numerator nor denominator.
The decision problem asks whether some assignment satisfies \(\sum_{\theta,v}x_{\theta,v}u_{\theta,v}(x)\ge\sigma\); no equilibrium condition is imposed. Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is this continuous welfare-threshold decision problem in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For discrete social Schelling games, welfare-threshold decision is \(\mathrm{NP}\)-complete even with all agents strategic and topology of maximum degree \(2\). [Elkind et al.](https://www.ijcai.org/proceedings/2019/0038.pdf)
No result settling this exact mass formulation was located in the literature search.
The continuous welfare-threshold problem is \(\mathrm{NP}\)-hard, even when \(m=3\), the topology is the triangle \(K_3\), and \(\sigma=1\). Thus hardness holds on a topology of maximum degree \(2\).
The proof uses a polynomial-time reduction from PARTITION. Its key feature is that welfare \(1\) forces certain pairs of roles to remain entirely together, despite the permission to split roles and share vertices.
Write the welfare as \(F(x)=\sum_{\theta,v}x_{\theta,v}u_{\theta,v}(x)\).
Since \(W\) has entries in \(\{0,1\}\), we have \(0\le f_{\theta,v}(x)\le d_v(x)\). Together with the zero-denominator convention, this gives \(0\le u_{\theta,v}(x)\le1\). Also, mass conservation gives \(\sum_{\theta,v}x_{\theta,v}=1\). Consequently,
\(F(x)\le1,\qquad 1-F(x)=\sum_{\theta,v}x_{\theta,v}\bigl(1-u_{\theta,v}(x)\bigr).\)
Every summand on the right is nonnegative. Therefore, if \(F(x)\ge1\), then \(F(x)=1\), and every pair with \(x_{\theta,v}>0\) satisfies \(u_{\theta,v}(x)=1\). In particular, such a pair must have \(d_v(x)>0\).
Lemma. Suppose the topology is complete, and two positive-mass roles \(p,q\) satisfy \(W_{p,q}=W_{q,p}=0\). In every assignment with welfare \(1\), all mass of both roles is concentrated at one common vertex.
Proof. Choose a vertex \(v\) with \(x_{p,v}>0\), which exists because \(\mu_p>0\). By Section 1, \(d_v(x)>0\) and \(u_{p,v}(x)=1\).
For every \(w\ne v\), completeness makes \(w\) a neighbor of \(v\). Since role \(q\) is unfriendly to role \(p\),
\(d_v(x)-f_{p,v}(x)=\sum_{w\ne v}\sum_{\theta'}(1-W_{p,\theta'})x_{\theta',w}\ge\sum_{w\ne v}x_{q,w}.\)
Utility \(1\) implies \(d_v(x)-f_{p,v}(x)=0\). Hence all mass of \(q\) lies at \(v\), so \(x_{q,v}=\mu_q>0\). Applying the same argument to role \(q\) at \(v\) shows that all mass of \(p\) also lies there. This proves the lemma.
PARTITION on positive binary-encoded integers is \(\mathrm{NP}\)-complete; see [Karp’s original paper](https://link.springer.com/chapter/10.1007/978-1-4684-2001-2_9). We use the form with positive integers \(a_1,\ldots,a_n\) satisfying
\(\sum_{i=1}^n a_i=2B,\)
and ask whether some subset sums to \(B\). Restricting to even total preserves hardness: multiplying every input integer by \(2\) preserves the existence of an equal partition and makes the total even.
Construct the following instance.
All masses are positive, and their sum is
\(\sum_{i=1}^n(\mu_{p_i}+\mu_{q_i})=\sum_{i=1}^n\frac{a_i}{2B}=1.\)
All capacities are positive, and
\(b_{v_1}+b_{v_2}+b_{v_3}=1+\frac{3}{4B}>1.\)
Thus the construction satisfies every input requirement. All fractions have binary-encoded integer numerators and denominators.
Suppose \(I\subseteq\{1,\ldots,n\}\) satisfies \(\sum_{i\in I}a_i=B\).
Place both roles of each item in \(I\) entirely at \(v_1\), and both roles of every remaining item entirely at \(v_2\). Leave \(v_3\) empty.
Each occupied vertex receives mass \(B/(2B)=1/2\), within its capacity. Every occupied role sees neighboring mass \(1/2\). Its sole unfriendly role is its paired role, which lies at the same vertex and therefore contributes neither to its numerator nor to its denominator. All neighboring mass is friendly.
Hence every occupied role-location pair has utility \(1\), and the welfare is \(1\).
Conversely, suppose an assignment has welfare at least \(\sigma=1\). Section 1 gives welfare exactly \(1\).
By the lemma, each pair \(p_i,q_i\) must be concentrated together at one vertex. Its total mass is \(a_i/(2B)\). No pair can occupy \(v_3\), because
\(\frac{a_i}{2B}\ge\frac{1}{2B}>\frac{1}{4B}=b_{v_3}.\)
Therefore all pairs occupy either \(v_1\) or \(v_2\).
For \(j\in\{1,2\}\), let \(A_j\) be the sum of the integers corresponding to pairs placed at \(v_j\). Capacity feasibility implies
\(\frac{A_j}{2B}\le\frac{2B+1}{4B},\qquad A_j\le B+\frac12.\)
Since \(A_j\) is an integer, \(A_j\le B\). Every item is assigned to one of these two vertices, so \(A_1+A_2=2B\). These inequalities force \(A_1=A_2=B\), giving an equal partition.
This argument covers arbitrary real assignments: splitting is excluded by the welfare condition itself.
The constructed instance has \(m=3\), \(\tau=2n\), and total binary encoding length
\(L=O\bigl(n^2+n\log(B+1)\bigr).\)
The quadratic term accounts for the explicitly supplied friendship matrix. If \(S\) denotes the source instance’s binary length, the construction takes \(O(S^2)\) bit operations when fractions are supplied as numerator-denominator pairs; requiring reduced fractions still gives polynomial time.
We have therefore established a polynomial-time many-one reduction from PARTITION. An algorithm running in time polynomial in \(m,\tau,L\) for the stated problem would decide PARTITION in polynomial time. Consequently, the problem is \(\mathrm{NP}\)-hard and has no such polynomial-time algorithm unless \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the assigned question: the continuous welfare-threshold problem is \(\mathrm{NP}\)-hard even for \(G=K_3\), \(m=3\), and \(\sigma=1\). I found no major or minor mathematical issues.
Nonnegative masses and binary friendship entries give \(0\le f_{\theta,v}(x)\le d_v(x)\). The zero-denominator convention therefore ensures \(0\le u_{\theta,v}(x)\le1\) in every case.
Mass conservation gives \(\sum_{\theta,v}x_{\theta,v}=1\), so the stated identity
\(1-F(x)=\sum_{\theta,v}x_{\theta,v}(1-u_{\theta,v}(x))\)
is correct. This is a finite sum of nonnegative terms. Consequently, \(F(x)\ge1\) forces equality and forces utility \(1\) at every role-location pair carrying positive mass.
The further conclusion \(d_v(x)>0\) at such a pair follows directly from the convention assigning utility \(0\) when the denominator vanishes. No continuity or attainment assumption is used.
Positive mass of role \(p\) guarantees an occupied vertex \(v\). Completeness ensures that every other vertex occurs in the neighborhood sum. The displayed difference \(d_v(x)-f_{p,v}(x)\) correctly counts all unfriendly neighboring mass, with nonnegative coefficients.
Since \(W_{p,q}=0\), this difference bounds the total mass of \(q\) outside \(v\). Utility \(1\), together with a positive denominator, makes the difference zero. Nonnegativity and mass conservation then force all of \(q\) to lie at \(v\).
Role \(q\) consequently has positive mass at \(v\). Applying the same reasoning using \(W_{q,p}=0\) forces all of \(p\) there as well. The lemma applies to arbitrary real masses and does not assume indivisibility.
The invoked theorem is the standard \(\mathrm{NP}\)-completeness of PARTITION for positive binary-encoded integers. This is the appropriate source problem; see [Karp’s paper, reprinted here](https://www.cs.umd.edu/~gasarch/BLOGPAPERS/Karp.pdf).
Multiplying every integer by \(2\) preserves equal-partition feasibility and produces an even total. This transformation has polynomial encoding size. Thus the stated even-total restriction remains \(\mathrm{NP}\)-hard.
Positivity and the nonempty source instances ensure that \(B\) is a positive integer, so every denominator in the construction is well-defined.
There are exactly \(2n\) listed positive-mass roles, consistent with the task’s definition of support size. Their total mass is
\(\sum_i a_i/(2B)=1\).
The friendship matrix is symmetric and binary. Its diagonal entries equal \(1\), which the task permits. Each role’s only unfriendly role is its paired role.
All three capacities are positive, and their sum is correctly calculated as \(1+3/(4B)>1\). The topology is simple and undirected, has three vertices, and has maximum degree \(2\). The threshold is a permitted rational value.
The construction therefore satisfies all stated input requirements.
A subset summing to \(B\) and its complement each produce vertex mass \(1/2\). These loads satisfy the two capacities, each of which exceeds \(1/2\).
Both occupied vertices have neighboring mass \(1/2>0\). Every unfriendly paired role lies at the same vertex as its partner and contributes to neither numerator nor denominator. All neighboring mass is friendly, so every occupied role-location pair has utility \(1\).
The empty third vertex contributes zero welfare. The total welfare is exactly \(1\).
Welfare at least \(1\) implies welfare exactly \(1\), allowing the lemma to be applied to every pair.
Each pair has mass \(a_i/(2B)\). Since \(a_i\ge1\), this exceeds \(b_{v_3}=1/(4B)\), so no pair can occupy the third vertex.
For either remaining vertex, the capacity inequality correctly gives \(A_j\le B+1/2\). Both \(A_j\) and \(B\) are integers, so \(A_j\le B\). Every item occurs at exactly one of these vertices, giving \(A_1+A_2=2B\). Hence both sums equal \(B\).
This establishes the reverse implication for all feasible real assignments, including assignments initially permitted to split and share vertices.
The explicit friendship matrix uses \(O(n^2)\) bits. Each listed rational uses \(O(\log(B+1))\) bits, since every \(a_i\le2B\). The bound \(L=O(n^2+n\log(B+1))\) is valid.
For source length \(S\), both \(n\) and \(\log(B+1)\) are \(O(S)\). Summation, construction of numerator-denominator pairs, and emission of the matrix fit the claimed \(O(S^2)\) bit-operation bound under that representation. Reducing fractions also takes polynomial time.
The resulting many-one reduction proves the claimed hardness in the binary input model. The proof does not establish membership of the general continuous problem in \(\mathrm{NP}\), and it does not claim to do so. No additional clarification or repair is required.
⟨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.