Skip to content
Tutorials Center
My learning

Topics

Lesson 131 of 225 ยท Graphs

Stable Marriage and the Hungarian Algorithm

Match two groups with the Gale-Shapley stable marriage algorithm and solve the minimum-cost assignment problem with the Hungarian algorithm in O(n^3) in Python.

Matching problems ask you to pair up items from two groups. Two famous versions look similar but optimize different things.

  • In stable matching, every person ranks the other side, and you want a pairing where nobody wants to leave their partner for someone who also prefers them. Think of students and schools, or doctors and hospitals.
  • In the assignment problem, each pair has a cost, and you want the pairing with the smallest total cost. Think of workers and jobs, or taxis and passengers.

This lesson implements the Gale-Shapley algorithm for the first and the Hungarian algorithm for the second, and verifies both against brute-force search on small inputs. Both are matchings in bipartite graphs (bipartite graphs); for matching without costs or preferences see network flow.

Stable marriage

There are n proposers and n receivers, and every person has a complete ranking of the other side. A matching is unstable if some proposer a and receiver b are not matched to each other, yet a prefers b to their partner and b prefers a to theirs: a blocking pair. A matching with no blocking pair is stable.

The Gale-Shapley algorithm

  1. Every proposer is free.
  2. While some proposer a is free and has not yet proposed to everyone: a proposes to the highest-ranked receiver b on their list that they have not tried.
  3. If b is free, they accept (tentatively). If b is matched but prefers a, b dumps their current partner (who becomes free again) and accepts a. Otherwise b refuses.

Each proposer proposes to each receiver at most once, so there are at most n^2 proposals: O(n^2) time. The algorithm always ends with a perfect stable matching.

flowchart TD
  A["Free proposer a"] --> B["Propose to best untried receiver b"]
  B --> C{"Is b free?"}
  C -->|yes| D["b accepts a"]
  C -->|no| E{"Does b prefer a to the current partner?"}
  E -->|yes| F["b switches to a, old partner becomes free"]
  E -->|no| G["b refuses, a stays free"]

A receiver only ever trades up, a proposer only ever moves down their list.

Python Gale-Shapley with a stability check

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

What makes the result special

Gale-Shapley is proposer-optimal: among all stable matchings, every proposer gets the best partner they could get in any stable matching, while every receiver gets their worst. So the side that proposes has the advantage. That is why real systems (like medical residency matching) have been studied carefully for who proposes.

Common mistakes: using incomplete lists without handling unmatched people, forgetting that a refused or dumped proposer continues down their list rather than restarting, and storing receiver preferences as lists (use a rank table so each comparison is O(1)).

The assignment problem

n workers, n jobs, and a cost matrix cost[i][j]. Assign each worker one job, each job to one worker, minimizing total cost. Brute force tries all n! permutations. The Hungarian algorithm solves it in O(n^3).

You could also solve it as a min-cost flow problem (see push-relabel and min-cost flow), or by bitmask DP in O(2^n * n) (bitmask DP), but for n up to a few hundred the Hungarian algorithm is the tool.

The idea: potentials

Give every row i a potential u[i] and every column j a potential v[j], and subtract: define the reduced cost cost[i][j] - u[i] - v[j]. As long as the potentials keep every reduced cost >= 0, a matching that uses only zero-reduced-cost cells is optimal, because its total cost equals sum of u + sum of v, which is a lower bound for any assignment.

The algorithm adds rows one at a time. For each new row it grows a tree of "tight" cells (reduced cost zero) with a Dijkstra-like search, and when it gets stuck it adjusts the potentials by the smallest slack delta, which creates a new tight cell without breaking the invariant. It then flips an augmenting path to enlarge the matching by one. This is the compact variant using arrays u, v, p (matched row of each column) and way.

Python Hungarian algorithm, checked against brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The 120 by 120 case finishes quickly because the work is about n^3, roughly 1.7 million basic steps.

Variants

  • Maximize the total: negate every cost (or use max_value - cost) and minimize.
  • Rectangular matrix (more jobs than workers): pad with dummy rows of cost 0.
  • Forbidden pairs: give them a very large cost and check the result.

Which one do I need?

Question Algorithm Time
Pair two groups by preferences with no incentive to break pairs Gale-Shapley O(n^2)
Pair by cost to minimize the total Hungarian O(n^3)
Pair without costs, maximum number of pairs bipartite matching with flow O(V E) or better
Tiny n (up to about 20) with side conditions bitmask DP O(2^n n)

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What is a blocking pair in stable matching?

    A blocking pair could leave their partners together and both be happier, which makes the matching unstable.
  2. 2. How many proposals does Gale-Shapley make in the worst case for n proposers?

    Each proposer proposes to each receiver at most once, so there are at most n * n proposals.
  3. 3. Who benefits in Gale-Shapley, the proposers or the receivers?

    The result is proposer-optimal and receiver-pessimal among all stable matchings.
  4. 4. What is the running time of the Hungarian algorithm for an n by n cost matrix?

    Each of the n rows is added with an augmenting search that costs O(n^2), giving O(n^3).

Summary

  • Stable matching asks for no blocking pairs; Gale-Shapley finds one in O(n^2) proposals and favors the proposing side.
  • The assignment problem minimizes total cost; the Hungarian algorithm solves it in O(n^3) with row and column potentials.
  • Maximize by negating costs, pad rectangular matrices with zero-cost dummies.
  • Verify both on small inputs with brute force (blocking pairs, permutations).

Next: Network Flow