🧩 Constraint Solving POTD:Problem of the Day: Stable Marriage Problem

[github-actions[bot]]

Problem Statement

The Stable Marriage Problem (SMP) asks: given n men and n women, each with a ranked preference list of all members of the opposite gender, can we find a perfect matching where no unmatched pair would both prefer each other to their current partners?

Concrete Instance

Consider 3 men (M1, M2, M3) and 3 women (W1, W2, W3) with preferences:

Men	Rankings	Women	Rankings
M1	W2 > W1 > W3	W1	M3 > M2 > M1
M2	W1 > W3 > W2	W2	M1 > M3 > M2
M3	W1 > W2 > W3	W3	M2 > M1 > M3

A stable matching is one where no "blocking pair" exists—a man and woman not matched to each other who would both be happier together.

Input/Output

• Input: Preference matrices (m × n) for each gender.
• Output: A perfect matching {(m_i, w_j)} ∀i∈[1..n] such that no pair (m, w) prefers each other to their matched partners.

---

Why It Matters

College and Residency Matching: Medical residency programs worldwide use stable matching algorithms to assign graduating doctors to hospital positions, respecting both applicant and hospital preferences.

Job Markets & Internships: Many internship and entry-level hiring pipelines use variants of the stable marriage algorithm to coordinate offers and acceptances.

Kidney Exchange Programs: Hospitals coordinate living kidney donor–recipient pairs using extensions of this model to find compatible exchanges that maximize fairness.

---

Modeling Approaches

Approach 1: Constraint Programming (CP)

Key idea: Model as bipartite matching with preference constraints.

• Decision variables: match[m] = w (which woman each man is matched to)
• Constraints:
  • alldifferent(match[*]) — each woman matched once
  • For each unmatched pair (m, w): either match[m] is better than w in m's ranking, OR match[w] is better than m in w's ranking (symmetry-breaking)
  • Preference orderings encoded as rank[person][preferred] < rank[person][current]

Trade-offs:

• ✅ Expressive: Constraints directly capture preference logic.
• ✅ Propagation: Global constraints like alldifferent and reified constraints enable strong domain reduction.
• ⚠️ Scalability: O(n2) preference constraints can grow costly; best for medium instances (n ≤ 1000).

Approach 2: Procedural Algorithm (Irving / Gale–Shapley)

Key idea: Iterative proposal-rejection with phase-out logic.

• Gale–Shapley: Men propose in order of preference; women accept tentatively and upgrade if a better proposal arrives. Guaranteed to find a stable matching in O(n2) time.
• Irving's Algorithm: Two phases—proposals followed by eliminations—handles both genders symmetrically.

Trade-offs:

• ✅ Efficiency: Polynomial-time guarantee; practical for any problem size.
• ✅ Simplicity: Elegant, easy to implement and reason about.
• ⚠️ Optimization: Returns a stable matching, not necessarily the best by other criteria.
• ⚠️ Variants: Handling unequal genders, incomplete preference lists, or weighted preferences requires bespoke extensions.

---

Key Techniques

1. Symmetry & Blocking-Pair Characterization

The core insight: a matching is stable iff no blocking pair exists. This transforms the problem from "find any matching" to "ensure all potential blocking pairs are prevented." Encoding this as reified constraints (b ∨ c ∨ ...) enables the solver to prune infeasible regions early.

2. Augmenting Paths & Flow Networks

For weighted or extended SMP variants (e.g., maximizing total preference scores), model as a minimum-cost maximum-flow problem. Men and women are nodes; edges have weights inversely proportional to preference rank. Standard network algorithms find optimal stable matchings in polynomial time.

3. Decomposition & Local Search

For large instances or many-sided matching (e.g., three-agent markets), decompose into sub-problems:

• Pair men greedily by preference agreement; solve subproblems independently.
• Use local search (swaps, trading chains) to improve partial solutions.
• Combine with backtracking for bounded exact search.

---

Challenge Corner

Can you extend the stable marriage model to a three-sided market where we have men, women, and employers, and each must be matched consistently across all three parties? How would you encode "no blocking triple" constraints?

Bonus: If preferences are only partial (not all options ranked), how does this change the CP formulation?

---

References

1. Gale, D. & Shapley, L.S. (1962). "College Admissions and the Stability of Marriage." American Mathematical Monthly, 69(1), 9–15. — The original paper; clear and concise.

2. Knuth, D.E. (1997). Stable Marriage and Its Relation to Other Combinatorial Problems. American Mathematical Society. — Comprehensive book-length treatment with algorithms and complexity.

3. Irving, R.W. (1985). "An Efficient Algorithm for the 'Stable Roommates' Problem." Journal of Algorithms, 6(4), 577–595. — Extends SMP to symmetric preferences; introduces phase-elimination technique.

4. Manlove, D.F. (2013). Algorithmics of Matching Under Preferences. World Scientific. — Modern reference covering variants, approximations, and applications.

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · ~10 AIC · ⌖ ~8 AIC · ⊞ 6.5K · ◷

• expires on Oct 30, 2026, 3:37 AM UTC-08:00

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #71634.