Answer: \(\mathrm{NP}\text{-complete}\), even with equal dyadic masses on equally sized supports.
Theorem 4 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateExistsCertainlyStableMatching is NP- complete, even if all agents are certain.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given finite type sets \(M\) and \(W\), rational masses \(\mu_i,\nu_j\) summing to one on each side, and complete deterministic pairwise preference relations over opposite-side types that may be cyclic, does there exist a nonnegative flow \(x_{ij}\) with \(\sum_j x_{ij}=\mu_i\) and \(\sum_i x_{ij}=\nu_j\) such that for every pair \(i,j\), \(A_{ij}(x)=\sum_{j':\,j\succ_i j'}x_{ij'}\) and \(B_{ij}(x)=\sum_{i':\,i\succ_j i'}x_{i'j}\) are not both positive?
Let \(M,W\) be nonempty finite sets of types. Each society is given by its support: the list of types with positive mass, each mass a binary rational. Write \(\tau=|M|+|W|\) for the total support size, not the number of possible types, \(m=\max\{|M|,|W|\}\), and \(L\) for the total input bit length. Masses satisfy \(\sum_{i\in M}\mu_i=\sum_{j\in W}\nu_j=1\).
Each type has an explicitly given strict pairwise preference relation over opposite-side types: for distinct types exactly one direction holds, self-comparisons never hold, and cycles are allowed on either side. All opposite-side types are acceptable; individuals of the same type are indifferent.
A complete allocation is a real flow \(x\in\mathbb R_{\ge0}^{M\times W}\) with \(\sum_jx_{ij}=\mu_i\) and \(\sum_ix_{ij}=\nu_j\). Define \(A_{ij}(x)=\sum_{j':\,j\succ_i j'}x_{ij'}\) and \(B_{ij}(x)=\sum_{i':\,i\succ_j i'}x_{i'j}\). It is stable if, for every \((i,j)\in M\times W\), \(A_{ij}(x)=0\) or \(B_{ij}(x)=0\), including pairs with \(x_{ij}>0\).
Is deciding whether such a stable complete allocation exists solvable in polynomial time in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?
For discrete agents, existence of a stable complete matching is \(\mathrm{NP}\)-complete even with deterministic pairwise preferences; it is polynomial-time solvable when preferences on one side are transitive. [Aziz et al.](https://www.nickmattei.net/docs/pairwise.pdf)
No complexity result for the exact mass-flow problem above was located in the literature search.
The problem is \(\mathrm{NP}\)-complete, even when both sides have the same number of types and every type has the same dyadic mass. The key fact is that any perfect matching contained in a stable flow’s positive support inherits stability.
For a nonnegative matrix \(x\), define
\[
\operatorname{supp}(x)=\{(i,j):x_{ij}>0\}.
\]
Lemma 1. If \(x\) satisfies the stated stability condition and \(y\) is nonnegative with \(\operatorname{supp}(y)\subseteq\operatorname{supp}(x)\), then \(y\) also satisfies that condition.
Proof. Suppose some pair \((i,j)\) violates stability for \(y\). Thus \(A_{ij}(y)>0\) and \(B_{ij}(y)>0\).
Because these are finite sums of nonnegative entries, there are types \(j'\) and \(i'\) such that
\[
j\succ_i j',\qquad y_{ij'}>0,\qquad
i\succ_j i',\qquad y_{i'j}>0.
\]
Support containment gives \(x_{ij'}>0\) and \(x_{i'j}>0\). Consequently \(A_{ij}(x)>0\) and \(B_{ij}(x)>0\), contradicting stability of \(x\). This argument applies to every pair, including pairs with positive allocated mass. \(\square\)
Lemma 2. Suppose \(|M|=|W|=n\) and all masses equal \(1/n\). A stable complete allocation exists if and only if the corresponding discrete instance has a stable perfect matching.
Proof. First, let \(P\) be a stable perfect matching. Define \(y_{ij}=1/n\) on \(P\) and \(y_{ij}=0\) elsewhere. This is a complete allocation.
Write \(P(i)\) and \(P(j)\) for the partners of \(i\) and \(j\). Then
\[
A_{ij}(y)>0\quad\Longleftrightarrow\quad j\succ_i P(i),
\]
and
\[
B_{ij}(y)>0\quad\Longleftrightarrow\quad i\succ_j P(j).
\]
Both inequalities hold exactly when \((i,j)\) blocks the discrete matching. For matched pairs, both sums are zero because self-comparisons never hold. Thus \(y\) is stable.
Conversely, let \(x\) be a stable complete allocation. Form the bipartite graph with edge set \(\operatorname{supp}(x)\). For \(S\subseteq M\), let \(N(S)\) denote its neighbors. The marginal constraints imply
\[
\frac{|S|}{n}
=\sum_{i\in S}\sum_{j\in N(S)}x_{ij}
\leq\sum_{j\in N(S)}\sum_{i\in M}x_{ij}
=\frac{|N(S)|}{n}.
\]
Hence \(|N(S)|\geq|S|\) for every \(S\subseteq M\). By Hall’s marriage theorem, the support graph contains a matching \(P\) covering \(M\). Since the two sides have equal size, \(P\) is perfect.
The allocation assigning mass \(1/n\) along \(P\) has support contained in \(\operatorname{supp}(x)\), so Lemma 1 makes it stable. By the first part’s blocking-pair characterization, \(P\) is a stable discrete matching. \(\square\)
Neither lemma assumes transitive preferences.
The discrete source problem asks whether two equally sized sets of agents, with complete strict pairwise preferences that may contain cycles, admit a stable complete matching. This problem is \(\mathrm{NP}\)-complete by Theorem 4 of [Aziz et al., *Stable Matching with Uncertain Pairwise Preferences*](https://www.nickmattei.net/docs/pairwise.pdf), even when all comparisons are deterministic. In that restriction, every comparison between distinct candidates has exactly one preferred direction, as required here.
Take a source instance with \(n\geq1\) agents on each side. To ensure that the output masses are dyadic, put
\[
N=2^{\lceil\log_2 n\rceil}.
\]
Add \(N-n\) dummy agents on each side, arranged into designated pairs.
Specify preferences as follows:
These preferences are explicit strict pairwise relations, and all candidates remain acceptable.
The padded discrete instance has a stable perfect matching exactly when the original instance does. Indeed, a stable original matching extends by matching all designated dummy pairs. No pair involving a dummy can block because that dummy receives its first choice.
Conversely, every stable matching of the padded instance must contain every designated dummy pair: if such a pair were absent, its two endpoints would strictly prefer each other to their partners and would block. Restricting a stable padded matching to the original agents therefore gives a stable perfect matching of the original instance.
Now give every padded agent its own type and assign every type mass \(1/N\). Copy the padded preferences unchanged. Lemma 2 proves
\[
\text{original discrete instance has a stable perfect matching}
\quad\Longleftrightarrow\quad
\text{output mass-flow instance has a stable complete allocation}.
\]
The reduction is polynomial: \(N<2n\), each mass \(1/N\) is dyadic with encoding length \(O(\log n)\), and the explicit comparison tables contain \(O(N^3)\) entries. The output has \(m=N\) and \(\tau=2N\).
Thus the stated problem is \(\mathrm{NP}\)-hard even for equal dyadic masses.
Real-valued feasibility requires justification that polynomial-size certificates exist.
Write each input mass as a rational with positive integer denominator, and let \(Q\) be the product of all these denominators. Then \(Q\mu_i\) and \(Q\nu_j\) are integers, and the bit length of \(Q\) is \(O(L)\).
Suppose a stable complete allocation \(x\) exists, and set \(E=\operatorname{supp}(x)\). Construct a directed network with source \(s\), sink \(t\), and arcs:
The scaled allocation \(Qx\) induces a feasible flow of value \(Q\). The total capacity leaving \(s\) is exactly \(Q\), so the maximum flow value is \(Q\).
All capacities are nonnegative integers. The integral maximum-flow theorem therefore supplies an integral flow of value \(Q\). Since the source and sink capacities each sum to \(Q\), every source arc and every sink arc is saturated. Its middle-arc values \(z_{ij}\), extended by zero outside \(E\), satisfy
\[
\sum_j z_{ij}=Q\mu_i,\qquad
\sum_i z_{ij}=Q\nu_j.
\]
Consequently \(y=z/Q\) is complete and has support contained in that of \(x\). Lemma 1 makes \(y\) stable.
Each integer \(z_{ij}\) lies between \(0\) and \(Q\), so the entire matrix has polynomial encoding length. A verifier checks nonnegativity, the displayed marginal equalities, and, for every pair \((i,j)\), that at least one of the integer sums
\[
\sum_{j':\,j\succ_i j'}z_{ij'}
\qquad\text{and}\qquad
\sum_{i':\,i\succ_j i'}z_{i'j}
\]
is zero. These checks take polynomial time and are exactly the stability checks for \(z/Q\).
Hence the problem belongs to \(\mathrm{NP}\).
Stable complete allocation existence is \(\mathrm{NP}\)-complete under the exact stability definition in the question. In particular, a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The prover’s claim is proved. The argument establishes \(\mathrm{NP}\)-completeness for the exact mass-flow problem, including the restriction to equal dyadic masses on equally sized supports. No major or minor mathematical issues were found.
The proof correctly uses finiteness and nonnegativity: a positive sum contains a positive summand. Thus a violation of stability for \(y\) supplies two positive entries witnessing the same violation for \(x\), because \(\operatorname{supp}(y)\subseteq\operatorname{supp}(x)\).
The lemma concerns the stability condition alone; it does not claim that shrinking support preserves completeness. This distinction is respected in subsequent applications, where completeness is established separately.
The argument checks every pair, including allocated pairs, and requires no transitivity.
Assigning mass \(1/n\) to each matching edge gives the required row and column marginals.
Each row and column has exactly one positive entry. Consequently, the two displayed equivalences between positive stability sums and strict preference over the assigned partner are exact. Their conjunction is precisely the discrete blocking-pair condition.
For a matched pair, the only potentially nonzero summand would require a self-comparison, which is excluded. Thus the proof respects the task’s requirement to check stability even on positive allocation entries.
The displayed neighborhood inequality is valid for every \(S\subseteq M\). Every positive entry in a row indexed by \(S\) has its column in \(N(S)\); nonnegativity then permits comparison with the full column totals.
Hall’s theorem applies to the finite bipartite support graph: the established condition \(|N(S)|\geq|S|\) for every \(S\subseteq M\) guarantees a matching covering \(M\). Equal side sizes make that matching perfect.
The allocation on this perfect matching is complete and has support contained in the original support. Lemma 1 therefore applies. The previously established blocking-pair characterization then yields a stable discrete matching.
There is no integrality assumption on the original allocation and no use of transitivity.
The cited Theorem 4 states that existence of a certainly stable matching is \(\mathrm{NP}\)-complete even when all agents’ comparisons are certain. The paper’s model uses equally sized sides, complete pairwise comparisons, and complete matchings. Under deterministic comparisons, certain stability is exactly absence of a mutually strictly preferred blocking pair. Thus the cited restriction matches the prover’s source problem. [Aziz et al., *Stable Matching with Uncertain Pairwise Preferences*, preliminaries and Theorem 4](https://www.nickmattei.net/docs/pairwise.pdf).
The prover correctly states both the hardness restriction and the relevant preference properties; the citation is not being applied to a materially different matching model.
The preference specifications are mutually consistent. Preserving original comparisons does not conflict with placing original candidates above dummy candidates. Giving each dummy its designated partner above every other candidate is also compatible with completing the remaining comparisons.
The forward implication is valid: extending a stable original matching by designated dummy pairs introduces no blocking pair involving a dummy, since that dummy receives its preferred candidate over every alternative. Original-original blocking conditions remain unchanged.
The reverse implication is valid: if a designated dummy pair is absent from a perfect matching, both endpoints have different partners and strictly prefer each other. The pair therefore blocks. Every designated dummy pair must consequently be present, leaving a perfect matching among original agents. Any original blocking pair would also block the padded matching.
The normalization satisfies \(n\leq N<2n\), including \(n=1\), and \(1/N\) is a positive dyadic rational. The stated comparison-table size and mass encoding bounds are polynomial. The resulting parameters \(m=N\) and \(\tau=2N\) are correct.
The product \(Q\) of the input denominators clears all denominators and has bit length bounded by the total denominator encoding length, hence by \(O(L)\). Its numerical magnitude may be large, but this does not invalidate the certificate-size argument.
The network has finite nonnegative integer capacities. The scaled allocation supplies a feasible flow of value \(Q\); its middle-arc values respect capacity \(Q\), since every allocation entry is at most the total mass \(1\). The total source capacity gives the matching upper bound on flow value.
The integral maximum-flow theorem therefore applies exactly as stated and yields an integral flow of value \(Q\). Since both boundary capacity totals equal \(Q\), every source arc and sink arc is saturated. Flow conservation gives the displayed integer marginals.
The resulting allocation \(y=z/Q\) is complete, and its support is contained in the original support, so Lemma 1 establishes stability.
The certificate contains at most \(|M||W|\) integers, each with \(O(L)\) bits. The marginal and stability checks use polynomially many exact integer operations on polynomial-length numbers. Since \(Q>0\), testing the integer stability sums for zero is equivalent to testing the corresponding sums for \(y\).
Using the unknown original support in the certificate-existence argument is legitimate: the proof does not require a verifier to discover that support.
The reduction establishes \(\mathrm{NP}\)-hardness, and the certificate argument establishes membership in \(\mathrm{NP}\). Together they justify the full claimed classification. The consequence concerning a polynomial-time algorithm in \(m,\tau,L\) also follows.
No additional mathematical 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.