match-stable-pairs

When to Use

• Hospital-resident matching
• Stable marriage problem
• College admissions
• Job candidate matching
• Any two-sided market with preferences
• When you need a "stable" matching (no pair wants to switch)

When NOT to Use

• One-sided assignment (use Hungarian algorithm)
• Weighted matching optimization (different problem)
• When preferences aren't strict orderings

The Pattern

Gale-Shapley Algorithm: Proposers propose in preference order; acceptors tentatively accept best offer so far.

def stable_matching(proposer_prefs, acceptor_prefs):
    """Find stable matching using Gale-Shapley algorithm.

    Returns dict mapping proposers to matched acceptors.
    Proposer-optimal: proposers get best partner possible.
    """
    n = len(proposer_prefs)

    # Track state
    unmatched = set(range(n))      # Unmatched proposers
    matched = {}                    # acceptor -> proposer
    proposals = [list(prefs) for prefs in proposer_prefs]  # Remaining preferences

    while unmatched:
        proposer = unmatched.pop()

        if not proposals[proposer]:
            continue  # Proposer exhausted all options

        acceptor = proposals[proposer].pop(0)  # Best remaining choice

        if acceptor not in matched:
            # Acceptor is free, tentatively accept
            matched[acceptor] = proposer
        elif acceptor_prefs[acceptor].index(proposer) < \
             acceptor_prefs[acceptor].index(matched[acceptor]):
            # Acceptor prefers new proposer
            unmatched.add(matched[acceptor])  # Old match becomes unmatched
            matched[acceptor] = proposer
        else:
            # Acceptor rejects, proposer tries again
            unmatched.add(proposer)

    return {p: a for a, p in matched.items()}

Example (from pytudes StableMatching.ipynb)

def stable_matching(P, A):
    """Stable matching with preference arrays.

    P[i][j] = proposer i's preference for acceptor j (lower = better)
    A[i][j] = acceptor i's preference for proposer j (lower = better)
    """
    n = len(P)
    ids = range(n)

    unmatched = set(ids)
    matched = {}  # acceptor -> proposer

    # Pre-sort: for each proposer, list acceptors by preference
    proposals = [sorted(ids, key=lambda a: P[p][a]) for p in ids]

    while unmatched:
        p = unmatched.pop()
        a = proposals[p].pop()  # Best remaining acceptor

        if a not in matched:
            matched[a] = p
        elif A[a][p] < A[a][matched[a]]:  # a prefers p to current
            unmatched.add(matched[a])
            matched[a] = p
        else:
            unmatched.add(p)  # Rejected, try again

    return {(p, a) for a, p in matched.items()}

Key Principles

1. Proposer advantage: Algorithm is optimal for proposing side
2. Tentative matching: Acceptors can "trade up"
3. Guaranteed stable: No blocking pairs in result
4. O(n^2) time: Each proposer proposes to each acceptor at most once
5. Pre-sort preferences: Makes lookup O(1) during matching