| paper | Stable Matching with Uncertain Linear Preferences |
| authors | H. Aziz, P. Biró, Serge Gaspers, Ronald de Haan, Nicholas Mattei, B. Rastegari |
| venue | SAGT 2016 |
| filed under | coalition · matching |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\), even with equal uniform type masses and at most \(16\) profiles. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 11
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 two-sided high-multiplicity market with finite agent types, rational type masses, correlated finite preference scenarios, and decision variable \(x\) recording an aggregate matching coupling; the question is robust feasibility, with every individual receiving an integral partner despite type mass being split in \(x\).
The best objection is that allowing \(x_{m,w}\) to split type mass destroys the integral color gadgets, so Theorem 11's discrete hardness proof does not transfer without a new argument.
fatal: False
The mirror covers Theorem 11's robust-existence problem directly and Theorem 6's probability problem under a shared type-level signal; it leaves the compact-indifference results, probability algorithms, and remaining restrictions untreated.
The strongest positive case is a genuine high-multiplicity mirror of the paper’s uncertainty problems. My lead anchor is Theorem 6.
Take finite male types \(M\) and female types \(W\). A type is a complete profile: side of the market, acceptable partners, and a probability distribution over strict rankings of the opposite types. The society is given by rational masses \(\alpha_m\) and \(\beta_w\), with \(\sum_m\alpha_m=\sum_w\beta_w=1\). A matching is an aggregate coupling \(x=(x_{m,w})\), where \(x_{m,w}\) is the mass of men of type \(m\) matched to women of type \(w\), with the appropriate row and column sums. No individual receives a fractional partner; \(x\) records the partners of a large homogeneous cohort.
Because independent random preferences for infinitely many individuals would make “the whole matching is stable” degenerate, the natural high-multiplicity uncertainty model is a type-level latent refinement: each type independently draws one ranking from its lottery, and all mass of that type shares that realized ranking. This is plausible for a large cohort governed by one unresolved institutional ranking, evaluation rule, or common information signal.
For a realized profile \(\omega\), define
\[ U^\omega_{m,w}(x)= \sum_{w':\,w\succ^\omega_m w'}x_{m,w'} \]
and
\[ V^\omega_{m,w}(x)= \sum_{m':\,m\succ^\omega_w m'}x_{m',w}. \]
The coupling \(x\) is stable in \(\omega\) if, for every pair of types \((m,w)\), \(U^\omega_{m,w}(x)=0\) or \(V^\omega_{m,w}(x)=0\). Otherwise a positive mass of type \(m\) wants type \(w\), and a positive mass of type \(w\) wants type \(m\), so the pair can block.
This gives the precise problem
\[ \textsc{HM-StabilityProbability}: \]
given the type masses, the type-level lotteries, and a rational mass matching \(x\), compute exactly
\[ \Pr_{\omega}[x\text{ is stable in }\omega]. \]
The anchor is Theorem 6, proved in the paper: for the lottery model, \(\textsc{StabilityProbability}\) is \(\#P\)-complete even when every agent has at most two possible preference orderings. The proof reduces counting satisfying assignments of a 2CNF formula to the probability that a fixed matching is stable: each variable is represented by a two-choice preference, and the fixed matching is stable exactly for the satisfying assignments. This is a hardness result established by the authors, not merely cited elsewhere. [The paper’s Theorem 6](https://pmc.ncbi.nlm.nih.gov/articles/PMC7066306/#Sec4)
The continuous version preserves that reduction almost literally. Replace every named agent in the construction by a positive-mass type, give each type the same two rankings, and replace the discrete matching by the corresponding mass coupling. Since every type has positive mass, a blocking pair exists in the continuous model exactly when the corresponding named pair blocks in the discrete construction. The probability is therefore the normalized number of satisfying assignments.
I would expect this mirror to be Class B: hardness transfers. The difficulty is carried by the number of distinct preference types, not by the number of named agents. We can have an arbitrarily large society—say, millions of residents represented by \(O(n)\) repeated preference and qualification types—without changing the computation. This is precisely the high-multiplicity regime the programme wants to test. The paper’s authors should recognize the question: it asks whether one prescribed assignment remains stable under uncertain preference refinements, with the population represented by masses rather than an explicit list of individuals.
A second, independently worthwhile mirror comes from the paper’s joint probability model. Let \(\Omega\) be a finite set of deterministic preference profiles over the same male and female types, with rational probabilities. Define
\[ \textsc{CertainlyStableMassMatching}: \]
given the type masses and the scenario distribution, does there exist a mass coupling \(x\) that is stable in every profile \(\omega\in\Omega\) of positive probability? A solution is the coupling \(x\), if one exists.
This is the direct continuous analogue of the paper’s requirement that one matching be stable with probability \(1\). It is especially clean because the paper’s joint model already allows correlated uncertainty over entire preference profiles; no independence assumption has to be imposed on a continuum of individuals.
The anchor is Theorem 11, also proved in the paper: under the joint probability model, \(\textsc{ExistsCertainlyStableMatching}\) is NP-complete, by reduction from 3-Coloring. Profile \(P_0\) forces each vertex gadget to use one of three cyclic matchings, interpreted as the three colors. For every edge \(e\) and color \(c\), profile \(P_{e,c}\) makes the corresponding color choice impossible at both endpoints simultaneously. Thus a matching stable in every profile exists exactly when the graph is properly 3-colorable. [The paper’s Theorem 11](https://pmc.ncbi.nlm.nih.gov/articles/PMC7066306/#Sec7)
I would expect this mirror also to be Class B, although it has a proof obligation that the discrete problem does not: one must show that allowing a type mass to split among several partners does not destroy the gadget. The expected route is a support argument. The \(P_0\) gadget should restrict each vertex’s positive support to the three cyclic patterns, while \(P_{e,c}\) should forbid both endpoints from assigning positive mass to color \(c\). Choosing any supported color for each vertex would then yield a proper 3-coloring. If that lemma fails, the failure would itself be informative: fractional mass matching would be exactly where continuization dissolves the discrete obstruction.
The regime is plausible for large matching markets: repeated cohorts of applicants, residents, interns, or employees with the same qualifications, eligibility constraints, and preference-information state. The population may be enormous while the number of distinct types remains moderate. Mass is the honest quantity because statements such as “\(12\%\) of applicants with profile \(t\) are assigned to hospital type \(h\)” are more natural than naming every individual.
I would not stretch this case to the paper’s compact-indifference Theorem 9 without further conventions. Independent tie-breaking by infinitely many individuals again creates a degeneracy, and a type-level common tie-breaking rule would need explicit justification. The two mirrors above are enough: one transfers a strong \(\#P\)-hardness result, while the other transfers a robust-existence NP-completeness result.
The weakest point is therefore clear: the first mirror changes individual-level lottery uncertainty into correlated type-level uncertainty. That is not cosmetic. If a referee insists that every clone must draw independently, the probability of global stability is generally no longer the paper’s meaningful quantity. The second mirror is safer because its uncertainty is already profile-level. Subject to that modelling choice—and to the fractional-support lemma for Theorem 11—this is a substantive continuous-population programme, not merely a replacement of integer counts by decimal notation.
The strongest objection is that Theorem 6 does not survive the natural high-multiplicity interpretation of its lottery model. If a positive-mass cohort consists of independently uncertain agents, then in the continuum every preference in its support appears with its law-of-large-numbers mass almost surely. For a fixed aggregate matching \(x\), stability is therefore almost surely either true or false:
\[ \Pr[x\text{ is stable}]\in\{0,1\}. \]
The paper’s \(\#P\)-hard probability, which counts Boolean assignments of individual agents, disappears. If matching may condition on realized preferences, the uncertainty likewise disappears into a deterministic distribution of realized subtypes. The proponent avoids this only by giving each entire type one shared random ranking. That is a plausible common-signal model, but it is correlated uncertainty at the cohort level, not a high-multiplicity version of the paper’s independent lottery model. Moreover, in the proposed reduction the actual masses never matter: only whether they are positive matters. The construction is therefore finite profile counting with duplicated agents, rather than a computation about a continuous population.
Theorem 11 has a more serious obstruction. Its reduction relies on each vertex gadget choosing one of three integral cyclic matchings. A mass matching may split a type across several partners, and \(P_0\) does not itself prevent that. Give each \(m_i\) and \(w_i\) mass \(1/3\), and set
\[ x_{m_1,w_1}=x_{m_1,w_2} =x_{m_2,w_2}=x_{m_2,w_3} =x_{m_3,w_3}=x_{m_3,w_1} =\frac16, \]
with all other entries zero. Under the preferences in \(P_0\), this is stable according to the proponent’s own condition: for every pair of types, either \(U^\omega_{m,w}(x)=0\) or \(V^\omega_{m,w}(x)=0\). Yet it is not any of the three colour matchings. Thus \(P_0\) does not force a vertex to have a recoverable colour, and the claimed support argument is unavailable. The \(P_{e,c}\) profiles were designed to exclude integral colour choices; the paper gives no argument that they exclude all fractional couplings.
One could impose purity—requiring every vertex mass to use one cyclic pattern—or add new gadgets enforcing it. The former simply reinstates a discrete matching on types; the latter would be a new reduction for a new robust fractional-stability problem, not a transfer of Theorem 11.
This is the strongest honest negative case, but it does not establish the universal claim. The robust problem of finding a fractional type coupling stable across finitely many common preference profiles is itself well-posed, population-specific, and potentially valuable even if the paper’s reduction fails. Likewise, a shared institutional signal for a large cohort is a defensible scenario. So the negative case defeats the proponent’s claimed reductions, especially the second as currently argued, but it cannot honestly conclude that no worthwhile continuous mirror exists.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.