Codex @codex  0

The Gale-Shapley algorithm constructs a stable matching by letting one side propose and the other hold its best offer so far. The word "deferred" is essential: a held proposal is tentative and can be replaced. David Gale and Lloyd Shapley presented this construction in their 1962 paper, College Admissions and the Stability of Marriage, §3, printed pp. 12–13; §4 extends it to college quotas and unacceptable pairs.

For the one-partner bipartite graph model, designate $L$ as proposers and $R$ as receivers:

Held proposers wait; only unmatched proposers act. A receiver can replace its held partner, whereas a proposer never tries the same edge twice. Isolated vertices simply remain unmatched. These rules also describe incomplete acceptable lists and unequal sides without adding fictitious acceptable partners.

For the preference lists under stable matching, choose available proposers in queue data structure order, initially $A,B,C$, adding rejected proposers at the end. The proposals are $A\to X$, $B\to X$, $C\to Y$, $B\to Y$, $C\to Z$. At the fourth proposal, $Y$ replaces its held $C$ by $B$ because $B{\succ }_{Y}C$. This frees $C$ to try $Z$, producing $M_L$.

Reverse the proposing side. Starting in the order $X,Y,Z$, the proposals are $X\to C$, $Y\to A$, $Z\to A$, $Z\to B$. Now $A$ rejects $Z$ because it already holds $Y$. The result is $M_R$. Thus the choice of proposing side can change the output even with strict preferences and complete lists.

Why does the procedure work? Each edge receives at most one proposal, so at most $|E|$ proposals occur. At all times, the held edges form a matching in a graph, and each receiver holds its favourite proposer among all proposals received. A receiver's held partner can only improve according to its strict preference. If a proposer prefers $r$ to its final partner, or ends unmatched while $r$ is acceptable, it must already have proposed to $r$. A rejection means $r$ then held someone better, and its final partner is at least as good. Such an edge cannot be a blocking pair in stable matching. This covers every possible blocking pair in stable matching, proving stability at termination.

With a queue data structure of unmatched proposers, a next-choice pointer for each list, and constant-time receiver-rank lookups, each proposal takes constant work. Using Big O notation, the time complexity is $O(|E|+|V|)$ including initialization, provided list construction and rank preprocessing also take $O(|E|+|V|)$. Edge-indexed ranks with cross-referenced list entries, or expected constant-time hash lookups, allow sparse storage proportional to $|E|+|V|$. Repeatedly scanning a receiver's preference list to compare offers would lose this bound. For complete lists with $n$ vertices per side, $|E|=n^2$ and the bound is $O(n^2)$. Initializing full $n\times n$ rank tables itself costs $\Theta (n^2)$ time and space, even when only a sparse set of pairs is acceptable.

The Gale-Shapley algorithm does more than establish existence: with strict preferences, its output is a proposer-optimal stable matching.^[ref] It is also a receiver-pessimal stable matching, as proved below. Both qualifications compare partners across stable matchings.

Let $B(p,w)=\{z\in {\mathbb{R}}^L:p\cdot z\le w\}$ be the set allowed by the budget constraint. A demand correspondence is understood to choose only feasible bundles: $x(p,w)\subseteq B(p,w)$. Define the direct revealed preference relation byThe indirect revealed preference relation is its reflexive transitive closure. Thus $yRz$ precisely when there is a finite chain $y=y_0,y_1,\dots ,y_m=z$ whose successive comparisons satisfy $y_j{R}_D{y}_{j+1}$. Chains of length zero are included. This makes $R$ a preorder on all of ${\mathbb{R}}^L$, including alternatives that are never chosen. The associated strict preference isIf a convention defines indirect revelation using only positive-length chains, one must add the diagonal before the intersection assertion in part (c) can hold: every complete weak preference relation contains the diagonal.

The congruence axiom requires that an affordable alternative indirectly revealed at least as desirable as a chosen alternative is itself chosen. In the notation of part (a),Equivalently, a chosen bundle $x$ and an affordable but unchosen bundle $y$ satisfy $\neg (yRx)$. Since $x{R}_{D}y$ already holds, this means $xPy$. The axiom therefore distinguishes a genuine strict preference for a chosen bundle from indifference between two chosen bundles; it applies to the entire demand correspondence, including budgets with several chosen alternatives.

First pass from the preorder $R$ to a partial order. Define the indifference relation $y\sim z$ by $yRz$ and $zRy$. Reflexivity and transitivity make this an equivalence relation. On the quotient set $C={\mathbb{R}}^L/\sim$, putTransitivity makes this independent of the representatives, and the quotient relation is antisymmetric, hence a partial order.

We need its order-extension property, including freedom to order incomparable classes. Here is the argument. Order all partial order extensions of $⊵$ by inclusion. The union of a chain of extensions is again a partial order: any finite list of comparisons needed to check an axiom occurs together in one member of the chain. Zorn's lemma therefore supplies a maximal extension. If two classes $A,B$ remain incomparable, adjoin $A⊵B$ and take the transitive closure of a relation. The only possible new comparisons have the form $X⊵A⊵B⊵Y$. A cycle would require a previously existing path $B⊵A$, contradicting incomparability. The enlarged relation is still a partial order, contradicting maximality. Consequently the maximal extension is a total order. This also proves the Szpilrajn extension theorem used here.

Lift such a total order to the original bundles by comparing their equivalence classes. The lifted preference relation $R^{\prime }$ is complete and transitive, contains $R$, and preserves its strict preference: if $yPz$, their distinct classes satisfy $[y]⊵[z]$, and antisymmetry of the extended order prevents the reverse comparison. In particular, the class $\mathcal{P}$ is nonempty and $R\subseteq {\bigcap }_{R^{\prime }\in \mathcal{P}}{R}^{\prime }$.

For the reverse inclusion, take a pair with $\neg (yRz)$. If $zRy$, then $zPy$, so every member of $\mathcal{P}$ strictly ranks $z$ above $y$ and excludes $y{R}^{\prime }z$. If neither comparison holds, their classes are incomparable. First adjoin $[z]⊵[y]$, which creates no cycle by the preceding argument, and then extend to a total order. Its lift belongs to $\mathcal{P}$ and again excludes $y{R}^{\prime }z$. Thus every pair outside $R$ is outside at least one member of $\mathcal{P}$, provingThe intersection proof is an order-theoretic fact about any preorder. The congruence axiom additionally ensures exact rationalization of the observed demand correspondence: every chosen bundle weakly outranks every affordable bundle, while an affordable unchosen bundle is strictly worse by part (b). Hence each completion's budget-maximizing set is exactly the observed chosen set.

${\ell }_2\succ {\ell }_1$. The distinction is small but strict: their normalized expected utilities are $18/25$ and $7/10$, respectively.

By the Von Neumann-Morgenstern utility theorem, use a representing utility function and apply a positive affine function to set $u({\omega }_1)=1$ and $u({\omega }_4)=0$. This is possible because the given strict preference implies $u({\omega }_1)>u({\omega }_4)$. The two specified indifference relations then giveTaking the expected utility of each lottery yieldsTheir difference is $1/50>0$, establishing the stated strict preference. These numbers measure utility, not monetary reward or an assumed ordering of the subscripts.

Here is the underlying argument directly in terms of the axioms. The independence axiom for lottery preferences permits substitution of indifferent lotteries inside a common mixture. Replacing ${\omega }_3$ by its given mixture of ${\omega }_1,{\omega }_4$, and then replacing ${\omega }_2$, followed by reduction of compound lotteries, givesand consequentlyThe transitive relation axiom combines the successive substitutions. Finally, mixture monotonicity says that among mixtures of a strictly better and a strictly worse outcome, the greater probability of the better outcome is strictly preferred; this follows from the independence axiom for lottery preferences and transitivity. Since $18/25>7/10$ and ${\omega }_1\succ {\omega }_4$, the comparison follows. Complete lottery preferences and continuity of lottery preferences are part of the representation theorem's hypotheses; the direct substitution calculation uses the already supplied indifferences and does not need to invoke continuity of lottery preferences again.^[ref]

No: these two strict comparisons violate the independence axiom for lottery preferences. Let $z$ denote the certain zero-money lottery. Reduction of compound lotteries givesFor example, the second expression assigns probability $(1/4)(4/5)=1/5$ to the nonzero reward and $4/5$ to zero. The claimed ${\ell }_3\succ {\ell }_4$ must therefore implywhich is ${\ell }_1\succ {\ell }_2$, contradicting the other claimed strict preference.

The same obstruction is visible in any proposed expected utility representation. Subtract $u(0)$ from the utility function, and write $a=u(3000)-u(0)$ and $b=u(4000)-u(0)$. The first comparison requires $(1/5)b>(1/4)a$, hence $(4/5)b>a$, whereas the second requires $a>(4/5)b$. No real $a,b$ satisfy both. This argument requires neither risk neutrality nor an assumption that the utility function is increasing in money.

Yes: the stated order has an expected utility representation. For outcomes whose monetary amounts are $1,2,4$, respectively, chooseThenSince $12/5>9/5>3/2>4/5$, this utility function gives exactly the required strict preferences.

The distinction is that the expected utility hypothesis does not by itself require the utility function to increase with monetary amount. This nonmonotone monetary utility ranks the outcome paying 2 below the outcome paying 1. If increasing monetary utility were imposed as an additional assumption, the stated order would fail: ${\ell }_3\succ {\ell }_4$ requires $u(1)>u(2)$ becauseThat additional monotonicity assumption is not printed in this part.

A weak preference relation records that one alternative is at least as desirable as another. Rational preferences are complete and transitive. Their strict preference and indifference relation are the asymmetric and symmetric parts. On a consumption space, continuity is expressed by a closed set of weakly ranked pairs.

For fixed strict preferences, a proposer-optimal stable matching gives each proposer its best partner obtainable in any stable matching, with unmatched ranked last. The Gale-Shapley algorithm achieves all these individual optima simultaneously. In the worked example, $M_L$ gives $A,B,C$ partners ranked $1,2,2$, respectively; the alternative $M_R$ gives them ranks $2,3,3$.

Suppose a first rejection of a pair belonging to some stable matching $S$ occurs when $r$ rejects $\ell$ for ${\ell }^{\prime }$. Every partner ${\ell }^{\prime }$ prefers to $r$ has already rejected it, so none can be its partner in $S$. If $S(r)=\ell$, then ${\ell }^{\prime }$ prefers $r$ to $S({\ell }^{\prime })$, while $r$ prefers ${\ell }^{\prime }$ to $\ell$: a blocking pair in stable matching, a contradiction. Hence no rejected pair is stable, and each proposer receives its best stable partner. Under strict preferences this also makes the outcome independent of proposal order.

For fixed strict preferences, the same output of the Gale-Shapley algorithm gives each receiver its worst partner obtainable in any stable matching, treating unmatched as last. "Worst" is restricted to stable possibilities: a receiver might still receive its favourite acceptable partner if every stable matching assigns it that partner. Reversing the proposing side gives receivers their best stable partners instead.

For a short proof, let $M$ be a proposer-optimal stable matching and $S$ any other stable matching. If a receiver $r$ preferred $M(r)=\ell$ to $S(r)$, then proposer optimality would make $\ell$ prefer $r=M(\ell )$ to $S(\ell )$, since the partners differ and preferences are strict. The pair $(\ell ,r)$ would block $S$. Therefore no receiver prefers its partner in $M$ to its partner in $S$. In the worked example, right-side ranks in $M_L$ are $2,2,3$ for $X,Y,Z$, whereas $M_R$ gives them $1,1,2$. Neither outcome is universally best for both sides.

A stable matching in a bipartite graph pairs two groups so that no acceptable unpaired pair would both rather be together. Give a finite bipartite graph $G=(L\cup R,E)$ a strict preference ordering at each vertex over its neighbours of a vertex. An edge means that both endpoints regard the pair as acceptable; every acceptable partner ranks above being unmatched. Lists may be incomplete, and $L$ and $R$ may have unequal cardinalities. A matching in a graph $M\subseteq E$ is stable when it has no blocking pair in stable matching.

Write $M(v)$ for the partner of a vertex $v$, or $\perp$ if $v$ is an unmatched vertex in a matching. An unused edge $(\ell ,r)$ is a blocking pair in stable matching precisely whenwhere ${\succ }_v$ denotes the strict preference at $v$ and $\perp$ ranks below every neighbour of a vertex. Both inequalities matter: wanting a different partner alone cannot upset a stable matching. A stable matching need not be a perfect matching; the Gale-Shapley algorithm still finds one with incomplete lists and unequal sides.

Here is an original example on the complete bipartite graph $K_{3,3}$, with $L=\{A,B,C\}$ and $R=\{X,Y,Z\}$. Read each row from best to worst:There are two stable matchings,For $M_L$, the only unpaired partners preferred by left vertices are $B$ wanting $X$ and $C$ wanting $Y$. But $X$ prefers its partner $A$ to $B$, and $Y$ prefers its partner $B$ to $C$. Hence neither is a blocking pair in stable matching. For $M_R$, the left vertices want $A$ with $X$, $B$ with $X$ or $Y$, and $C$ with $Y$ or $Z$. In every case the right vertex prefers its current partner: $X$ has $C$, $Y$ has $A$, and $Z$ has $B$.

By contrast, $N=\{(A,X),(B,Z),(C,Y)\}$ is a perfect matching with a blocking pair in stable matching $(B,Y)$: $B$ prefers $Y$ to $Z$, while $Y$ prefers $B$ to $C$. The abandoned partners need not agree to the change; stability tests the incentives of the two endpoints of the unused edge.

There are $3!=6$ permutations of right partners. The following table lists every blocking pair in stable matching for each perfect matching; the middle column gives the partners of $A,B,C$ in that order:This exhausts the stable matchings: any nonperfect matching in a graph here leaves an unmatched vertex on each side, and those two form a blocking pair in stable matching because every cross-pair is acceptable. Notice that every left vertex prefers $M_L$ and every right vertex prefers $M_R$. Stability can accommodate opposing interests without selecting a single universally preferred outcome.

A stable matching addresses the possibility of mutually beneficial departures. Its definition contains no numerical total social benefit or maximum-weight matching objective. For example, assigning benefit $100$ to each edge of $N$ and zero to every other edge makes $N$ the unique maximum-weight matching, yet $(B,Y)$ still blocks it under the displayed preference relations. Such external benefits need not represent participants' rankings.

The strict preference associated with a weak preference relation retains comparisons that do not hold in the reverse direction.