Allocations That Endure Without Universal Contentment: Gale-Shapley Stable Matching and Institutional Design

1. The Unseen Fracture Beyond the Acceptance Letter

When an applicant is rejected by their top choice university and accepted by their second choice, the admissions process appears complete from the outside. Formal admission documents are issued, and institutional procedures are concluded.

Yet looking beyond the boundaries of the mechanism reveals potential hidden fault lines. Among applicants assigned elsewhere, someone may prefer this university over their assigned placement, and the university may secretly evaluate that rejected applicant higher than the student it currently holds. If so, both parties have every reason to abandon the official assignment and strike an informal side agreement.

This is not merely a tale of personal dissatisfaction. It means an escape route exists where both participants, by deviating together, achieve an outcome strictly superior to their official assignment. Any institution that leaves such fissures unaddressed will eventually disintegrate from within through voluntary defections.

In two-sided matching markets such as college admissions, employment, or marriage where mutual consent is required, an ideal allocation granting everyone their first choice is mathematically impossible. On what foundation, then, must institutions be erected when universal contentment cannot be attained?

2. Conflicting Desires: The Preference Paradox of Minwoo and Jisu

To examine this dynamic intuitively, imagine a simplified admissions market with two colleges (College A, College B) each having a quota of exactly one, and two applicants (Minwoo, Jisu).

Their private preference orderings diverge sharply as follows:

Minwoo desires College A above all, while Jisu desires College B. The colleges hold precisely the opposite evaluation: College A prioritizes Jisu, and College B prioritizes Minwoo.

With each institution admitting only one candidate, both applicants cannot receive their first choice simultaneously. Someone must inevitably be relegated to their second choice. By what criteria should the system determine their destiny?

확대

3. The Force That Destabilizes from Within: The Blocking Pair

In their seminal 1962 paper, "College Admissions and the Stability of Marriage," mathematicians David Gale and Lloyd Shapley addressed this dilemma directly. They did not ask how to maximize universal happiness. Instead, they asked a pragmatically vital question: Does there always exist an allocation that cannot be broken apart by the private choices of its participants?

The primary threat to institutional longevity is not individual discontent itself, but the potential for profitable collusion. Matching theory formalizes this threat as a blocking pair.

flowchart LR
    subgraph Official["Official Matching Outcome"]
        S["Student: Assigned to 2nd Choice"]
        C["College: Holds 2nd Choice Candidate"]
    end

    subgraph BlockingPair["Blocking Pair: Mutual Incentive to Defect"]
        S <==>|"Incentive to break official assignment\n(Both strictly prefer each other over current match)"| C
    end

    style BlockingPair fill:#fff1f0,stroke:#cf1322,stroke-width:2px
    style Official fill:#f6ffed,stroke:#52c41a,stroke-width:1px

If a student strictly prefers College X over their assigned college, and College X simultaneously evaluates that student higher than one of its current admittees, they form a blocking pair. Together, they hold an unambiguous incentive to bypass the central clearinghouse and form an independent union.

Conversely, a stable matching is defined as an allocation in which not a single blocking pair exists across the entire market. Individuals may remain dissatisfied with second-choice outcomes. Yet as long as no unassigned partner exists with whom they could mutually benefit by defecting, the allocation endures without requiring physical external coercion.

4. The Deferred Acceptance Algorithm: The Wisdom of Tentative Holding

The mechanism that systematically discovers this stable state is the Deferred Acceptance (DA) algorithm. The sequential application process can be visualized as follows:

flowchart TD
    Start["Step 1: Rejected applicants apply\nto their next preferred college"] --> CollegeReview["Step 2: Colleges compare new applicants\nwith currently held candidates"]
    CollegeReview --> HoldDecision{"Retain top candidates up to quota\non a 'tentative hold'"}
    HoldDecision --> RejectAction["Issue formal rejections to\napplicants exceeding quota"]
    RejectAction --> CheckUnmatched{"Do any rejected applicants remain\nwith viable alternatives?"}
    CheckUnmatched -- "Yes" --> Start
    CheckUnmatched -- "No" --> FinalMatch["Step 3: Convert tentative holds\ninto permanent admissions (Conclude)"]

    style HoldDecision fill:#e6f7ff,stroke:#1890ff,stroke-width:2px
    style FinalMatch fill:#f6ffed,stroke:#52c41a,stroke-width:2px

The core insight resides in the concept of deferral. When a college receives a desirable applicant, it does not grant immediate binding acceptance. It merely holds them tentatively, keeping open the possibility of admitting a superior candidate later. The applicant, upon rejection, advances to their next preferred alternative.

The quality of candidates tentatively retained by colleges monotonically improves or remains constant throughout the iterations, and an applicant once rejected is never revisited. Consequently, when the algorithm terminates, any student who failed to enter a preferred college was definitively rejected in favor of candidates that the institution preferred even more. By construction, zero blocking pairs remain in the final assignment.

확대

5. Asymmetric Optimality: Who Holds the Power to Propose?

Here, however, institutional designers encounter a profound revelation: stable allocations are rarely unique.

Applying the algorithm to Minwoo, Jisu, College A, and College B demonstrates this striking divergence:

Scenario 1: Applicant-Proposing DA. Minwoo applies to his top choice (College A), and Jisu applies to her top choice (College B). Each college receives exactly one applicant and places them on tentative hold. With no rejections, the procedure terminates immediately in Step 1. Minwoo is assigned to College A, and Jisu to College B. Both applicants attain their absolute first choice. The colleges accept their second choices, but because neither student has any desire to transfer, collusion is impossible. The outcome is completely stable.

Scenario 2: College-Proposing DA. College A makes an offer to its top choice (Jisu), while College B offers to Minwoo. Both applicants tentatively accept their respective offers. With no institutions rejected, the procedure terminates instantly. Minwoo ends up at College B, and Jisu at College A. Both colleges secure their premier candidates, while both students are relegated to their second choices. Because neither college wishes to recruit elsewhere, no blocking pair can form. This outcome is also completely stable.

Both outcomes are mathematically unassailable. Under either regime, the threat of subversive side contracts is entirely eliminated.

Yet depending on who initiates the proposal, one side reaps maximum advantage while the other bears the cost. Applicant-proposing DA guarantees the applicant-optimal stable match, which is simultaneously the least favorable stable outcome for the institutions. College-proposing DA produces the exact converse.

Designing an algorithm is never a purely technical computation. The moment an architect decides who proposes first, the mechanism has already made a normative declaration about whose welfare takes priority.

6. When Honesty Incurs No Penalty: Eliminating Strategic Manipulation

Rules do more than allocate resources; they reshape how participants articulate truth.

In conventional admissions or allocation mechanisms, applicants frequently engage in anxious gaming. Listing a dream institution as first choice risks catastrophic failure: if rejected, secondary institutions may already be filled, leaving the applicant completely unplaced. Consequently, participants suppress their true aspirations and strategically report safer compromises.

Those with superior information exploit this friction, while sincere participants who trust the system suffer structural penalties.

The genius of applicant-proposing Deferred Acceptance lies in strategy-proofness: truth-telling is a weakly dominant strategy. An applicant gains no advantage by falsifying their true ranking, because being rejected by an ambitious first choice does not compromise their standing against other contenders at their second choice. Strategic anxiety is rendered obsolete.

The 2005 reform of the Boston Public Schools assignment system demonstrated this transition empirically. The prior Immediate Acceptance mechanism penalized families who dared to rank competitive schools first without certainty, disproportionately harming vulnerable households. By adopting applicant-proposing Deferred Acceptance, the school committee restored a framework where parents could express their genuine desires without fear of tactical ruin.

7. Institutional Legitimacy: Is Stability Sufficient for Justice?

Does an enduring, stable allocation equate to a just and equitable society? We must maintain vigilance before this conflation. Stability and fairness belong to fundamentally distinct categories.

Suppose an institution evaluates candidates through structurally biased or discriminatory criteria. The Gale-Shapley algorithm will process those flawed priorities with mathematical precision, outputting an unshakeable stable match free of blocking pairs.

The absence of private defection does not certify institutional justice. Were opportunities to participate distributed equitably? Did institutional evaluation criteria reflect genuine merit? Were historical disadvantages accounted for? These questions lie outside the mathematical definition of stability.

Stability merely guarantees the mechanical absence of bilateral collapse; it cannot substitute for the moral judgment required to ensure that rules are worthy of survival.

To design an institution is not to construct a utopian fantasy where every desire is satisfied. It is to erect a reliable bulwark against distrust, ensuring that participants are not driven to subvert the collective compact through clandestine agreements.

Once mathematics provides the blueprint for an allocation that will not break, the ultimate inquiry returns to human conscience: Through this resilient architecture, whose rights and dignity have we chosen to protect?