Answer: \(\mathrm{NP}\text{-complete}\): a qualifying priority order exists exactly when \(H\) has a Hamiltonian path.
Corollary 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateLet (k, G(W, E)) be given. It is NP-complete to test if there is a labeling {w1, w2, . . . , wn} of the workers such that, if all firms rank the workers according to that labeling, the complete locally stable matching is unique.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given a type graph \(H=(T,E)\) with \(\tau\) worker types of mass \(1/\tau\), and \(\tau\) firms each with capacity \(1/\tau\), all types share the strict firm ranking \(f_1 \succ \cdots \succ f_\tau\), and firms share a strict priority order \(\pi\) over types. A complete mass matching is an array \(x_{t,f} \ge 0\) whose row and column sums are all \(1/\tau\). For each edge \(\{t,u\} \in E\) with \(t \succ_\pi u\), local stability requires \(x_{t,f_j}x_{u,f_i}=0\) whenever \(i<j\). Does there exist an order \(\pi\) for which exactly one complete locally stable mass matching exists?
A society is given by its support: the list of the \(\tau\) types with positive mass, each with its mass as a binary rational; \(\tau\) is the support size, not the number of possible types.
The input is a finite simple undirected graph \(H=(T,E)\), where \(|T|=\tau\geq1\); every type has mass \(1/\tau\), so total mass is \(1\). There are \(m=\tau\) firms, each of capacity \(1/\tau\).
All types share the strict ranking \(f_1\succ\cdots\succ f_m\). The firms share a strict total priority order \(\pi\) over types, which may be chosen freely.
A complete mass matching is an array \(x\in\mathbb{R}_{\geq0}^{T\times F}\) satisfying \(\sum_f x_{t,f}=1/\tau\) for every type and \(\sum_t x_{t,f}=1/\tau\) for every firm; mass may be split arbitrarily.
For a chosen \(\pi\), a matching is locally stable precisely when \(x_{t,f_j}x_{u,f_i}=0\) for every \(\{t,u\}\in E\) with \(t\succ_\pi u\) and every \(1\leq i<j\leq m\). Uniqueness means equality of arrays, without distinguishing individuals within a type.
Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
Is deciding whether some strict priority order \(\pi\) yields exactly one complete locally stable mass matching solvable in polynomial time, or is it NP-hard?
For indivisible workers and one position per firm under these common strict rankings, choosing a priority order that yields a unique complete locally stable matching is NP-complete. [Arcaute and Vassilvitskii](https://theory.stanford.edu/~sergei/papers/wine09-matching.pdf).
No result settling the exact mass-matching decision problem above was identified in the literature search.
The decision problem is \(\mathrm{NP}\text{-complete}\). More precisely, a priority order yields exactly one complete locally stable mass matching if and only if its consecutive types form a Hamiltonian path in \(H\).
The proof below applies to arbitrary real mass splitting.
Fix a priority order \(t_1\succ_\pi\cdots\succ_\pi t_\tau\), with \(m=\tau\). Define the canonical matching by
\(x^*_{t_r,f_i}=1/\tau\) if \(i=r\), and \(x^*_{t_r,f_i}=0\) otherwise.
Every row and column has sum \(1/\tau\), so this matching is complete.
It is also locally stable. Indeed, if \(\{t_r,t_s\}\in E\) and \(r<s\), the only firms receiving their mass are \(f_r\) and \(f_s\), respectively. Thus the higher-priority type never has positive mass at a worse firm than the lower-priority type.
Suppose \(\{t_r,t_{r+1}\}\notin E\) for some \(r<\tau\). Modify the canonical matching by assigning all mass of \(t_r\) to \(f_{r+1}\) and all mass of \(t_{r+1}\) to \(f_r\).
The resulting array is complete and differs from \(x^*\).
Swapping two consecutive types changes their relative firm order only with respect to each other: every other type occupies a firm either before both or after both. Consequently, the relative firm order of the endpoints of every edge remains consistent with \(\pi\), because the swapped pair is not an edge. The modified matching is therefore locally stable.
Hence uniqueness requires
\(\{t_r,t_{r+1}\}\in E\quad\text{for every }1\le r<\tau.\)
Assume now that every consecutive pair is an edge, and let \(x\) be any complete locally stable mass matching.
For each type, define its nonempty support of firm indices by
\(S_r=\{i:x_{t_r,f_i}>0\}.\)
These supports are nonempty because every type has positive total mass. Write \(a_r=\max S_r\) and \(b_r=\min S_r\).
For the edge \(\{t_r,t_{r+1}\}\), local stability implies
\(a_r\le b_{r+1}.\)
Otherwise, the positive entries \(x_{t_r,f_{a_r}}\) and \(x_{t_{r+1},f_{b_{r+1}}}\), with \(b_{r+1}<a_r\), would violate the stated stability condition.
Since \(b_r\le a_r\), these inequalities imply, for every \(r<s\),
\(a_r\le b_{r+1}\le a_{r+1}\le\cdots\le b_s.\)
Thus every firm supporting an earlier type is at least as preferred as every firm supporting a later type. Equality of firm indices remains possible at this stage.
We now prove inductively that each type places all its mass at its corresponding firm.
Suppose that types \(t_1,\ldots,t_{r-1}\) have already been shown to place all their mass at \(f_1,\ldots,f_{r-1}\), respectively. For \(r=1\), this assumption is empty.
Those earlier firms are full, so nonnegativity and their column sums imply that no remaining type places mass there.
If \(t_r\) had positive mass at some \(f_j\) with \(j>r\), then \(a_r\ge j>r\). The support inequalities would give \(b_s\ge a_r>r\) for every \(s>r\). Hence no later type could place mass at \(f_r\). Earlier types place their mass only at their already determined firms, so the entire column sum at \(f_r\) would have to come from \(t_r\). Therefore
\(x_{t_r,f_r}=1/\tau.\)
But this exhausts the row sum of \(t_r\), contradicting its positive mass at \(f_j\).
Thus \(t_r\) has no mass at firms after \(f_r\), and it has none at firms before \(f_r\). Its row sum consequently forces \(x_{t_r,f_r}=1/\tau\). This completes the induction.
Therefore \(x=x^*\), proving uniqueness.
For \(\tau=1\), the consecutive-edge condition is vacuous and the single entry is necessarily \(1\), so the characterization also covers this case.
Combining the two directions, a fixed priority order has a unique complete locally stable mass matching precisely when every consecutive pair in that order is an edge.
A Hamiltonian path is a sequence containing every vertex exactly once, with an edge between each consecutive pair. Therefore
\(\exists\pi\text{ yielding a unique complete locally stable mass matching}\quad\Longleftrightarrow\quad H\text{ has a Hamiltonian path}.\)
Undirected Hamiltonian Path is \(\mathrm{NP}\text{-complete}\); this standard hardness fact is also stated in this [research paper on Hamiltonian paths and cycles](https://arxiv.org/abs/2309.09228).
The reduction preserves the graph. Given a finite simple undirected graph with \(\tau\ge1\) vertices, create one type per vertex, each with mass \(1/\tau\), and \(m=\tau\) firms, each with capacity \(1/\tau\), with the stipulated common firm ranking. All required hypotheses hold.
The rational number \(1/\tau\) has a binary numerator-denominator encoding of length \(O(\log(\tau+1))\). Thus, if the source graph has encoding length \(L_H\), the constructed instance has length \(O(L_H+\tau\log(\tau+1))\) and is produced in polynomial time. The proved equivalence makes this a many-one reduction.
A certificate is a permutation of the \(\tau\) types, of length \(O(\tau\log(\tau+1))\). The verifier checks that it contains every type exactly once and that each consecutive pair is an edge. Sections 2–3 prove that these checks are necessary and sufficient, including for matchings with arbitrary real entries.
On a standard word RAM, reading the input and constructing an adjacency matrix takes \(O(L+\tau^2)\) time; checking the certificate then takes \(O(\tau)\) time. Since \(m=\tau\), the total is \(O(L+m\tau)\).
Alternatively, using repeated sequential scans of the binary edge list gives a conservative verifier bound of \(O(\tau L+\tau^2\log(\tau+1))\) bit operations, also polynomial in \(m,\tau,L\).
Thus the problem belongs to \(\mathrm{NP}\) and is \(\mathrm{NP}\text{-hard}\), completing the proof of \(\mathrm{NP}\text{-completeness}\).
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The argument establishes the exact characterization for arbitrary real mass splitting and correctly derives \(\mathrm{NP}\)-completeness. I found no major or minor gaps.
Each type \(t_r\) assigns its entire mass \(1/\tau\) to firm \(f_r\). Every row and column therefore has the required sum.
For an edge \(\{t_r,t_s\}\) with \(r<s\), the only positive entries for its endpoints occur at firm indices \(r\) and \(s\), respectively. A forbidden product would require the higher-priority endpoint’s firm index to exceed the lower-priority endpoint’s index. That cannot occur. This checks every stability constraint involving that edge.
The proposed swap preserves all row and column sums and produces a distinct array because \(1/\tau>0\).
The stability argument is valid: any other type has priority index either less than \(r\) or greater than \(r+1\), and its firm lies correspondingly before or after both swapped firms. Thus the swap reverses the firm order only for the pair \(\{t_r,t_{r+1}\}\). By hypothesis, this pair is not an edge, so its reversal violates no stability constraint.
Consequently, any priority order yielding uniqueness must have an edge between every consecutive pair.
Each support \(S_r\) is nonempty because its row sum is positive, and its minimum and maximum exist because there are finitely many firms.
If \(a_r>b_{r+1}\), the entries at those two indices are positive by definition. Their product violates precisely the stability constraint for the consecutive edge, with \(i=b_{r+1}<j=a_r\). Therefore \(a_r\le b_{r+1}\).
Combining these inequalities with \(b_r\le a_r\) correctly gives \(a_r\le b_s\) for every \(r<s\). This argument permits equality, as required: stability does not forbid two adjacent types from supporting the same firm.
Under the induction hypothesis, earlier types fill their corresponding firms completely. Nonnegativity and the column sums then prohibit any remaining type from assigning mass to those firms.
If \(t_r\) assigns positive mass to some \(f_j\) with \(j>r\), then \(a_r>r\). The previously established support inequalities force every later type’s minimum supported firm index to exceed \(r\). Hence later types assign no mass to \(f_r\). Earlier types also assign no mass there, by the induction hypothesis.
The required column sum at \(f_r\) therefore forces \(x_{t_r,f_r}=1/\tau\). This exhausts the row sum of \(t_r\), contradicting its assumed positive entry at \(f_j\).
Thus \(t_r\) supports neither earlier nor later firms, and its row sum forces its entire mass onto \(f_r\). The empty induction hypothesis at \(r=1\) is valid. At \(r=\tau\), there are no later firms, so the same conclusion follows without requiring any nonexistent later type.
This proves equality of arrays, which is exactly the task’s definition of uniqueness. No integrality or rationality assumption on matching entries is used.
When \(\tau=m=1\), the only entry equals \(1\), and the consecutive-edge condition is vacuous. The claimed characterization therefore holds on the full stated domain.
A strict priority order lists every vertex exactly once. Requiring an edge between every consecutive pair is exactly the definition of a Hamiltonian path; neither prescribed endpoints nor an edge closing a cycle is required.
The cited external fact concerns deciding Hamiltonian-path existence in general undirected graphs. The linked paper explicitly confirms its \(\mathrm{NP}\)-completeness. Its separate results for bounded independence number do not restrict the hardness fact used here. [Cited paper](https://arxiv.org/abs/2309.09228)
The reduction preserves the graph and constructs precisely the equal-mass, equal-capacity instance required by the task. The numerator-denominator encoding of \(1/\tau\) requires \(O(\log(\tau+1))\) bits. The stated output-length bound is therefore valid, and construction is polynomial in the explicit source input length. The proved equivalence supplies both directions of the many-one reduction.
The certificate is a permutation, whose encoding has length \(O(\tau\log(\tau+1))\). Checking its validity and consecutive edges suffices by the established characterization. No certificate containing real matching entries is needed.
On the stated word-RAM model, the adjacency-matrix preparation and certificate checks fit within \(O(L+\tau^2)=O(L+m\tau)\). The alternative bound of \(O(\tau L+\tau^2\log(\tau+1))\) bit operations is a valid conservative polynomial verification bound. Because the support is explicitly listed, \(\tau\) is bounded by the input length; these are polynomial bounds in the required input model.
The output fully resolves the assigned continuous decision problem. No additional clarification or 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.