Chapter 4. The Stable Marriage Problem
Gale-Shapley as the LLP main loop on the proposal-vector lattice.
This page: LLP forms. View classical forms »
The proposal vector
Consider $n$ men and $n$ women, each with a strict preference list over the other side. A proposal vector $G$ assigns to every man $i$ his current proposal index $G[i] \in \{1, \ldots, n\}$ — meaning man $i$ is currently proposing to his $G[i]$-th-preferred woman. Smaller values are top choices.
Man $j$ is forbidden in $G$ if some other man $j'$ is currently proposing to the same woman that $j$ is, and that woman strictly prefers $j'$ over $j$. The advance rule increments $G[j]$ — $j$ moves on to his next-preferred woman. The fixed point is a stable matching, and is exactly what the Gale-Shapley algorithm computes.
LLP-StableMarriage
The demo runs on any $n \times n$ instance. The default values describe the 3-man, 3-woman case shown below; edit the input boxes for any other size (every preference row must have the same number of entries, indices are 1-based, and the initial proposal indices are typically all $1$).
Time complexity: $O(n^2)$, where $n$ is the number of men (= number of women).
Default preferences (top to bottom = most to least preferred):
| Men's preferences | |||
|---|---|---|---|
| 1st | 2nd | 3rd | |
| m₁ | w₂ | w₃ | w₁ |
| m₂ | w₂ | w₃ | w₁ |
| m₃ | w₃ | w₁ | w₂ |
| Women's preferences | |||
|---|---|---|---|
| 1st | 2nd | 3rd | |
| w₁ | m₁ | m₃ | m₂ |
| w₂ | m₂ | m₁ | m₃ |
| w₃ | m₁ | m₂ | m₃ |
On the default instance the proposal vector starts at $G = (1, 1, 1)$ — every man proposes to his top choice. The demo highlights any forbidden man (one whose proposed woman currently prefers a rival) and advances his proposal one step at a time. The same algorithm applies for any $n$: the vector $G$ has length $n$, and the forbidden / advance loop iterates over $j = 1, \ldots, n$.
LLP predicates for this chapter
Each LLP program in this chapter defines a state vector $G$ and a
forbidden predicate; the algorithm runs until no $j$ is forbidden.
The table below lists, for each algorithm, what $G[i]$ represents and the
negation of the forbidden clause from the matching .llp source.
| Algorithm | $G[j]$ | Negation of the forbidden clause |
|---|---|---|
| LLP-StableMarriage | $G[j]$ — man $j$'s proposal index | $\forall j,\, i,\, k \leq G[i]:\ \neg\bigl(\mathrm{mpref}[j][G[j]] = \mathrm{mpref}[i][k] \,\wedge\, \mathrm{rank}[\mathrm{mpref}[j][G[j]]][i] < \mathrm{rank}[\mathrm{mpref}[j][G[j]]][j]\bigr)$ |
Looking ahead
The proposal-vector lattice and the “forbidden / advance” structure of this chapter are reused throughout the book. Chapter 5 applies the same machinery to sorting via the inversion-vector lattice. Later chapters use it for shortest paths, minimum spanning trees, and dynamic programming. For the classical Gale-Shapley listing, see the classical companion page.