Two applicants, A and B, must be paired with two hosts, X and Y. Each host can take one applicant and each applicant can take one host. This is a synthetic allocation problem: the preferences are supplied assumptions, not measured happiness. Read an earlier entry as strictly preferred to every later entry.
Participant
First choice
Second choice
A
X
Y
B
X
Y
X
B
A
Y
A
B
A proposed outcome pairs A with X and B with Y. Everyone has a partner and no capacity is exceeded. Yet B prefers X to Y, and X prefers B to A. They would both prefer to pair with one another. This is a blocking pair. The issue is not that B alone is disappointed: X’s preference matters too.
Before reading on, list the other unpaired possibility, A with Y. Does it block? It does not, because A prefers its current partner X. An unhappy participant does not automatically make a matching unstable, and a happy participant can prevent a particular deviation even when the other person wants it.
Predict
Predict what happens if we switch to A with Y and B with X. A now wants X, but X prefers its assigned B. B has its first choice and does not want Y. Both unpaired possibilities therefore fail the two-sided test. The new matching is stable: it has no blocking pair.
Both outcomes contain two pairs, which is the maximum possible. Maximum cardinality asks how many participants can be matched; stability asks whether an unassigned cross-side pair mutually prefers switching. A maximum matching need not be stable. Hall’s theorem and cardinality certificates answer valuable questions, but they do not encode these preference comparisons.
Predict which evidence is sufficient for each claim. One checked blocking pair refutes stability. To certify stability directly, you must account for every unpaired cross-side pair, or give a general argument covering them all. Checking only one satisfied participant is not enough.
Experiment
The diagram shows the first, unstable outcome. Solid horizontal lines are assigned pairs. The dashed diagonal is a proposed deviation, not an additional simultaneous assignment.
Every participant is paired, but B and X mutually prefer the dashed alternative. Preferences come from the table; line positions do not represent preference strength.
Make an audit table with one row for each unpaired pair. Use two separate columns: “Does the applicant prefer switching?” and “Does the host prefer switching?” Mark a block only when both entries are yes. For the initial matching, A–Y has no/yes and B–X has yes/yes. For the repaired matching, A–X has yes/no and B–Y has no/no.
Now change only X’s ranking to A above B. Re-audit both outcomes rather than reusing the old conclusion. The original A–X, B–Y is now stable, while the switched outcome is blocked by A–X. A small change to a participant’s stated preferences can change the certificate even when the set of feasible pairs stays the same.
Understand
Our default model has two disjoint finite sides of equal size n. Every participant ranks all n participants on the other side, with no ties. These are complete strict preference lists. Every possible cross-side partner is preferred to remaining unmatched. A matching is a collection of pairs with no participant repeated; it is perfect when everyone is paired.
For a perfect matching M, an unpaired applicant–host pair (a,h) blocks M exactly when a prefers h to its M-partner and h prefers a to its M-partner. Stability means no such pair exists. This is an individual two-party deviation criterion, not a theorem about fairness, happiness totals or resistance to every possible coalition.
The partial-matching version compares an acceptable partner with being unmatched as well. Under the default complete model, a stable matching must be perfect. If someone on the first side were unmatched, equal sizes would leave someone unmatched on the other side too. Both prefer pairing with each other to remaining unmatched, creating a block. Notice the roles of equal sizes and complete acceptability. Neither can simply disappear from this argument.
Completeness and strictness also describe what is known, not what can be guessed. Lists for only one side cannot determine stability: the unreported participants might welcome or refuse a deviation. A certificate must use both sides’ preferences.
A direct finite audit checks at most n² cross-side pairs, excluding assigned pairs from the deviation test. This bound refers to checking a supplied matching, not yet finding one. A later lesson gives an algorithm that constructs a stable outcome under our hypotheses.
Apply
Construct your own two-per-side profile with two stable outcomes. One method is to let the two applicants prefer different hosts, while each host prefers the other applicant. Pair applicants with their first choices for one outcome; reverse both assignments for the other. The first outcome is stable because no applicant wants to switch; the second because no host wants to switch. Explain why this shows nonuniqueness is possible, without claiming every profile has two stable outcomes.
Change the model more substantially: suppose a host finds some applicants unacceptable. A pair involving an unacceptable participant is forbidden, so two unmatched participants need not form a block. With A and B accepting only X, and Y accepting nobody, no perfect acceptable matching exists. Match X with its preferred acceptable applicant and leave the others unmatched: that outcome can be stable despite not being perfect.
Ties require another decision. “Weak stability” commonly forbids a pair where both strictly prefer switching; “strong stability” also forbids a pair where neither would be worse off and at least one would be strictly better off. These definitions can disagree on the same matching. Specify the definition rather than silently applying the strict-list theorem to tied data. The written tasks supply complete small examples to analyze both notions.
Continue
Bring a preference table and a checked blocking certificate, not just a claim that everyone has been paired. In the next lesson, provisional holds and permanent rejection history will construct an outcome whose stability has a general proof.
For the different cardinality problem, revisit Hall’s theorem and bipartite matchings. Keep its neighbor-set feasibility criterion separate from the preference conditions developed here. You do not need to complete that whole course to follow the next algorithm.
Apply · explain · revise
Practice and reasoning
Drafts save locally as you type. Reveal worked solutions when useful; the site remembers that exposure. Automatic matches check the requested answer, while written arguments require review against the rubric.
Proposers rank D:U>V>W, E:V>U>W, F:U>W>V. Receivers rank U:E>D>F, V:D>E>F, W:F>E>D. For matching D-W,E-V,F-U, find every blocking pair. Then verify that D-U,E-V,F-W is stable. Explain why maximum cardinality alone distinguishes neither outcome.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Two proposers rank A:Y>X and B:X>Y. The proposed matching is A-X,B-Y. Only these proposer lists are known. Show that the missing receiver preferences prevent deciding stability by giving one complete receiver profile making it stable and another making it unstable.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Extend the blocking definition to a partial matching by treating every partner as preferable to being unmatched. Prove that with equal finite sides and complete strict lists, every stable matching is perfect. Does that prove every perfect matching is stable? Give a two-per-side counterexample if not.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Let A:X>Y, B:Y>X, X:B>A, Y:A>B. List all perfect matchings and prove which are stable. Explain why this disproves uniqueness without implying that every preference profile has multiple stable outcomes.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
There are two participants per side. A and B list only X as acceptable; X ranks A above B; Y lists nobody. Unlisted pairs are forbidden and every acceptable partner is preferred to being unmatched. Find a stable matching, prove no perfect acceptable matching exists, and identify the failed hypothesis of the complete-list theorem.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Allow ties: A ranks X and Y equally; B ranks X above Y; X ranks A above B; Y ranks A above B. A weak blocking pair requires both participants to strictly prefer the new partner. A strong blocking pair requires both to weakly prefer it and at least one strictly to prefer it. Analyze both perfect matchings under these definitions.
Structure your argument and preserve revisions
These optional planning fields save locally. Recording your response saves an immutable copy of the argument and these fields. Older records may contain only first/latest responses; missing intermediate revisions are not reconstructed.
Each field allows 2,000 characters. Keep a specific claim, state where it applies, cite the facts you use, and explain what still needs checking. Blank fields are allowed and are not evidence of mastery.
Reflect and continue
Before marking this lesson complete, explain one key idea without the worked solution and identify a condition that matters. Marking complete records participation, not independent mastery.
