Answer: \(\mathrm{NP}\text{-hard}\), already with \(\tau=1\) and \(N=2\). The restriction to \(N=2\) is \(\mathrm{NP}\text{-complete}\).
Theorem 6. — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateConsider a modified $1$-Schelling game and let $\xi$ be a rational number. Then, deciding whether there exists an assignment with social welfare at least $\xi$ is NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a connected graph \(G=(V,E)\), an integer \(N\geq 2\) with \(|V|>N\), and a rational threshold \(\xi\), does there exist a real mass allocation \((\mu_v)_{v\in V}\) with \(0\leq\mu_v\leq 1/N\) and \(\sum_{v\in V}\mu_v=1\) such that \(F_N(\mu)\geq\xi\), where \(z_v=\sum_{w\in N(v)}\mu_w\) and \(F_N(\mu)=\sum_{v\in V}\mu_v z_v/(1/N+z_v)\)?
A society is given by its support: the list of the \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) counts supported types, not possible types. Here there is one type, of mass \(1\), so \(\tau=1\); vertex masses below are allocation variables.
The input is a simple undirected connected graph \(G=(V,E)\), with \(m=|V|\), a binary integer \(N\geq2\) satisfying \(m>N\), and a binary rational threshold \(\xi\in\mathbb Q\). Let \(L\) be the total input bit length; state running times in \(m,\tau,L\), and \(N\).
A feasible allocation has real masses \(0\leq\mu_v\leq1/N\) and \(\sum_{v\in V}\mu_v=1\). Write \(N_G(v)\) for the open neighborhood of \(v\), and define \(z_v=\sum_{w\in N_G(v)}\mu_w\) and \(F_N(\mu)=\sum_{v\in V}\mu_v z_v/(1/N+z_v)\). All mass is of the same type; the term \(1/N\) is fixed even at partially occupied vertices. No equilibrium condition is imposed.
Is deciding whether a feasible real allocation satisfies \(F_N(\mu)\geq\xi\) solvable in polynomial time in the binary input size, or is it NP-hard?
For the discrete version, placing \(N\) identical agents at distinct vertices and giving each agent with \(d\) occupied neighbors utility \(d/(1+d)\), deciding whether total utility reaches a rational threshold is NP-complete ([discrete hardness result](https://repository.essex.ac.uk/30550/1/modified.tcs.revision.pdf)).
No result settling this exact continuous allocation problem was identified in the literature search.
The continuous allocation problem is \(\mathrm{NP}\)-hard, already with \(\tau=1\) and \(N=2\). In fact, its restriction to \(N=2\) is \(\mathrm{NP}\)-complete.
The key is an exact formula for the continuous optimum in terms of the clique number. Fractional allocations are fully accounted for.
Let \(\omega(G)\) denote the maximum number of vertices in a clique of \(G\). For any nonnegative vector \(x\) with \(\sum_v x_v=1\), define
\(Q_G(x)=\sum_v x_v\sum_{w\in N_G(v)}x_w=2\sum_{\{v,w\}\in E}x_vx_w.\)
We first prove
\(Q_G(x)\leq 1-\dfrac{1}{\omega(G)}.\)
This is the quadratic bound of [Motzkin and Straus](https://www.cambridge.org/core/services/aop-cambridge-core/content/view/S0008414X00039493). Here is a self-contained proof.
Suppose two nonadjacent vertices \(u,v\) both have positive coordinates. Put
\(c_u=\sum_{w\in N_G(u)}x_w,\qquad c_v=\sum_{w\in N_G(v)}x_w.\)
Because \(G\) has no loops and \(u,v\) are nonadjacent, these two quantities depend only on coordinates outside \(\{u,v\}\). The part of \(Q_G(x)\) involving either coordinate is therefore
\(2x_uc_u+2x_vc_v.\)
If \(c_u\geq c_v\), replace \((x_u,x_v)\) by \((x_u+x_v,0)\). The change in \(Q_G\) is \(2x_v(c_u-c_v)\geq0\). Otherwise, transfer all of \(x_u\) to \(v\).
Each transfer preserves nonnegativity and total mass, does not decrease \(Q_G\), and reduces the number of positive coordinates. Repeating produces a vector \(y\) whose support is a clique, of some size \(r\leq\omega(G)\). Consequently,
\(Q_G(x)\leq Q_G(y)=\left(\sum_v y_v\right)^2-\sum_v y_v^2=1-\sum_v y_v^2.\)
By Cauchy–Schwarz, \(\sum_v y_v^2\geq1/r\). Thus
\(Q_G(x)\leq1-\dfrac1r\leq1-\dfrac1{\omega(G)}.\)
These transfers are used only to prove an inequality on the unrestricted simplex; they need not preserve the allocation cap.
Define
\(h_N(t)=\dfrac{t}{1/N+t}\qquad(t\geq0).\)
Its derivatives are
\(h_N'(t)=\dfrac{1/N}{(1/N+t)^2}>0,\qquad h_N''(t)=-\dfrac{2/N}{(1/N+t)^3}<0.\)
Thus \(h_N\) is increasing and concave. For every feasible allocation \(\mu\), Jensen’s inequality applies with nonnegative weights \(\mu_v\) summing to one:
\(F_N(\mu)=\sum_v\mu_vh_N(z_v)\leq h_N\left(\sum_v\mu_vz_v\right)=h_N(Q_G(\mu)).\)
Applying the quadratic bound and monotonicity gives
\(F_N(\mu)\leq h_N\left(1-\dfrac1{\omega(G)}\right)=\dfrac{N(\omega(G)-1)}{\omega(G)+N(\omega(G)-1)}.\)
Now suppose \(\omega(G)\geq N\). Choose a maximum clique \(C\), write \(r=|C|=\omega(G)\), and allocate
\(\mu_v=\dfrac1r\) for \(v\in C\), and \(\mu_v=0\) otherwise.
This allocation is feasible because \(1/r\leq1/N\). Every vertex with positive mass has neighborhood mass \(z_v=(r-1)/r\). Therefore its objective value attains the upper bound.
We have proved the exact formula
\(\displaystyle \max_{\mu\text{ feasible}}F_N(\mu)=\dfrac{N(\omega(G)-1)}{\omega(G)+N(\omega(G)-1)}\qquad\text{whenever }\omega(G)\geq N.\)
In particular, every connected graph with \(m>2\) contains an edge, so \(\omega(G)\geq2\). Hence for every valid instance with \(N=2\),
\(\displaystyle \max_{\mu\text{ feasible}}F_2(\mu)=\dfrac{2(\omega(G)-1)}{3\omega(G)-2}.\)
The function \(B(r)=2(r-1)/(3r-2)\) is strictly increasing for integers \(r\geq2\), since
\(B(r+1)-B(r)=\dfrac{2}{(3r+1)(3r-2)}>0.\)
We use the standard \(\mathrm{NP}\)-complete CLIQUE problem: given a simple graph \(H\) on \(n\) vertices and an integer \(k\), decide whether \(\omega(H)\geq k\). Its \(\mathrm{NP}\)-completeness is established in [Karp’s original paper](https://doi.org/10.1007/978-1-4684-2001-2_9).
We may restrict to \(n\geq2\) and \(2\leq k\leq n\): inputs outside these ranges are decidable directly, so excluding them preserves hardness.
Construct \(G\) by adding one new vertex adjacent to every vertex of \(H\). Set
\(N=2,\qquad \xi=\dfrac{2k}{3k+1}.\)
Use the single supported type of mass one, so \(\tau=1\).
The constructed graph is simple and connected, and \(m=n+1>2=N\). Moreover,
\(\omega(G)=\omega(H)+1.\)
Indeed, adding the new vertex to a maximum clique of \(H\) proves one inequality. Conversely, removing the new vertex from any clique containing it leaves a clique of \(H\), and any clique excluding it already lies in \(H\).
The exact optimum formula now yields
\(\displaystyle \max_\mu F_2(\mu)=B(\omega(H)+1),\qquad \xi=B(k+1).\)
Strict monotonicity of \(B\) gives both directions of the reduction:
\(\displaystyle \exists\,\mu\text{ feasible with }F_2(\mu)\geq\xi\quad\Longleftrightarrow\quad\omega(H)\geq k.\)
The graph construction takes polynomial time in \(m\) and the input length. The threshold’s numerator and denominator have \(O(\log m)\) bits. For example, a conservative bit-operation bound for the reduction is \(O((m+L)^3)\), with \(\tau=1\) and \(N=2\) fixed.
Thus the full continuous problem is \(\mathrm{NP}\)-hard.
For a valid \(N=2\) instance, a certificate is a clique \(C\) of size \(r\geq2\). The verifier checks its edges and the rational inequality
\(\dfrac{2(r-1)}{3r-2}\geq\xi.\)
An accepted certificate gives a feasible uniform allocation on \(C\) attaining this value. Conversely, if the instance is a yes-instance, a maximum clique supplies an accepted certificate by the exact optimum formula.
The certificate has \(O(m\log m)\) bits. Verification uses at most \(O(m^2)\) adjacency checks and exact integer arithmetic on numbers of \(O(L+\log m)\) bits. A conservative verification bound is \(O((m+L)^3)\), again with \(\tau=1\) and \(N=2\).
Therefore the \(N=2\) restriction is \(\mathrm{NP}\)-complete. In particular, a polynomial-time algorithm in the binary input size—or even a bound \(f(N,\tau)(m+L)^{O(1)}\)—would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The output resolves the task correctly: the continuous decision problem is \(\mathrm{NP}\)-hard even with \(\tau=1\) and \(N=2\), and that restriction is \(\mathrm{NP}\)-complete. I found no major or minor mathematical gaps.
\[
Q_G(x)=2\sum_{\{v,w\}\in E}x_vx_w
\]
correctly counts each undirected edge twice.
For nonadjacent positive coordinates \(x_u,x_v\), both \(c_u\) and \(c_v\) are independent of these coordinates: simplicity excludes loops, and nonadjacency excludes an interaction between \(u\) and \(v\). Consequently, the stated change \(2x_v(c_u-c_v)\) is correct.
Each transfer preserves total mass and nonnegativity, does not decrease \(Q_G\), and strictly reduces the support size. The process therefore terminates with nonempty clique support of size \(1\leq r\leq\omega(G)\). On that support, the displayed identity \(Q_G(y)=1-\sum_vy_v^2\) and the Cauchy–Schwarz bound are valid. The final inequality has the correct direction.
The prover explicitly confines these transfers to the unrestricted simplex. Failure to preserve the allocation cap therefore creates no gap.
Jensen’s inequality is applied with weights \(\mu_v\geq0\) summing to one and arguments \(z_v\geq0\). Zero weights are permitted. Its weighted mean is exactly \(Q_G(\mu)\). Thus the upper bound applies to every feasible real allocation, including partially occupied vertices. It uses the fixed term \(1/N\) specified in the task.
Substitution gives precisely
\[
\frac{N(r-1)}{r+N(r-1)}.
\]
This matches the universal upper bound, proving both the formula and attainment. The allocation variables are real, so there is no requirement that \(1/r\) have a terminating binary expansion.
The formula is explicitly conditional on \(\omega(G)\geq N\). The subsequent hardness argument uses only instances satisfying that condition.
The expression
\[
B(r)=\frac{2(r-1)}{3r-2}
\]
is correct. Rechecking the subtraction gives
\[
B(r+1)-B(r)=\frac{2}{(3r+1)(3r-2)}>0
\]
for every integer \(r\geq2\). There is no denominator or range issue.
Restricting to \(n\geq2\) and \(2\leq k\leq n\) removes only directly decidable cases and preserves hardness. Adding a universal vertex produces a simple connected graph with \(m=n+1>2\). The argument establishing \(\omega(G)=\omega(H)+1\) checks both possibilities for a clique: containing or excluding the new vertex.
The threshold is correctly computed:
\[
\xi=B(k+1)=\frac{2k}{3k+1}.
\]
Both arguments of \(B\) lie in its strictly increasing range. The exact optimum formula therefore establishes the claimed equivalence in both directions, including equality at the threshold. No discrete-to-continuous assumption is used.
Binary encoding of \(N\) presents no difficulty because hardness already holds at a fixed value.
Certificate length and adjacency checking are polynomial. Rational comparison can be performed exactly with integers of \(O(L+\log m)\) bits, so the stated conservative verification bound is sufficient. The argument covers arbitrary rational thresholds, including negative thresholds and unattainably large thresholds.
The prover claims membership only for the \(N=2\) restriction; it does not assert an unsupported membership result for general \(N\).
No additional clarification or mathematical repair 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.