Answer: Polynomial-time solvable: every valid instance admits a stable mass assignment.
Theorem 3.1 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateS-Eq is NP-complete. Note that membership in NP is trivial, as we can check whether an assignment is a swap-equilibrium by iterating over all pairs of agents and checking whether they have a profitable swap.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a connected graph \(G=(V,E)\), rational capacities \(b_v>0\) with \(\sum_{v\in V}b_v=1\), and a two-type population distribution \(\mu=(\mu_1,\mu_2)\), decide whether there exists a mass assignment \(x_{\ell v}\ge0\) satisfying \(\sum_{\ell=1}^2x_{\ell v}=b_v\) and \(\sum_{v\in V}x_{\ell v}=\mu_\ell\), such that no pair of infinitesimal households of distinct types has a mutually profitable swap. Here \(u_\ell(v;x)=0\) when the neighbourhood has zero mass, and otherwise \(u_\ell(v;x)=\frac{\sum_{w\in N(v)}x_{\ell w}}{\sum_{k=1}^2\sum_{w\in N(v)}x_{kw}}\); a swap from \(u\) and \(v\) is profitable exactly when \(x_{\ell u}x_{kv}>0\), \(\ell\ne k\), and \(u_\ell(v;x)>u_\ell(u;x)\) and \(u_k(u;x)>u_k(v;x)\).
For each \(v\in V\), let \(N(v)\) be its neighbourhood. The input consists of a connected graph \(G=(V,E)\), rational \(b_v>0\) with \(\sum_{v\in V}b_v=1\), and rational \(\mu_1,\mu_2\ge 0\) with \(\mu_1+\mu_2=1\). An assignment has \(x_{\ell v}\ge0\), \(\sum_{\ell=1}^2x_{\ell v}=b_v\), and \(\sum_{v\in V}x_{\ell v}=\mu_\ell\). Define \(u_\ell(v;x)=0\) if \(\sum_{k=1}^2\sum_{w\in N(v)}x_{kw}=0\), and otherwise \(u_\ell(v;x)=\frac{\sum_{w\in N(v)}x_{\ell w}}{\sum_{k=1}^2\sum_{w\in N(v)}x_{kw}}\). It is stable if no \(u,v\in V\) and \(\ell\ne k\) satisfy \(x_{\ell u}x_{kv}>0\), \(u_\ell(v;x)>u_\ell(u;x)\), and \(u_k(u;x)>u_k(v;x)\).
Target. Is deciding whether such a stable mass assignment exists solvable in polynomial time, or is it NP-hard?
Nearest known results. For finite two-type Schelling games with every vertex occupied and the same fraction-of-own-type utility, deciding whether a swap-equilibrium exists is NP-complete (Kreisel, Boehmer, Froese, and Niedermeier, 2022). No result for the mass-assignment formulation above is included here.
The decision problem is polynomial-time solvable. In fact, every valid input admits a stable mass assignment, so the decision algorithm always answers “yes.”
Let
\[ y_v:=x_{1v}. \]
Then \(x_{2v}=b_v-y_v\), and the feasible set for \(y\) is
\[ K:=\left\{y\in\mathbb R^V:0\le y_v\le b_v\text{ for every }v,\ \sum_{v\in V}y_v=\mu_1\right\}. \]
This set is nonempty because \(y_v=\mu_1b_v\) belongs to \(K\). It is also compact and convex.
Suppose first that \(|V|\ge2\). Since \(G\) is connected, every vertex has a neighbor. Define
\[ B_v:=\sum_{w\in N(v)}b_w>0 \]
and
\[ q_v(y):=\frac{\sum_{w\in N(v)}y_w}{B_v}. \]
The denominator in the utility definition is independent of the assignment:
\[ \sum_{k=1}^2\sum_{w\in N(v)}x_{kw} =\sum_{w\in N(v)}(x_{1w}+x_{2w}) =\sum_{w\in N(v)}b_w =B_v. \]
Consequently,
\[ u_1(v;x)=q_v(y),\qquad u_2(v;x)=1-q_v(y). \]
Each \(q_v\) is a linear, hence continuous, function of \(y\).
Consider first a potential blocking pair with \(\ell=1\) and \(k=2\). Its conditions become
\[ y_u>0,\qquad y_v<b_v,\qquad q_v(y)>q_u(y), \]
because
\[ u_2(u;x)>u_2(v;x)\iff 1-q_u(y)>1-q_v(y)\iff q_v(y)>q_u(y). \]
If instead \(\ell=2\) and \(k=1\), interchanging the names of \(u\) and \(v\) gives the same condition. Therefore an assignment is stable exactly when
\[ y_u>0\text{ and }y_v<b_v\quad\Longrightarrow\quad q_u(y)\ge q_v(y) \]
for all \(u,v\in V\).
Thus every vertex carrying positive type-\(1\) mass must have weakly greater type-\(1\) neighborhood fraction than every vertex having room for additional type-\(1\) mass.
For \(y,a\in K\), define
\[ \Phi(y,a):=\sum_{v\in V}q_v(y)a_v. \]
For fixed \(y\), define the correspondence
\[ F(y):=\operatorname*{arg\,max}_{a\in K}\Phi(y,a). \]
We verify the hypotheses of Kakutani’s fixed-point theorem.
\[ \Phi(y^{(n)},a^{(n)})\ge\Phi(y^{(n)},c). \]
Taking limits gives \(\Phi(y,a)\ge\Phi(y,c)\), so \(a\in F(y)\).
Kakutani’s theorem therefore yields some \(y^*\in K\) satisfying
\[ y^*\in F(y^*). \]
Suppose, toward a contradiction, that \(y^*\) is not stable. By the characterization above, there are vertices \(u,v\) such that
\[ y^*_u>0,\qquad y^*_v<b_v,\qquad q_v(y^*)>q_u(y^*). \]
Choose
\[ 0<\delta\le\min\{y^*_u,b_v-y^*_v\} \]
and transfer \(\delta\) units of type-\(1\) mass from \(u\) to \(v\):
\[ a:=y^*-\delta e_u+\delta e_v. \]
The coordinate bounds remain satisfied, and \(\sum_w a_w=\sum_w y^*_w=\mu_1\), so \(a\in K\). But
\[ \Phi(y^*,a)-\Phi(y^*,y^*) =\delta\bigl(q_v(y^*)-q_u(y^*)\bigr)>0. \]
This contradicts \(y^*\in F(y^*)\). Hence \(y^*\) is stable.
Setting
\[ x_{1v}:=y^*_v,\qquad x_{2v}:=b_v-y^*_v \]
produces the required stable mass assignment.
If \(V=\{v\}\), then \(b_v=1\). Set
\[ x_{1v}=\mu_1,\qquad x_{2v}=\mu_2. \]
The neighborhood is empty, so both utilities are \(0\). No strict utility inequalities can hold, and the assignment is stable.
Every connected valid instance, including the one-vertex instance, admits a stable assignment. Therefore the existence language contains every promised input. A decision algorithm can simply answer “yes,” and hence runs in constant time after input validation.
This does not imply that constructing a stable assignment by a particular representation is computationally easy; the fixed-point proof is existential. It completely settles the stated existence decision problem.
⟨structured verdict parsed — rendered above⟩
The prover’s argument is correct and fully resolves the stated existence decision problem. It proves that every valid connected instance admits a stable mass assignment. Consequently, the promised decision problem is polynomial-time solvable by always answering “yes.”
No mathematical gaps or false assertions were found.
Setting \(y_v=x_{1v}\) correctly forces \(x_{2v}=b_v-y_v\). The resulting feasible set
\[ K=\left\{y\in\mathbb R^V:0\leq y_v\leq b_v,\ \sum_v y_v=\mu_1\right\} \]
is nonempty because \(y_v=\mu_1b_v\) satisfies all constraints, using \(0\leq\mu_1\leq1\) and \(\sum_v b_v=1\). Compactness and convexity follow directly from the finite-dimensional linear constraints.
For \(\lvert V\rvert\geq2\), connectedness ensures every vertex has a neighbor. Since every \(b_w>0\), this gives
\[ B_v=\sum_{w\in N(v)}b_w>0. \]
The utility denominator is correctly shown to equal \(B_v\), independently of the assignment. Thus
\[ u_1(v;x)=q_v(y),\qquad u_2(v;x)=1-q_v(y). \]
There is no unhandled zero-denominator case in this part of the proof.
For \(\ell=1\) and \(k=2\), the mass condition is exactly
\[ y_u>0,\qquad b_v-y_v>0, \]
and both strict utility inequalities reduce to \(q_v(y)>q_u(y)\).
For \(\ell=2\) and \(k=1\), swapping the labels of \(u\) and \(v\) indeed gives the same condition. Because stability quantifies over all ordered pairs \(u,v\), this renaming is legitimate.
Therefore the stated characterization
\[ y_u>0\ \text{and}\ y_v<b_v \quad\Longrightarrow\quad q_u(y)\geq q_v(y) \]
for every \(u,v\) is equivalent to the original stability definition.
For each \(y\in K\), the correspondence
\[ F(y)=\operatorname*{arg\,max}_{a\in K}\sum_v q_v(y)a_v \]
has nonempty, compact, and convex values:
The objective is jointly continuous. The cited Berge maximum theorem applies because the feasible correspondence is the fixed nonempty compact set \(K\). Hence \(F\) is upper hemicontinuous.
The supplied sequential argument establishes that the graph of \(F\) is closed. In this compact finite-dimensional setting, this is also sufficient for upper hemicontinuity. Thus the hypotheses of Kakutani’s fixed-point theorem are satisfied, and the conclusion \(y^*\in F(y^*)\) is justified.
If \(y^*\) violated stability, the characterization from Section 2 would give \(u,v\) with
\[ y_u^*>0,\qquad y_v^*<b_v,\qquad q_v(y^*)>q_u(y^*). \]
A positive \(\delta\) satisfying the stated bound exists. The transferred vector
\[ a=y^*-\delta e_u+\delta e_v \]
remains in \(K\): the coordinate bounds are respected and the total mass remains \(\mu_1\).
The objective change is correctly calculated as
\[ \Phi(y^*,a)-\Phi(y^*,y^*) =\delta\bigl(q_v(y^*)-q_u(y^*)\bigr)>0. \]
This contradicts \(y^*\in F(y^*)\). Hence every such fixed point is stable. Translating back to \(x_{1v}=y_v^*\) and \(x_{2v}=b_v-y_v^*\) satisfies all assignment constraints.
For a connected graph with one vertex, its neighborhood is empty under the usual graph convention. The denominator in every utility is zero, so the definition assigns both utilities the value \(0\). Strict improvement inequalities are therefore impossible. The proposed assignment is feasible and stable.
The proof is existential, but the target asks only whether a stable assignment exists. Since every valid promised input has one, an always-“yes” decision procedure is correct. Input validation, if counted, is plainly polynomial-time; after validation, the answer itself is constant-time.
The absence of an explicit procedure for constructing \(y^*\) does not affect the stated decision problem.
⟨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.