Try
Two people A and B are matched with X and Y: the fixed matching is A-X and B-Y. You know A prefers X to Y, and X prefers A to B. You do not know B’s or Y’s ranking. Can missing information change whether this matching is stable?
There are only two unmatched pairs to inspect. A-Y cannot block because A prefers its current partner X. B-X cannot block because X prefers its current partner A. Therefore neither missing ranking can create a blocking pair. The matching stays stable under every way of completing the missing comparisons.
| Unmatched pair | Assigned partners | Known refusing endpoint | Consequence |
|---|
| A-Y | A has X; Y has B | A has X>Y | Cannot block |
| B-X | B has Y; X has A | X has A>B | Cannot block |
Now remove X’s known comparison. Predict a completion that creates a blocker. Choose B to rank X above Y and X to rank B above A. These choices can coexist; they make B-X a blocking pair. A’s known comparison does not protect a pair of which A is not an endpoint. The matching may still be stable in other completions, but it is no longer guaranteed stable in all of them.
Predict
Our model has two equal finite sides and a fixed perfect matching. Every person’s true preferences are strict and complete over the entire opposite side. We know only some comparisons. Unknown means the comparison is unresolved; it does not mean an option is unacceptable or absent from the eventual ranking. This differs from a matching model with incomplete lists of acceptable partners.
For each person, draw an arrow from a preferred option to a less preferred option. Known comparisons must be consistent: their transitive consequences form a strict partial order, with no directed cycle. A completion is a strict total ranking respecting every known arrow. We allow each person to choose any such completion independently of everyone else.
Predict whether a missing direct arrow means that neither ordering is forced. Suppose A’s known arrows are X→Y and Y→Z. Even without a direct X→Z arrow, every completion places X above Z. Paths matter, not only individually recorded comparisons. If a cycle X→Y→Z→X appears instead, there is no strict complete ranking extending the reports. We reject those inconsistent data before making a stability claim.
Experiment
Fix the matching A-X, B-Y, C-Z. Use these known comparisons: A ranks X above Y and X above Z; B ranks Y above X; C has no known comparison; X ranks A above C; Y ranks B above C; Z ranks C above B. All other comparisons are unknown. List all six unmatched pairs and find one endpoint forced to refuse each.
Reveal the complete certificate
A refuses A-Y and A-Z. B refuses B-X. Z refuses B-Z because its current partner C is above B. X refuses C-X because A is above C, and Y refuses C-Y because B is above C. These six obligations exhaust the unmatched pairs. No condition on C’s preferences is needed, and several other comparisons can remain unresolved.
Change just X’s comparison: remove A>C, leaving X with no known comparisons. Construct a full completion that makes C-X block, while keeping every other reported comparison.
Reveal a changed full profile
Use A:X>Y>Z, B:Y>X>Z, C:X>Z>Y, X:C>A>B, Y:B>C>A, Z:C>B>A. Every surviving known comparison is respected. C prefers X to its partner Z, and X prefers C to its partner A, so C-X blocks. This completion refutes universal stability. It does not say that all completions of the changed data are unstable.
Understand
First establish the link between comparison paths and forced preferences. For two distinct options p and q in one person’s comparison graph, every completion places p above q if there is a directed path p→⋯→q: respecting the edges and transitivity forces that ordering.
Conversely, suppose there is no path from p to q. Add the arrow q→p. It cannot create a directed cycle, because such a cycle would need an existing path from p back to q. The resulting finite graph is acyclic and therefore has a total ordering respecting all arrows. To justify that last statement, an acyclic finite nonempty graph has a vertex with no incoming arrow: otherwise following incoming arrows would eventually revisit a vertex, forming a cycle. Put such a vertex first, remove it and repeat. This produces a strict complete ranking and, with the added arrow, places q above p. Thus p is forced above q exactly when p reaches q in the comparison graph.
Apply this fact with p equal to a person’s assigned partner and q equal to an alternative. Our criterion is:
The fixed matching is stable in every independent completion exactly when each unmatched pair has at least one endpoint forced to prefer its assigned partner to the other endpoint.
For sufficiency, take any allowed joint completion and any unmatched pair. Its certified endpoint still prefers the assigned partner, so the pair cannot block. Since the certificate covers every unmatched pair, the matching is stable in that completion. The completion was arbitrary, so stability is universal.
For necessity, argue by contraposition. Suppose an unmatched pair has no such forced-refusal endpoint. At each endpoint there is no comparison path from the assigned partner to the other person. By the preceding extension argument, that endpoint has a valid completion preferring the other person to the assigned partner. Choose both completions together. This is exactly where independence is needed. All other people’s acyclic comparison graphs also have extensions, so complete their rankings arbitrarily. The selected pair now blocks in a valid full profile, refuting universal stability.
The theorem does not require finding every possible completion. A positive certificate is a list of refusing endpoints and comparison paths, one for every unmatched pair. A negative certificate is one pair together with two compatible endpoint rankings and, if a full profile is requested, extensions for everyone else. The proof constructs these certificates rather than relying on a visual guess about the number of unknown comparisons.
The consistency assumption is essential to the meaning of the answer. A universal statement over zero completions is formally true, but a cyclic ranking report is an invalid instance of this model, not evidence that a real matching is protected from blocking. By contrast, an instance with zero people has the empty profile as a genuine completion and no unmatched pairs; its empty matching is validly stable.
Apply
Separate possible stability from necessary stability. With no known comparisons in the two-by-two instance, rank every assigned partner first to obtain a stable completion. Alternatively rank A:Y>X and Y:A>B; give B and X any complete rankings. Then A-Y blocks. Both kinds of completion are allowed. One stable completion proves existence, while one blocking completion refutes necessity. Neither witness proves that every completion has its own property.
For a different change, suppose every person is known to prefer its assigned partner to every alternative, but all comparisons among alternatives are unknown. Every unmatched pair is refused. Resolving those lower ranks cannot change the conclusion. Missing information is relevant only through the comparisons needed by the pair obligations, including their transitive consequences.
Finally, consider a model where people’s unknown rankings are correlated and only two full profiles are permitted. In one, A wants Y but Y prefers B; in the other, Y wants A but A prefers X. Fix B:Y>X and X:A>B in both. Both profiles are stable, yet neither A nor Y is always a refusing endpoint for A-Y. There is no contradiction: combining the two desire-to-swap rankings is disallowed by the correlated model. Our necessity proof expressly assumed independent extensions. Check that assumption before transferring the criterion to jointly constrained data.
Continue
Return to the blocking-pair definitions if you need to revisit strict preference stability. In this lesson the matching stays fixed; the uncertainty concerns the rankings, not whether an algorithm will find a new matching.
The practice asks for complete pair audits, transitive comparison paths, failed certificates and explicit blocking completions. State which family of profiles you quantify over. A conclusion about one completion, every independent completion, or a correlated family is a different mathematical claim even when the displayed matching is unchanged.
