Answer: \(\mathrm{NP}\text{-complete}\), even with equal uniform type masses and at most \(16\) profiles.
Theorem 11 — class: hardness
Given finite male types \(M\) and female types \(W\), rational masses \((\alpha_m)_{m\in M}\) and \((\beta_w)_{w\in W}\), and a finite rational distribution over preference profiles \(\Omega\), does there exist a coupling \(x=(x_{m,w})_{m\in M,w\in W}\ge0\) with row sums \(\alpha\) and column sums \(\beta\) that is stable in every \(\omega\in\Omega\)? Stability means that for every type pair \((m,w)\), either \(\sum_{w':\,w\succ_m^\omega w'}x_{m,w'}=0\) or \(\sum_{m':\,m\succ_w^\omega m'}x_{m',w}=0\).
A society is given by its support: nonempty finite sets of male types \(M\) and female types \(W\), each type having positive binary rational mass. Let \(\tau=|M|+|W|\) be the support size, not the number of possible types, and let \(m=\max\{|M|,|W|\}\). Normalize \(\sum_{a\in M}\alpha_a=\sum_{b\in W}\beta_b=1\).
The input also explicitly lists a nonempty support \(\Omega\) of \(k\) preference profiles with positive binary rational probabilities summing to \(1\). Each profile specifies, for every type, a strict complete ranking of all opposite-side types; all partners are acceptable. Let \(L\) be the total binary input length.
A coupling is a real matrix \(x\geq0\) satisfying \(\sum_{b\in W}x_{a,b}=\alpha_a\) and \(\sum_{a\in M}x_{a,b}=\beta_b\). It is stable in profile \(\omega\) if, for every \((a,b)\in M\times W\), either \(\sum_{b':\,b\succ_a^\omega b'}x_{a,b'}=0\) or \(\sum_{a':\,a\succ_b^\omega a'}x_{a',b}=0\). Certainly stable means stable in every profile in \(\Omega\).
Is deciding whether a certainly stable coupling exists solvable in polynomial time in \(m,\tau,k,L\), or is it NP-hard?
For discrete agents with strict complete rankings and an explicitly listed joint distribution over profiles, existence of a certainly stable matching is NP-complete, even with only \(16\) profiles. [Aziz et al.](https://link.springer.com/article/10.1007/s00453-019-00650-0)
No result settling this precise coupling-existence problem was located in the literature search.
The coupling-existence problem is \(\mathrm{NP}\)-complete, even when \(|M|=|W|=n\), every type has mass \(1/n\), and there are at most \(16\) profiles.
The key fact is that, for uniform masses, any certainly stable coupling contains a certainly stable discrete matching in its positive support.
For a nonnegative matrix \(x\), define its positive support by
\(
E(x)=\{(a,b):x_{a,b}>0\}.
\)
Lemma 1. Suppose \(x\) is stable in a profile \(\omega\). If \(y\) is a coupling satisfying \(E(y)\subseteq E(x)\), then \(y\) is stable in \(\omega\).
Proof. Fix a pair \((a,b)\). Stability of \(x\) means that at least one of
\(
\sum_{b':\,b\succ_a^\omega b'}x_{a,b'}
\quad\text{and}\quad
\sum_{a':\,a\succ_b^\omega a'}x_{a',b}
\)
is zero.
Every summand is nonnegative. Consequently, a zero sum forces all its summands to be zero. Support containment forces the corresponding entries of \(y\) to be zero as well. Thus the same sum is zero for \(y\), proving its stability at \((a,b)\). This holds for every pair. \(\square\)
Applying the lemma separately to each profile shows that support restriction also preserves certain stability.
Lemma 2. Suppose \(|M|=|W|=n\) and \(\alpha_a=\beta_b=1/n\) for every type. A certainly stable coupling exists if and only if a perfect matching stable in every listed profile exists.
Proof.
First, let \(\mu:M\to W\) be a perfect matching, and define
\(
y^\mu_{a,b}=
\begin{cases}
1/n,&b=\mu(a),\\
0,&b\ne\mu(a).
\end{cases}
\)
This is a coupling with the required margins.
In any profile \(\omega\), its two dissatisfaction sums at \((a,b)\) are
\(
\sum_{b':\,b\succ_a^\omega b'}y^\mu_{a,b'}
=\frac1n\,\mathbf{1}\{b\succ_a^\omega\mu(a)\}
\)
and
\(
\sum_{a':\,a\succ_b^\omega a'}y^\mu_{a',b}
=\frac1n\,\mathbf{1}\{a\succ_b^\omega\mu^{-1}(b)\}.
\)
Both sums are positive exactly when \((a,b)\) is a discrete blocking pair. Hence \(y^\mu\) is stable in \(\omega\) exactly when \(\mu\) is stable there. This proves one direction.
Conversely, let \(x\) be a certainly stable coupling. Consider the finite bipartite graph with vertex classes \(M,W\) and edge set \(E(x)\). For \(S\subseteq M\), let \(N(S)\subseteq W\) be its neighborhood. The margin equations give
\(
\frac{|S|}{n}
=\sum_{a\in S}\sum_{b\in N(S)}x_{a,b}
\leq
\sum_{b\in N(S)}\sum_{a\in M}x_{a,b}
=\frac{|N(S)|}{n}.
\)
Thus \(|N(S)|\geq|S|\) for every \(S\subseteq M\). Hall’s marriage theorem applies and supplies a matching saturating \(M\); because both vertex classes have size \(n\), this is a perfect matching \(\mu\).
The coupling \(y^\mu\) defined above satisfies \(E(y^\mu)\subseteq E(x)\). By Lemma 1 it is stable in every listed profile. The displayed characterization of its dissatisfaction sums then shows that \(\mu\) is stable in every profile. \(\square\)
The discrete result needed here is precisely Corollary 6 of [Aziz et al., *Stable Matching with Uncertain Linear Preferences*](https://link.springer.com/article/10.1007/s00453-019-00650-0): deciding whether a certainly stable matching exists in the explicitly listed joint probability model is \(\mathrm{NP}\)-complete even with \(16\) profiles. Their setting uses equal numbers of men and women, strict complete rankings, and universal acceptability.
Take such a discrete instance with \(n\) agents on each side. Construct the coupling instance as follows:
Give the listed profiles equal positive probabilities. Their precise probabilities do not affect certain stability. If duplicate profiles occur, merge them; this leaves at most \(16\) profiles.
Every stable matching in the source instance is perfect: an incomplete matching leaves both a man and a woman unmatched, and their pair blocks because all partners are acceptable. Therefore Lemma 2 proves the equivalence
\(
\text{the discrete instance has a certainly stable matching}
\quad\Longleftrightarrow\quad
\text{the constructed instance has a certainly stable coupling}.
\)
The construction is polynomial. Each mass \(1/n\), represented by a binary numerator and denominator, requires \(O(\log n)\) bits. Rankings are copied without expansion, and profile probabilities require polynomially many bits. Moreover, the constructed parameters are \(m=n\) and \(\tau=2n\).
This proves \(\mathrm{NP}\)-hardness for the stated restricted family.
Real-valued witnesses require some care. We prove that every yes-instance has a rational witness of polynomial encoding length.
Lemma 3. If a certainly stable coupling exists, then one exists whose positive-support graph is a forest.
Proof. Start with any certainly stable coupling \(x\). If its positive-support graph contains a cycle, the cycle has even length because the graph is bipartite. Label its edges alternately with plus and minus signs.
Let \(t>0\) be the minimum entry of \(x\) on the minus edges. Add \(t\) on the plus edges and subtract \(t\) on the minus edges.
At every cycle vertex, one incident entry increases and another decreases by the same amount. Thus all row and column sums remain unchanged. Entries remain nonnegative, at least one minus edge becomes zero, and no previously zero entry becomes positive. Lemma 1 preserves certain stability.
Each operation strictly decreases the number of positive entries. After finitely many operations, the positive-support graph is a forest. \(\square\)
Now write all input masses as binary-encoded fractions, and let \(Q\) be the product of their denominators. Its binary length is \(O(L)\), since the sum of the denominators’ encoding lengths is at most \(L\).
Let \(z\) be the forest-supported coupling supplied by Lemma 3. Consider any positive edge \(e=(a,b)\). Deleting \(e\) from its tree leaves two components; let \(C\) be the component containing \(a\). Subtracting the column-margin equations for women in \(C\) from the row-margin equations for men in \(C\) gives
\(
z_{a,b}
=
\sum_{u\in M\cap C}\alpha_u
-
\sum_{v\in W\cap C}\beta_v.
\)
To justify this identity, every edge internal to \(C\) appears once in each sum and cancels. The only positive edge crossing its boundary is \(e\), whose male endpoint lies in \(C\), so its contribution is \(+z_{a,b}\).
Consequently, \(Qz_{a,b}\) is an integer. Also \(0\leq z_{a,b}\leq1\), so every entry has the form \(r_{a,b}/Q\) with an integer satisfying \(0\leq r_{a,b}\leq Q\). Each numerator therefore has \(O(L)\) bits. Since there are at most \(|M||W|\) entries, the whole witness has polynomial encoding length.
A verifier computes \(Q\), reads the integer numerators, and checks by exact integer arithmetic:
There are polynomially many checks in \(m,\tau,k,L\), and all integers involved have polynomial bit length. Thus verification runs in polynomial time, proving membership in \(\mathrm{NP}\).
The problem is \(\mathrm{NP}\)-complete. Allowing divisible mass does not defeat the discrete hardness: uniform margins force a perfect matching inside the positive support, and that matching inherits stability simultaneously across all profiles. A polynomial-time algorithm in \(m,\tau,k,L\) would therefore imply \(\mathrm{P}=\mathrm{NP}\).
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the stated coupling-existence problem. It establishes \(\mathrm{NP}\)-completeness, including the restriction to equal uniform masses and at most \(16\) profiles. I found no mathematical gaps requiring repair.
Lemma 1 correctly uses both nonnegativity and support containment.
For each fixed pair and profile, stability of \(x\) supplies at least one zero dissatisfaction sum. Because its summands are nonnegative, every entry occurring in that sum is zero. The containment \(E(y)\subseteq E(x)\) forces those same entries of \(y\) to vanish. Consequently, the corresponding dissatisfaction sum for \(y\) is zero.
The argument applies to every pair and independently to every profile. It does not require the same zero-sum alternative to hold across profiles. The lemma also correctly assumes that \(y\) is already a coupling; support restriction alone would not ensure the prescribed margins.
Assessment: Correct.
Both directions of Lemma 2 are valid.
From a perfect matching to a coupling. The matrix \(y^\mu\) has exactly one entry \(1/n\) in every row and column, so it satisfies all margins. Each displayed dissatisfaction sum is \(1/n\) precisely when the corresponding agent strictly prefers the proposed partner to its assigned partner, and otherwise is zero.
Thus both sums are positive precisely for a blocking pair. A pair already belonging to the matching causes no exception: strict preferences never rank an assigned partner above itself, so both indicators vanish there.
From a coupling to a perfect matching. The support graph is finite and bipartite. For every \(S\subseteq M\), all positive entries incident to \(S\) terminate in \(N(S)\), which justifies the first equality in the displayed calculation. Nonnegativity justifies enlarging the sum to all men, and the column margins justify its final equality.
The resulting inequality is exactly Hall’s condition. Hall’s marriage theorem states that a finite bipartite graph has a matching saturating its left vertex class if every subset of that class has at least as many neighbors. The proof verifies this condition for every \(S\), including the empty set. Equal side sizes then make the matching perfect.
The selected edges belong to \(E(x)\), so the resulting matching coupling inherits stability in every profile by Lemma 1. The already established blocking-pair characterization transfers that stability back to the discrete matching.
Nonempty supports ensure \(n\geq1\); there is no division-by-zero or singleton-case problem.
Assessment: Correct.
The external theorem is accurately identified. Corollary 6 of Aziz et al. states that existence of a certainly stable matching in the joint probability model is \(\mathrm{NP}\)-complete with only \(16\) profiles. The paper’s setting uses equally sized sides, linear rankings, complete lists, and universal acceptability. These are the hypotheses required by the reduction. [Aziz et al., *Stable Matching with Uncertain Linear Preferences*](https://link.springer.com/article/10.1007/s00453-019-00650-0)
The proof cites this result as an external theorem; it need not reproduce the theorem’s hardness construction. Its statement and applicable hypotheses are sufficiently specified and match the cited source.
Assessment: The citation supports exactly the hardness claim used.
The reduction satisfies the target’s input requirements:
Changing positive probabilities does not change which matchings are certainly stable: with finite positive support, probability-one stability is equivalent to stability in every supported profile. Merging duplicate profiles also preserves that condition and leaves a nonempty support with at most \(16\) profiles.
The statement that every source stable matching is perfect is correct. With equally sized sides, any incomplete matching leaves an unmatched agent on each side. Universal acceptability makes that pair blocking.
Lemma 2 therefore supplies both directions of the required yes-instance equivalence. The construction’s encoding bound is also correct: binary numerator-denominator representation of \(1/n\) uses \(O(\log n)\) bits, and rankings are copied without expansion. Here \(m=n\) and \(\tau=2n\), so the reduction establishes hardness for the parameters actually specified in the task.
Assessment: Valid polynomial many-one reduction.
Lemma 3 correctly preserves feasibility and certain stability during every cycle elimination.
A cycle in the bipartite support graph has even length. Alternating signs therefore give one increasing and one decreasing cycle edge at each cycle vertex. Choosing the minimum positive entry on the decreasing edges ensures that:
Lemma 1 then preserves stability in all profiles. The number of positive entries strictly decreases at every operation and is finite initially. Termination with an acyclic support follows.
This argument is an existence argument, so starting from an arbitrary real coupling introduces no algorithmic assumption or witness-encoding problem.
Assessment: Correct.
The common denominator \(Q\) has polynomial bit length: the bit length of a product is bounded by the sum of the factors’ bit lengths, up to a constant, and these denominators are part of the input.
The cut identity for a positive forest edge has the correct sign. After deleting \(e=(a,b)\), the component \(C\) containing \(a\) has only that positive edge crossing its boundary in the original support. Internal entries cancel between the row and column totals. Since the crossing edge’s male endpoint lies in \(C\), its remaining contribution is \(+z_{a,b}\).
Hence every positive entry is an integer multiple of \(1/Q\). Zero entries have the same representation. Normalization and nonnegativity give \(0\leq z_{a,b}\leq1\), so the numerators have \(O(L)\) bits.
The certificate contains polynomially many entries. Exact checks of margins and dissatisfaction sums involve polynomially many operations on integers of polynomial bit length. Explicitly listing the types and rankings also ensures that the matrix dimensions and profile count are bounded by the input size, as needed for ordinary \(\mathrm{NP}\) membership.
Assessment: Correct polynomial-size certificate and polynomial-time verifier.
The output establishes both hardness and membership in \(\mathrm{NP}\). Its conclusion applies to the continuous coupling problem itself, rather than merely to discrete matchings. 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.