Answer: polynomial-time solvable
Theorem 4.2 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateFor any distance factor function, if the friend- ship graph is acyclic and utilities are non-negative, then a jump stable assignment exists and can be computed in poly- nomial time.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given rational masses over complete utility types, capacitated topology locations with a specified aggregate distance kernel, and a nonnegative acyclic utility matrix, decide whether there exists a feasible mass assignment \(x\) such that every type occupying a location weakly prefers it to every location with residual capacity.
An instance consists of finite \(T\), rational masses \(\mu_t\ge 0\) with \(\sum_{t\in T}\mu_t=1\), rational utilities \(u(t,t')\), a finite undirected graph \(G=(V,E)\), and rational capacities \(\kappa_v\) with \(\sum_{v\in V}\kappa_v>1\). A feasible allocation has \(x_{t,v}\ge0\), \(\sum_v x_{t,v}=\mu_t\), and \(\sum_t x_{t,v}\le\kappa_v\). Let \(\bar f_G(v,v)=1\), \(\bar f_G(v,z)=1/d_G(v,z)\) for distinct vertices in one component, and \(\bar f_G(v,z)=0\) across components. Define \(U_t(v;x)=\sum_{t'\in T}\sum_{z\in V}\bar f_G(v,z)u(t,t')x_{t',z}\). An allocation is jump stable if, whenever \(x_{t,v}>0\) and \(\sum_t x_{t,w}<\kappa_w\), \(U_t(v;x)\ge U_t(w;x)\).
Is deciding whether a jump-stable feasible allocation exists in this continuous reciprocal-distance model in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard?
For finite-agent topological distance games with reciprocal distance factors, deciding whether a jump-stable assignment exists is \(\mathrm{NP}\)-complete, even when the topology has a constant number of connected components and \(\lvert V\rvert=\Theta(n)\).
The problem is polynomial-time solvable. In fact, under the standard assumption that every capacity is nonnegative, every promised instance admits a jump-stable feasible allocation.
Thus the finite-agent NP-hardness does not survive the continuous relaxation.
Let \(T\) and \(V\) be finite, let \(\mu_t\ge 0\) with \(\sum_t\mu_t=1\), and suppose \(\kappa_v\ge 0\) for every \(v\), with \(\sum_v\kappa_v>1\). For arbitrary utilities \(u(t,t')\), there exists a jump-stable feasible allocation.
For an allocation \(x\) satisfying only the type-mass constraints, define the load
\[ y_v(x)=\sum_{t\in T}x_{t,v}. \]
Let
\[ X_t=\left\{a\in\mathbb R_{\ge 0}^{V}:\sum_{v\in V}a_v=\mu_t\right\}, \qquad X=\prod_{t\in T}X_t. \]
The set \(X\) is nonempty, compact, and convex.
For every positive integer \(n\), define the overload penalty
\[ p_v^{(n)}(x)=n\max\{0,y_v(x)-\kappa_v\} \]
and the penalized payoff
\[ q_t^{(n)}(v;x)=U_t(v;x)-p_v^{(n)}(x). \]
For fixed \(x\), let
\[ A_t^{(n)}(x)=\mathop{\rm argmax}_{v\in V}q_t^{(n)}(v;x) \]
and let \(B_t^{(n)}(x)\) consist of all vectors in \(X_t\) supported on \(A_t^{(n)}(x)\).
Each \(B_t^{(n)}(x)\) is nonempty, compact, and convex. Moreover, the correspondence \(B_t^{(n)}\) has closed graph: if \(x^k\to x\), \(a^k\to a\), and \(a^k\in B_t^{(n)}(x^k)\), then whenever \(a_v>0\), one has \(a_v^k>0\) eventually. Hence \(v\) maximizes \(q_t^{(n)}(\cdot;x^k)\) eventually, and continuity of \(q_t^{(n)}\) implies that \(v\) maximizes \(q_t^{(n)}(\cdot;x)\). Thus \(a\in B_t^{(n)}(x)\).
Consequently, \(B^{(n)}(x)=\prod_t B_t^{(n)}(x)\) is an upper-hemicontinuous correspondence from \(X\) to nonempty compact convex subsets of \(X\). Kakutani’s fixed-point theorem therefore gives some \(x^{(n)}\in X\) such that \(x^{(n)}\in B^{(n)}(x^{(n)})\).
In particular,
\[ x_{t,v}^{(n)}>0 \quad\Longrightarrow\quad q_t^{(n)}(v;x^{(n)})\ge q_t^{(n)}(w;x^{(n)}) \]
for every \(w\in V\).
Let
\[ M=\max_{t,t'\in T}|u(t,t')|. \]
Since \(0\le \bar f_G(v,z)\le 1\) and the total mass is \(1\),
\[ |U_t(v;x)|\le \sum_{t',z}|u(t,t')|x_{t',z} \le M \]
for every \(t,v,x\in X\).
Fix \(n\). Because \(\sum_v y_v(x^{(n)})=1<\sum_v\kappa_v\), there is at least one vertex \(w_n\) such that
\[ y_{w_n}(x^{(n)})<\kappa_{w_n}. \]
Thus \(p_{w_n}^{(n)}(x^{(n)})=0\).
Suppose \(y_v(x^{(n)})>\kappa_v\). Since \(\kappa_v\ge0\), this implies \(y_v(x^{(n)})>0\), so some type \(t\) satisfies \(x_{t,v}^{(n)}>0\). The fixed-point inequality comparing \(v\) with \(w_n\) gives
\[ U_t(v;x^{(n)})-n\bigl(y_v(x^{(n)})-\kappa_v\bigr) \ge U_t(w_n;x^{(n)}). \]
Therefore
\[ n\bigl(y_v(x^{(n)})-\kappa_v\bigr) \le U_t(v;x^{(n)})-U_t(w_n;x^{(n)}) \le 2M. \]
Consequently, for every \(v\),
\[ y_v(x^{(n)})\le \kappa_v+\frac{2M}{n}. \]
Compactness of \(X\) yields a subsequence, still denoted \(x^{(n)}\), converging to some \(x^*\in X\).
Passing to the limit in the preceding load bound gives
\[ y_v(x^*)\le\kappa_v \]
for every \(v\). Hence \(x^*\) is feasible.
Let \(t\in T\) and \(v,w\in V\) satisfy
\[ x^*_{t,v}>0 \qquad\text{and}\qquad y_w(x^*)<\kappa_w. \]
Because both inequalities are strict, for all sufficiently large \(n\),
\[ x_{t,v}^{(n)}>0 \qquad\text{and}\qquad y_w(x^{(n)})<\kappa_w. \]
Thus \(p_w^{(n)}(x^{(n)})=0\). The penalized equilibrium inequality gives
\[ U_t(v;x^{(n)})-p_v^{(n)}(x^{(n)}) \ge U_t(w;x^{(n)}). \]
Since \(p_v^{(n)}(x^{(n)})\ge0\), it follows that
\[ U_t(v;x^{(n)})\ge U_t(w;x^{(n)}). \]
The functions \(U_t(v;\cdot)\) are linear and therefore continuous. Passing to the limit yields
\[ U_t(v;x^*)\ge U_t(w;x^*). \]
This is precisely jump stability.
If capacities are understood, as usual, to be nonnegative, the decision algorithm simply returns “yes” on every promised instance.
Under the literal statement, which does not explicitly require \(\kappa_v\ge0\), the algorithm is:
This requires only a polynomial-time scan of the rational capacities.
The finite-agent hardness reduction therefore cannot transfer directly: divisibility and total spare capacity guarantee existence through the limiting penalized equilibrium argument.
⟨structured verdict parsed — rendered above⟩
The prover fully resolves the decision problem. The existence theorem is correct, the limiting argument is rigorous, and the treatment of potentially negative capacities covers the literal input definition. Consequently, the decision problem is in \(\mathrm{P}\): return “no” exactly when some capacity is negative, and “yes” otherwise.
The set \(X=\prod_t X_t\) is correctly identified as nonempty, compact, and convex. This remains valid for types with \(\mu_t=0\), in which case \(X_t\) is a singleton.
The penalized payoffs \(q_t^{(n)}(v;x)\) are continuous in \(x\). Since \(V\) is finite, every argmax set \(A_t^{(n)}(x)\) is nonempty. The set of allocations in \(X_t\) supported on this argmax is nonempty, compact, and convex.
The closed-graph argument is valid: if \(a_v>0\) and \(a^k\to a\), then \(a_v^k>0\) for all sufficiently large \(k\). Thus \(v\) is an argmax along the tail, and continuity preserves the corresponding weak inequalities in the limit.
On the compact domain \(X\), the resulting correspondence satisfies Kakutani’s hypotheses. The fixed point \(x^{(n)}\) therefore exists and has the asserted support-on-maximizers property.
The estimate \(\lvert U_t(v;x)\rvert\le M\) is correct because \(0\le\bar f_G(v,z)\le1\) and the total allocated mass is \(1\).
The existence of a vertex \(w_n\) with \(y_{w_n}(x^{(n)})<\kappa_{w_n}\) follows from
\[ \sum_v y_v(x^{(n)})=1<\sum_v\kappa_v. \]
If every vertex instead satisfied \(y_v\ge\kappa_v\), summing would contradict this strict inequality.
For an overloaded vertex \(v\), nonnegative capacity ensures \(y_v>0\), so some type is assigned positive mass there. Comparing that vertex with \(w_n\) in the fixed-point inequality correctly yields
\[ n\bigl(y_v-\kappa_v\bigr)\le 2M. \]
Thus \(y_v(x^{(n)})\le\kappa_v+2M/n\) for every vertex.
Compactness supplies a convergent subsequence. Since its integer indices tend to infinity, the overload error \(2M/n\) tends to zero. Continuity of each load gives \(y_v(x^*)\le\kappa_v\). The type-mass constraints are retained because \(x^*\in X\). Hence \(x^*\) is feasible.
If \(x^*_{t,v}>0\) and \(y_w(x^*)<\kappa_w\), convergence and strictness imply the same two inequalities for all sufficiently large subsequence indices. Therefore the destination penalty is zero.
The penalized equilibrium inequality then gives
\[ U_t(v;x^{(n)})-p_v^{(n)}(x^{(n)})\ge U_t(w;x^{(n)}). \]
Because \(p_v^{(n)}\ge0\), the claimed unpenalized inequality follows. Continuity of \(U_t\) permits passage to the limit, producing exactly the required jump-stability condition.
If some \(\kappa_v<0\), feasibility is impossible because the nonnegative load at \(v\) cannot be at most a negative number. If all capacities are nonnegative, the theorem guarantees existence. Checking the signs of the rational capacities is polynomial time.
No construction of the equilibrium is required for the stated decision problem, so the nonconstructive use of Kakutani does not undermine the complexity classification.
No mathematical or logical defects 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.