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

[github-actions[bot]]

Constraint Problem of the Day: The Stable Marriage Problem

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, find a stable matching where no man-woman pair would rather be with each other than their current partners.

Concrete Instance (4×4)

Men's preferences:

• Adam: (Alexis, Beth, Cynthia, Diana)
• Brian: (Beth, Alexis, Diana, Cynthia)
• Charlie: (Cynthia, Alexis, Beth, Diana)
• David: (Diana, Cynthia, Beth, Alexis)

Women's preferences:

• Alexis: (Brian, Adam, David, Charlie)
• Beth: (Adam, Brian, Charlie, David)
• Cynthia: (Charlie, Adam, Brian, David)
• Diana: (David, Adam, Brian, Charlie)

Goal: Find a pairing such that no unmarried couple mutually prefer each other over their current spouses.

Input/Output Specification

• Input: Two matrices M[i][j] and W[i][j] where M[i][j] is man i's preference rank of woman j (1 = most preferred)
• Output: A matching (permutation π where woman π(i) is matched to man i) that is stable (no blocking pairs)

Why It Matters

Real-world applications:

• Medical residency matching: The NRMP (National Resident Matching Program) uses a stable marriage algorithm to assign graduating physicians to hospital residencies, affecting the livelihoods of thousands annually.
• School choice & college admissions: Many public school districts use SMP-based algorithms to assign students to schools in a fair, stable manner.
• Labor market matching: Job seekers and employers both benefit from stable algorithmic matchings that reduce subsequent contract renegotiations.

---

Modeling Approaches

Approach 1: Constraint Programming (Declarative)

Model the problem using finite domain variables and global constraints:

Decision variables: wife[m] ∈ {1..n} ∀ m ∈ men  (who is each man matched to)
                   husband[w] ∈ {1..n} ∀ w ∈ women (who is each woman matched to)

Constraints:
  1. AllDifferent(wife)  // each man matched to different woman
  2. AllDifferent(husband)  // each woman matched to different man
  3. wife[m] = w ⇔ husband[w] = m  // match consistency
  4. Stability: ∀ (m, w) not matched:
       rank_m[w] > rank_m[wife[m]] OR rank_w[m] > rank_w[husband[m]]
       (if either prefers current partner, no blocking pair)

Objective: Minimize blocked pairs (or find any stable matching)

Trade-offs:

• ✓ Highly expressive; easily extends to variants (multiple slots, fairness constraints)
• ✓ Propagation can eliminate many candidates early
• ✗ Stability constraints are global and asymmetric; weaker propagation than some alternatives

Approach 2: Graph Theory / Matching Algorithm (Constructive)

Use the Gale-Shapley algorithm, a polynomial-time greedy procedure:

Algorithm: Gale-Shapley
  Initialize: all men and women are free
  
  while ∃ free man m with remaining proposals do
    w ← next woman on m's preference list
    if w is free then
      match (m, w)
    else
      m' ← w's current partner
      if w prefers m to m' then
        unmatch (m', w)
        match (m, w)
      else
        leave w matched with m'
    end if
  end while
  
  Return final matching

Trade-offs:

• ✓ Guaranteed O(n2) solution time; always finds a stable matching
• ✓ Simple to implement and understand
• ✓ Man-optimal: each man gets the best possible stable partner
• ✗ Not woman-optimal; women may prefer another stable matching
• ✗ Less flexible for side constraints (e.g., fairness, multiple slots)

---

Key Techniques

1. Stability Checking via Blocking Pair Enumeration

After any proposed matching, verify stability by checking all O(n2) potential blocking pairs. A pair (m, w) blocks the matching if both prefer each other to their current partners. This is the verification step in both algorithmic and CP-based approaches.

2. Symmetry Breaking & Preference Reduction

• Dominated preferences: If woman w prefers woman w' to all men, we can prune proposals from men she ranks below w'.
• Symmetry: The SMP is symmetric in roles; man-optimal and woman-optimal stable matchings bound the solution space. Forcing one role breaks the search asymmetry.

3. Local Search & Randomization

For extensions (weighted SMP, many-to-one matching), use local search to escape local optima:

• Swap pairs in a current matching if they improve a fairness or preference score
• Randomized restarts to explore different regions of the solution space

---

Challenge Corner

Open Questions for Readers:

1. Fairness & Optimality: The Gale-Shapley algorithm favors proposers (men). Can you design or prove existence of a fair stable matching that maximizes the minimum preference rank across all participants?

2. Weighted Extensions: Suppose each man-woman pair has a "happiness weight" reflecting mutual preference strength. How would you model finding the stable matching with maximum total happiness? (Hint: combine SMP stability constraints with MIP objectives.)

3. Many-to-One: How would you extend the model to allow women to accept multiple men (e.g., hospitals with multiple residency slots)? What new blocking pair definitions emerge?

---

References

1. Gale, D. & Shapley, L. S. (1962). "College Admissions and the Stability of Marriage." American Mathematical Monthly, 69(1), 9–15.

   • The foundational paper; remarkably concise and elegant.

2. Roth, A. E. & Sotomayor, M. A. O. (1990). Two-Sided Matching: A Study in Game-Theoretic Modeling and Analysis. Cambridge University Press.

   • Comprehensive treatment including game-theoretic implications and real-world applications.

3. Irving, R. W. (1985). "An Efficient Algorithm for the 'Stable Roommates' Problem." Journal of Algorithms, 6(4), 577–595.

   • Extends SMP to the roommates problem (no two genders); characterizes when stable matchings exist.

4. Constraint Programming for Operations Research tutorials (e.g., OR-Tools, MiniZinc docs)

   • Modern solvers provide efficient global constraints and symmetry-breaking heuristics for matching problems.

---

Happy solving! Share your thoughts on fairness in matching or extensions you'd explore. 🤝

Generated by 🧩 Constraint Solving — Problem of the Day · 44.6 AIC · ⌖ 4.35 AIC · ⊞ 25.4K · ◷

• expires on Jun 19, 2026, 4:44 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 #39071.