Try
Two teams are forming pairs. In one local group, proposers p and q rank receivers a and b in opposite orders: p prefers a, while q prefers b. The receivers also disagree, but in the opposite direction: a prefers q, while b prefers p. Can both possible complete pairings be stable?
A blocking pair consists of two people who are not currently paired but each prefer the other to their assigned partner. All preferences here are strict and complete, and all opposite-side participants are acceptable. The sides have equal finite size. We study perfect matchings; an imperfect matching would leave someone unmatched on each side, and those two would block.
Predict
Compare the two local outcomes M₀=(p-a,q-b) and M₁=(p-b,q-a). In the first, both proposers get their first choice. In the second, both receivers get their first choice. Predict whether that observation certifies all unmatched pairs, rather than merely making the outcomes seem attractive.
Now imagine three separate groups with these same local preferences. Each participant ranks both local opposite-side people above every outsider. Predict how many stable matchings we can construct by independently choosing an outcome in each group. Then ask a harder question: could additional stable matchings pair people across the groups?
Experiment
List the two unmatched pairs in each local outcome before checking this table. “Rejects” means the named participant prefers its current partner, so that pair cannot block.
| Outcome | Unmatched pair | Why it does not block |
|---|
| M₀: p-a, q-b | p-b | p prefers current a |
|---|
| M₀: p-a, q-b | q-a | q prefers current b |
|---|
| M₁: p-b, q-a | p-a | a prefers current q |
|---|
| M₁: p-b, q-a | q-b | b prefers current p |
|---|
For three groups, write a three-bit string recording the local choices. For example 010 chooses M₀ in the first group, M₁ in the second, and M₀ in the third. List all eight strings. Explain why changing one bit changes an actual partner, not merely a label attached to the same matching.
The outsider rankings are not missing data: they may be completed in any strict order below the two local choices. Our proof will work for every such completion. It must use only the guaranteed rank barrier, rather than silently assigning a convenient outsider order.
Understand
For k groups, there are 2k participants on each side. Group i contains pᵢ,qᵢ and aᵢ,bᵢ. Each participant prefers every opposite-side member of its own group to every outsider. Choose M₀ or M₁ independently in each group and combine the results. This produces a perfect matching because groups have disjoint participants.
An internal unmatched pair cannot block, by the local checks. A cross-group pair cannot block either: both members already have a local partner, preferred to every outsider. Thus each of the 2^k binary strings gives a stable matching. Different strings give different partners in some group, so these are distinct outcomes. At this point we have proved at least 2^k, not yet an exact total.
To prove exactness, consider any stable perfect matching and one group. Let r be the number of its internal matched edges. Those edges use r proposers and r receivers from the group. Consequently 2−r proposers and 2−r receivers from that group have outside partners. If any participant is matched outside, then r is less than 2 and at least one participant on each side has an outside partner.
Choose one of each. They are not paired to each other, since both have outside partners. Each prefers the other, an own-group participant, to its present outsider. They therefore block, contradicting stability. No group can leak participants in a stable matching. This argument counts internal edges, so it works whether the first observed leak was on the proposer or receiver side.
Every stable global matching must therefore be a union of local perfect matchings. Each restriction must be locally stable, since a local blocker would also block globally. There are exactly two local possibilities and both are stable. Combining this exclusion result with the product construction proves exactly 2^k stable matchings for this family.
The result concerns a constructed family, not every preference profile of that size. A profile may have a unique stable outcome. Nor do two proposal algorithms enumerate all stable outcomes: the two sides’ extreme outcomes need not exhaust the independent group choices.
Apply
Extend to 2k+1 participants per side by adding one proposer s and one receiver t who rank one another first. Keep every existing group’s two local options above all outsiders. Any stable matching must include s-t, or that mutual first-choice pair would block. Conversely, adding s-t to any original stable matching creates no new blocker, since neither new participant prefers anyone else. The stable count remains 2^k. For k=0 this is a single forced pair; the even-size zero-group case has one empty matching, consistent with 2⁰=1.
Test the barrier by changing two rankings in a two-group example: put a₂ above p₁’s own-group receivers, and put p₁ above a₂’s own-group proposers. The combined M₀ outcomes now contain the cross-group blocker p₁-a₂. The local pairings have not changed, but the global proof fails exactly where it excluded outsider incentives.
Changed counting case
Suppose two groups have two stable local outcomes and a third has exactly one, with all barriers intact. There are 2·2·1=4 global stable outcomes. The same no-leak proof gives exactness; the local counts need not all equal two. To justify the answer, verify the third group’s uniqueness separately rather than assuming every two-by-two profile has two stable outcomes.
Continue
In the practice, keep three arguments separate: stability of each local choice, stability and distinctness of their combinations, and exclusion of every other outcome. The first two give a lower bound. The balanced-group blocking argument upgrades it to an exact count. State the preference barriers and complete-list assumptions whenever reusing this reasoning; a changed population or a changed acceptability rule may invalidate the counting step.
