Published by Dimitris Kougioumtzis · Updated
Proposers make offers in preference order; receivers retain their preferred offer. Complete strict lists produce a proposer-optimal stable matching.
Proposers advance through preferences while receivers retain their best proposal so far; each pair is considered at most once.
When to use Stable marriage (Gale–Shapley)
Stable two-sided allocation with strict complete preferences.
Choosing an alternative
Maximum-weight assignment optimizes utility, not the absence of blocking pairs.
Worked example: input and state changes
Example input
0,1,2;1,0,2;1,2,0 | 1,0,2;0,1,2;0,1,2
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: All participants begin unmatched.
State at this checkpoint
{ "values": [ "free", "free", "free", "free", "free", "free" ], "active": [], "kind": "graph", "bipartite": true, "nodeLabels": [ "P0", "P1", "P2", "R0", "R1", "R2" ], "chosen": [], "visited": [], "partners": [ -1, -1, -1 ] }Step 2: R0 retains P0.
State at this checkpoint
{ "values": [ "R0", "free", "free", "P0", "free", "free" ], "active": [ 0, 3 ], "kind": "graph", "bipartite": true, "nodeLabels": [ "P0", "P1", "P2", "R0", "R1", "R2" ], "chosen": [ 0 ], "visited": [ 0, 3 ], "partners": [ 0, -1, -1 ] }Step 5: Proposer P2 offers to R1.
State at this checkpoint
{ "values": [ "R0", "R1", "free", "P0", "P1", "free" ], "active": [ 2, 4 ], "kind": "graph", "bipartite": true, "nodeLabels": [ "P0", "P1", "P2", "R0", "R1", "R2" ], "chosen": [ 0, 1 ], "visited": [ 0, 3, 1, 4 ], "partners": [ 0, 1, -1 ] }Step 7: Proposer P2 offers to R2.
State at this checkpoint
{ "values": [ "R0", "R1", "free", "P0", "P1", "free" ], "active": [ 2, 5 ], "kind": "graph", "bipartite": true, "nodeLabels": [ "P0", "P1", "P2", "R0", "R1", "R2" ], "chosen": [ 0, 1 ], "visited": [ 0, 3, 1, 4 ], "partners": [ 0, 1, -1 ] }Step 9: Stable proposer-optimal matching complete.
State at this checkpoint
{ "values": [ "R0", "R1", "R2", "P0", "P1", "P2" ], "active": [], "kind": "graph", "bipartite": true, "nodeLabels": [ "P0", "P1", "P2", "R0", "R1", "R2" ], "chosen": [ 0, 1, 2 ], "visited": [ 0, 3, 1, 4, 2, 5 ], "partners": [ 0, 1, 2 ] }
Expected final state
Stable proposer-optimal matching complete.
Complexity and input bounds
Family: Greedy. Time complexity: O(n²).
Space complexity: O(n squared) preference ranks plus O(n) matching state.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
Proposer preference rows | receiver preference rows. Rows separated by semicolons; 1–5 participants per side, each row a permutation of 0..n-1.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Stability does not mean maximum total happiness; the result favors the proposing side among stable matchings.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | // 1–5 participants per side. Both arrays contain n row-major permutations of 0..n-1 with strict complete preferences. Writes proposer-to-receiver partners and returns n. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(proposers, receivers, n, output) { let ranks = Array(256).fill(0); let matched = Array(256).fill(0); let next = Array(256).fill(0); let queue = Array(256).fill(0); for (let w = 0; w < n; w++) { matched[w] = -1; output[w] = -1; queue[w] = w; for (let i = 0; i < n; i++) { ranks[w * n + receivers[w * n + i]] = i; } } let head = 0; let tail = n; while (head < tail) { let m = queue[head++]; let w = proposers[m * n + next[m]++]; let old = matched[w]; if (old < 0 || ranks[w * n + m] < ranks[w * n + old]) { matched[w] = m; output[m] = w; if (old >= 0) { output[old] = -1; queue[tail++] = old; } } else { queue[tail++] = m; } } return n; } |
Source
Primary research source for the algorithm or its underlying method. The playground is a bounded teaching implementation, not the publication's original program.
- College Admissions and the Stability of Marriage
D. Gale; L. S. Shapley (1962). Research paper.