Stable Matching (Gale–Shapley)

Every problem so far in this module optimized a number — the most jobs, the fewest machines, the cheapest tree. Stable matching optimizes a relationship instead. Given two groups, each member of one ranking the members of the other, we want to pair them up so that the pairing holds: no two people, looking at their assigned partners, would both rather abandon them for each other. A pairing with such a defecting couple is unstable, and the couple is the proof of its instability. Gale and Shapley proved that a stable pairing always exists and that a simple greedy procedure — everyone proposes in order of preference, and each recipient keeps only the best proposal seen so far — always finds one. The procedure is greedy in spirit (each proposer tries its top remaining choice; each receiver locally improves), and like the rest of the module its correctness rests on an exchange-style argument. It is also deployed at national scale: the medical residency match and many school-assignment systems are this algorithm.

The stable marriage problem

Fix two disjoint sets of equal size $n$ , traditionally called the proposers and the receivers (the older literature says men and women; we keep the neutral roles). Each proposer ranks all $n$ receivers in a strict preference list, and each receiver ranks all $n$ proposers. A matching $M$ is a one-to-one pairing; it is perfect when everyone is matched.

The definition forbids exactly this instability: two people who each outrank the other's partner and would both defect. The algorithm must leave no such pair.

A blocking pair.

p

prefers

r

over its partner

M (p)

and

r

prefers

p

over its partner

M (r)

, so

(p, r)

would both defect — the matching

M

(gray) is unstable.

Here $p$ is matched to $r^{'}$ but prefers $r$ , and $r$ is matched to $p^{'}$ but prefers $p$ ; the dashed pair $(p, r)$ blocks. Stability is a weak requirement in one sense — it asks nothing about social welfare or total happiness — and a strong one in another: a single blocking pair condemns the whole matching. It is not obvious a stable matching always exists; for the closely related stable roommates problem (one set, everyone ranks everyone) it sometimes does not. The two-sided structure is what guarantees existence.

blocking_pair.pypython

from collections.abc import Hashable, Mapping, Sequence
from typing import Optional, TypeVar

Proposer = TypeVar("Proposer", bound=Hashable)
Receiver = TypeVar("Receiver", bound=Hashable)
Owner = TypeVar("Owner", bound=Hashable)
Candidate = TypeVar("Candidate", bound=Hashable)

def _rank_tables(
  preferences: Mapping[Owner, Sequence[Candidate]],
) -> dict[Owner, dict[Candidate, int]]:
  """
    Turn each preference list into a candidate -> position lookup so that\n
    "who do I prefer?" is a constant-time comparison of two positions.\n
  """
  return {
    owner: {candidate: position for position, candidate in enumerate(ranking)}
    for owner, ranking in preferences.items()
  }

def find_blocking_pair(
  matching: Mapping[Proposer, Receiver],
  proposer_preferences: Mapping[Proposer, Sequence[Receiver]],
  receiver_preferences: Mapping[Receiver, Sequence[Proposer]],
) -> Optional[tuple[Proposer, Receiver]]:
  """
    A blocking pair of `matching`, or None if the matching is stable.\n
    Returns the first (proposer, receiver) found in which the proposer\n
    prefers the receiver to its partner and the receiver prefers that\n
    proposer to its own partner.\n
  """
  receiver_rank = _rank_tables(receiver_preferences)

  # invert the matching so each receiver knows its assigned proposer.
  partner_of_receiver: dict[Receiver, Proposer] = {
    receiver: proposer for proposer, receiver in matching.items()
  }

  for proposer, current_receiver in matching.items():
    for candidate_receiver in proposer_preferences[proposer]:
      if candidate_receiver == current_receiver:
        # proposers descend their lists; nothing below the partner can block.
        break
      candidate_partner: Proposer = partner_of_receiver[candidate_receiver]
      if (
        receiver_rank[candidate_receiver][proposer]
        < receiver_rank[candidate_receiver][candidate_partner]
      ):
        # both prefer each other to their partners: a blocking pair.
        return (proposer, candidate_receiver)
  return None

def is_stable(
  matching: Mapping[Proposer, Receiver],
  proposer_preferences: Mapping[Proposer, Sequence[Receiver]],
  receiver_preferences: Mapping[Receiver, Sequence[Proposer]],
) -> bool:
  """
    Whether `matching` is a perfect matching with no blocking pair.\n
    A matching that leaves anyone unpaired, or pairs anyone twice, is not\n
    perfect and so not stable.\n
  """
  # perfect: everyone paired, no receiver used twice, all receivers covered.
  receivers_used: list[Receiver] = list(matching.values())
  is_perfect: bool = (
    len(matching) == len(proposer_preferences) == len(receiver_preferences)
    and len(set(receivers_used)) == len(receivers_used)
    and set(receivers_used) == set(receiver_preferences)
  )
  if not is_perfect:
    return False

  # a perfect matching is stable exactly when no pair blocks it.
  return (
    find_blocking_pair(
      matching, proposer_preferences, receiver_preferences
    )
    is None
  )

The Gale–Shapley algorithm

The algorithm is deferred acceptance. Proposers propose, but receivers never finally commit: a receiver holds onto its best proposal so far and stays free to trade up. Time runs in rounds; in each round some free proposer proposes to the most-preferred receiver it has not yet proposed to. That receiver, comparing the new offer to whatever it currently holds, keeps the better of the two and rejects the other. A rejected proposer becomes free again and will later propose further down its list. The deferral — receivers tentatively hold rather than accept — is the entire idea; it is what lets an early, hasty pairing dissolve when a better proposer arrives.

Algorithm 1:

\textsc{Gale-Shapley}(P, R)

— a stable matching from preference lists

1
initialize every proposer and receiver as free
2
while some proposer $p$ is free and has not proposed to every receiver do
3
$r \gets$ first receiver on $p$ 's list to whom $p$ has not yet proposed
4
if $r$ is free then
5
match $p$ and $r$
tentative: $r$ may still trade up
6
else if $r$ prefers $p$ to its current partner $p'$ then
7
free $p'$
$r$ trades up to $p$
8
match $p$ and $r$
9
else
10
$r$ rejects $p$
$p$ stays free, proposes lower next time
11
return the set of matched pairs

Two invariants make the whole proof go, and both are visible in the loop. First, proposers descend their lists: a proposer only ever proposes to receivers strictly worse (for it) than ones it has already been rejected by, so over its life a proposer's offers move monotonically down. Second, receivers improve: once a receiver is matched it stays matched forever, and the partner it holds only ever gets better (for it), since it trades up and never down.

Deferred acceptance, the trade-up step. Receiver

r

tentatively holds

p^{'}

(left). A better proposer

p

arrives; since

r

prefers

p

, it drops

p^{'}

(red, now free again) and holds

p

(green). A held partner only ever improves for

r

We run a small instance to see deferred acceptance trade up.

An instance. Proposers

p_{1}, p_{2}, p_{3}

and receivers

r_{1}, r_{2}, r_{3}

with the preference lists shown (left = top choice). Deferred acceptance produces the stable matching

p_{1} - r_{2}, p_{2} - r_{1}, p_{3} - r_{3}

(blue).

A trace on this instance, one proposal per row:

Proposal	$p$ proposes to	$r$ currently holds	$r$ 's decision	Held pairs after
1	$p_{1} \to r_{2}$	(free)	accept	$p_{1} r_{2}$
2	$p_{2} \to r_{1}$	(free)	accept	$p_{1} r_{2}, p_{2} r_{1}$
3	$p_{3} \to r_{2}$	$p_{1}$	reject ( $r_{2}$ prefers $p_{1}$ )	$p_{1} r_{2}, p_{2} r_{1}$
4	$p_{3} \to r_{3}$	(free)	accept	$p_{1} r_{2}, p_{2} r_{1}, p_{3} r_{3}$

$p_{3}$ leads with its top choice $r_{2}$ , but $r_{2}$ already holds $p_{1}$ and ranks $p_{1}$ above $p_{3}$ , so $p_{3}$ is turned away and descends to $r_{3}$ , which is free. Everyone is now matched; no proposer was displaced, so the algorithm stops with $p_{1} - r_{2}$ , $p_{2} - r_{1}$ , $p_{3} - r_{3}$ . We will verify shortly that it is stable.

The proposal trace, one column per step. Solid blue edges are tentative holds; the red dashed edge in step~~3 is $p_{3}$ proposing to $r_{2}$ and being rejected (it holds $p_{1}$ ). Step~~4 settles

p_{3}

with

r_{3}

; the final holds are stable (green).

gale_shapley.pypython

from collections import deque
from collections.abc import Hashable, Mapping, Sequence
from typing import Generic, Optional, TypeVar

Proposer = TypeVar("Proposer", bound=Hashable)
Receiver = TypeVar("Receiver", bound=Hashable)
Candidate = TypeVar("Candidate", bound=Hashable)

class Participant(Generic[Candidate]):
  """
    One side of a stable-matching instance: an identity plus a preference\n
    ranking over the other side's members. `rank_of` answers "where does\n
    this candidate sit on my list?" in constant time, the precomputed\n
    table that makes each step O(1).\n
  """

  def __init__(
    self, identity: Hashable, preferences: Sequence[Candidate]
  ) -> None:
    self.identity: Hashable = identity
    self.preferences: list[Candidate] = list(preferences)
    self._rank: dict[Candidate, int] = {
      candidate: position for position, candidate in enumerate(self.preferences)
    }

  def rank_of(self, candidate: Candidate) -> int:
    """
      The position of `candidate` on this participant's list — lower is\n
      better, position 0 being the top choice.\n
    """
    return self._rank[candidate]

  def prefers(self, candidate: Candidate, over: Candidate) -> bool:
    """
      Whether `candidate` outranks `over` on this participant's list.\n
    """
    return self._rank[candidate] < self._rank[over]

  def __repr__(self) -> str:
    return f"Participant({self.identity!r})"

class GaleShapley(Generic[Proposer, Receiver]):
  """
    A stable-marriage instance: two equal-size sides, each member ranking\n
    every member of the other. `solve` runs deferred acceptance and returns\n
    the proposer-optimal stable matching.\n
  """

  def __init__(
    self,
    proposer_preferences: Mapping[Proposer, Sequence[Receiver]],
    receiver_preferences: Mapping[Receiver, Sequence[Proposer]],
  ) -> None:
    """
      Build from two preference maps. Each proposer must rank exactly the\n
      receivers and each receiver exactly the proposers; the two sides must\n
      have equal size.\n
    """
    self.proposers: dict[Proposer, Participant[Receiver]] = {
      identity: Participant(identity, preferences)
      for identity, preferences in proposer_preferences.items()
    }
    self.receivers: dict[Receiver, Participant[Proposer]] = {
      identity: Participant(identity, preferences)
      for identity, preferences in receiver_preferences.items()
    }
    if len(self.proposers) != len(self.receivers):
      raise ValueError("the two sides must have equal size")

  def solve(self) -> dict[Proposer, Receiver]:
    """
      The proposer-optimal stable matching, as a proposer -> receiver map.\n
      Free proposers propose down their lists; receivers hold their best\n
      offer and trade up. Runs in O(n^2).\n
    """
    # every proposer starts free, with a pointer at the top of its list.
    free_proposers: deque[Proposer] = deque(self.proposers)
    next_choice: dict[Proposer, int] = {
      proposer: 0 for proposer in self.proposers
    }

    # the proposer a receiver currently holds, if any.
    held_by: dict[Receiver, Optional[Proposer]] = {
      receiver: None for receiver in self.receivers
    }

    while free_proposers:
      proposer_id = free_proposers.popleft()
      proposer = self.proposers[proposer_id]

      # the next receiver this proposer has not yet proposed to.
      target_id: Receiver = proposer.preferences[next_choice[proposer_id]]
      next_choice[proposer_id] += 1
      receiver = self.receivers[target_id]
      incumbent: Optional[Proposer] = held_by[target_id]

      if incumbent is None:
        # free receiver: tentatively held.
        held_by[target_id] = proposer_id
      elif receiver.prefers(proposer_id, incumbent):
        # receiver trades up; the displaced proposer becomes free again.
        held_by[target_id] = proposer_id
        free_proposers.append(incumbent)
      else:
        # rejected: this proposer tries lower next round.
        free_proposers.append(proposer_id)

    return {
      held: receiver_id
      for receiver_id, held in held_by.items()
      if held is not None
    }

Termination and the $O (n^{2})$ bound

The bound is tight up to the leading constant: an adversarial instance can force about $n^{2} - n + 1$ proposals. With the right data structures every step is $O (1)$ — each proposer keeps a pointer to its next un-proposed receiver, and each receiver answers do I prefer $p$ to my current partner? by a precomputed rank table indexed in constant time — so the whole algorithm runs in $O (n^{2})$ , linear in the size of the input, since the preference lists themselves already have $2 n^{2}$ entries.

Perfection: everyone gets matched

Termination alone could leave some proposer free. It does not.

The key is invariant (ii): a receiver, once approached, never goes back to being free. A free-at-the-end proposer must have approached everyone, which would have matched everyone, leaving no room for it to be unmatched — a contradiction.

Stability: no blocking pair survives

The central theorem. Termination and perfection only say we have a perfect matching; this says the one we have holds together.

Proof. Take any pair $(p, r)$ not matched in $M$ ; we show it does not block. There are two cases by whether $p$ ever proposed to $r$ .

Case 1: $p$ never proposed to $r$ . Proposers descend their lists (invariant (i)), and $p$ is matched in $M$ to whichever receiver it last proposed to. Since $p$ stopped before reaching $r$ , the receiver $M (p)$ sits at or above $r$ on $p$ 's list, i.e. $p$ prefers $M (p)$ to $r$ (or they coincide, excluded). So $p$ is content; $(p, r)$ does not block.

Case 2: $p$ did propose to $r$ at some point. Since $p$ and $r$ are not matched in $M$ , $r$ must have rejected $p$ — either turning $p$ down on arrival for a partner it preferred, or later trading up away from $p$ . Either way, by invariant (ii) the partner $r$ holds only improves over time, so $r$ 's final partner $M (r)$ is at least as good (for $r$ ) as the proposer it preferred over $p$ , hence strictly better than $p$ . So $r$ prefers $M (r)$ to $p$ ; $(p, r)$ does not block.

In both cases at least one of $p, r$ prefers its assigned partner, so $(p, r)$ is not a blocking pair. As $(p, r)$ was an arbitrary unmatched pair, $M$ has none and is stable. $□$

The two cases are exhaustive and complementary, and they split exactly along which side is satisfied. If $p$ never asked $r$ , then $p$ is already with someone it likes at least as much as $r$ . If $p$ did ask and is not with $r$ , then $r$ upgraded to someone it likes more than $p$ . The figure below traces Case 2, the subtler one: a rejection only ever moves a receiver up its list, so once it has rejected $p$ it can never again prefer $p$ to what it holds.

Stability, Case 2. After

r

rejects

p

for

p^{'}

(or trades up to

p^{'}

r

's held partner only improves, so

r

ends with

M (r)

that it prefers to

p

. The pair

(p, r)

cannot block.

Together the three theorems show: deferred acceptance always terminates, always returns a perfect matching, and that matching is always stable. A stable matching exists for every instance, constructively.

The asymmetry: proposer-optimal, receiver-pessimal

An instance can have many stable matchings, and the algorithm always lands on a very specific one — the best possible for the proposing side, simultaneously the worst possible for the receiving side. To state it, call a receiver $r$ a valid partner of a proposer $p$ if some stable matching pairs them.

valid_partners.pypython

from collections.abc import Hashable, Mapping, Sequence
from itertools import permutations
from typing import TypeVar

from blocking_pair import is_stable

Proposer = TypeVar("Proposer", bound=Hashable)
Receiver = TypeVar("Receiver", bound=Hashable)

def all_stable_matchings(
  proposer_preferences: Mapping[Proposer, Sequence[Receiver]],
  receiver_preferences: Mapping[Receiver, Sequence[Proposer]],
) -> list[dict[Proposer, Receiver]]:
  """
    Every stable matching of the instance, by exhaustive search.\n
    Tries all n! ways to assign receivers to proposers and keeps the stable\n
    ones — exponential, so for small instances and for checking the\n
    optimality theorems, not for production solving.\n
  """
  proposers: list[Proposer] = list(proposer_preferences)
  receivers: list[Receiver] = list(receiver_preferences)
  stable: list[dict[Proposer, Receiver]] = []

  # keep each permutation that pairs everyone without a blocking pair.
  for assignment in permutations(receivers):
    matching: dict[Proposer, Receiver] = dict(zip(proposers, assignment))
    if is_stable(matching, proposer_preferences, receiver_preferences):
      stable.append(matching)

  return stable

def valid_partners(
  proposer_preferences: Mapping[Proposer, Sequence[Receiver]],
  receiver_preferences: Mapping[Receiver, Sequence[Proposer]],
) -> dict[Proposer, set[Receiver]]:
  """
    For each proposer, the set of receivers it is paired with in some stable\n
    matching — its valid partners.\n
  """
  partners: dict[Proposer, set[Receiver]] = {
    proposer: set() for proposer in proposer_preferences
  }

  # union the partner each proposer takes across every stable matching.
  for matching in all_stable_matchings(
    proposer_preferences, receiver_preferences
  ):
    for proposer, receiver in matching.items():
      partners[proposer].add(receiver)

  return partners

def best_valid_partner(
  proposer: Proposer,
  proposer_preferences: Mapping[Proposer, Sequence[Receiver]],
  receiver_preferences: Mapping[Receiver, Sequence[Proposer]],
) -> Receiver:
  """
    The highest receiver on `proposer`'s list among its valid partners —\n
    the partner deferred acceptance is proven to deliver.\n
  """
  partners: set[Receiver] = valid_partners(
    proposer_preferences, receiver_preferences
  )[proposer]
  ranking: Sequence[Receiver] = proposer_preferences[proposer]

  # walk the list top-down; the first valid partner is the best one.
  for receiver in ranking:
    if receiver in partners:
      return receiver

  raise ValueError(f"{proposer!r} has no valid partner")

Valid-partner ladders. Each proposer's preference list runs top to bottom; the boxed receivers are its valid partners (paired in some stable matching). Deferred acceptance hands each proposer the topmost of its boxed entries (green) — its best valid partner.

Proof. Suppose not. Among all runs, consider the first moment some proposer is rejected by a valid partner; say $r$ rejects $p$ , and $r$ is a valid partner of $p$ . The rejection means $r$ holds (or trades up to) some $p^{'}$ it prefers to $p$ . Because this is the first rejection by a valid partner, $p^{'}$ has not yet been rejected by any valid partner of its own, so $r$ is at least as good for $p^{'}$ as $p^{'}$ 's best valid partner — in particular $p^{'}$ prefers $r$ to any partner it could have in a stable matching where it is not with $r$ .

Now let $M^{'}$ be a stable matching pairing $p$ with $r$ (one exists, as $r$ is valid for $p$ ). In $M^{'}$ , $p^{'}$ is matched to someone other than $r$ , and $p^{'}$ prefers $r$ to that partner (previous paragraph), while $r$ prefers $p^{'}$ to $p$ (the rejection). Then $(p^{'}, r)$ is a blocking pair in $M^{'}$ , contradicting that $M^{'}$ is stable. So no proposer is ever rejected by a valid partner, and each ends with the best valid partner it could reach. $□$

The mirror statement is immediate.

So the side that does the proposing wins. The figure shows the gap: the same instance admits two stable matchings, and proposer-optimal picks the one where the proposers get their better valid partners and the receivers their worse.

Two stable matchings of one instance. The proposer-optimal one (blue, returned by deferred acceptance) gives each proposer its better valid partner; the receiver-optimal one (gray) is what the receivers would get if they proposed.

The asymmetry carries a design lesson: in deploying such a system you choose which side proposes, and that choice is not neutral. It also has a strategic consequence — a proposer can never gain by misreporting its list, but a receiver sometimes can, a fact that shaped how the real matches were engineered.

Applications

A near-identical procedure assigns tens of thousands of people every year.

The residency match (NRMP). Graduating medical students and residency programs each rank the other, and the National Resident Matching Program computes a stable assignment by deferred acceptance — historically program-proposing, later changed to applicant-proposing precisely because of the optimality asymmetry above: the side that proposes gets its best stable outcome, and reformers wanted that to be the students. Programs admit several residents, so the real system is the hospitals/residents generalization (receivers have capacity $> 1$ ), but the mechanism, proofs, and stability guarantee carry over almost verbatim.

School choice. Many cities assign students to public schools with a deferred-acceptance mechanism: students (or families) submit ranked lists, schools have priorities and capacities, and the algorithm produces a stable, and under the student-proposing version strategy-proof for students, assignment. The practical appeal is the theory itself: stability means no student-school pair is left mutually preferring each other over their assignments, so no family can credibly complain that a swap was available and denied.

These deployments use every theorem above: existence (a stable matching always exists, so the system can always output something), the $O (n^{2})$ bound scaled up (it runs fast at national size), and proposer-optimality (the chosen proposing side provably gets its best stable outcome, which is why who proposes became a policy decision).

Market design and the Nobel-winning legacy

Stable matching launched a whole field.

A Nobel Prize in market design. Gale and Shapley's 1962 paper College Admissions and the Stability of Marriage was pure combinatorics, but its impact came decades later.¹ Alvin Roth showed the National Resident Matching Program had, since 1952, been running essentially the deferred-acceptance algorithm, and that it was stability that kept the market from unraveling; he then redesigned the residency match and, with Elliott Peranson, the mechanisms behind school-choice systems in New York and Boston. Roth and Shapley shared the 2012 Nobel Memorial Prize in Economics for the theory of stable allocations and the practice of market design.² The basis is this lesson's three theorems: a stable matching always exists (so the system can always output one), it is computable fast, and it is proposer-optimal (so who proposes is a policy choice).

Hospitals/residents and the rural-hospitals theorem. Real matches are many-to-one: each hospital admits several residents. The hospitals/residents generalization keeps deferred acceptance almost verbatim (a hospital holds its best $q$ applicants so far), and a structural fact emerges — the rural hospitals theorem (Roth, 1986): the set of residents left unmatched, and the number of positions each hospital fills, is identical across every stable matching.³ An under-subscribed rural hospital cannot improve its intake by gaming which stable matching is chosen; if it is short-staffed in one, it is short-staffed in all. This is why the policy fights are over who proposes (the optimality asymmetry) rather than over which stable matching to pick.

Strategy-proofness and its limits. Proposer-optimal deferred acceptance is strategy-proof for the proposing side (Dubins & Freedman, 1981; Roth, 1982): no proposer can gain by misreporting its list.⁴ But the receiving side can sometimes gain by lying, and no stable mechanism is strategy-proof for everyone at once — a limit that shapes every real deployment. A greedy algorithm from a 1962 math paper became, essentially verbatim, national infrastructure.

Takeaways

A stable matching is a perfect pairing of two equal-size sides with no blocking pair — no proposer and receiver who each prefer the other to their assigned partner.
Gale–Shapley deferred acceptance: free proposers propose down their lists; each receiver tentatively holds its best offer so far and trades up, rejecting the rest. Two invariants drive everything — proposers' offers descend, receivers' held partners improve.
It terminates in at most $n^{2}$ proposals (no proposer asks the same receiver twice), returns a perfect matching (an unmatched proposer would have asked everyone, matching everyone), and that matching is stable (any unmatched pair has a satisfied side).
The output is proposer-optimal and receiver-pessimal: every proposer gets its best valid partner and every receiver its worst, independent of the order proposals are made.
The mechanism runs the residency match and many school-choice systems; whichever side proposes provably gets its best stable outcome, making who proposes a deliberate policy lever.

Gale, D. & Shapley, L. S. (1962), College admissions and the stability of marriage, American Mathematical Monthly 69(1), 9–15 — introduces the stable-marriage problem and the deferred-acceptance algorithm, proving a stable matching always exists. ↩
Roth, A. E. (2002), The economist as engineer: game theory, experimentation, and computation as tools for design economics, Econometrica 70(4), 1341–1378; and the 2012 Sveriges Riksbank Prize in Economic Sciences awarded to Roth and Shapley for the theory of stable allocations and market design. ↩
Roth, A. E. (1986), On the allocation of residents to rural hospitals: a general property of two-sided matching markets, Econometrica 54(2), 425–427 — the rural-hospitals theorem: the set of matched agents is invariant across all stable matchings. ↩
Dubins, L. E. & Freedman, D. A. (1981), Machiavelli and the Gale–Shapley algorithm, American Mathematical Monthly 88(7), 485–494; and Roth, A. E. (1982), The economics of matching: stability and incentives, Mathematics of Operations Research 7(4), 617–628 — strategy-proofness of deferred acceptance for the proposing side, and the impossibility of full strategy-proofness for both sides. ↩

The stable marriage problem

The Gale–Shapley algorithm

Termination and the O(n2) bound

Perfection: everyone gets matched

Stability: no blocking pair survives

The asymmetry: proposer-optimal, receiver-pessimal

Applications

Market design and the Nobel-winning legacy

Takeaways

Footnotes

Termination and the $O (n^{2})$ bound