Match Stable Pairs

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)  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

Source & license

This open-source skill is cataloged on AgentStack and links to its original source — we do not rehost the code.

• Author: jimmc414
• Source: jimmc414/claude-code-plugin-marketplace
• License: MIT

Install and usage instructions live in the source repository linked above.