El Problema del Matrimonio EstableEl Problema del Matrimonio Estable
Roger Z. Ríos
Programa de Posgrado en Ing. de SistemasFacultad de Ing. Mecánica y EléctricaUniversidad Autónoma de Nuevo León
http://yalma.fime.uanl.mx/~pisis
Seminario de Clase “Optimización de Flujo en Redes”PISIS – FIME - UANL
Cd. Universitaria 24 Agosto 2007
Agenda
Problem definition
Solution algorithm
Variations and extensions
Real-world application
Problem Definition
2 disjoint sets of size n (women, men)
1 2 1 4 3
2 4 3 1 2
3 1 4 3 2
4 2 1 4 3
1 2 4 1 3
2 3 1 4 2
3 2 3 1 4
4 4 1 3 2
Men’s preferencesWomen’s preferences
Matching M ={(1,1), (2,3), (3,2), (4,4)}
Blocking pair (4,1)
Problem Definition
2 disjoint sets of size n (women, men)
1 2 1 4 3
2 4 3 1 2
3 1 4 3 2
4 2 1 4 3
1 2 4 1 3
2 3 1 4 2
3 2 3 1 4
4 4 1 3 2
Men’s preferencesWomen’s preferences
Matching M ={(1,1), (2,3), (3,2), (4,4)}
Blocking pair (4,1)
Problem Definition
2 disjoint sets of size n (women, men)
1 2 1 4 3
2 4 3 1 2
3 1 4 3 2
4 2 1 4 3
1 2 4 1 3
2 3 1 4 2
3 2 3 1 4
4 4 1 3 2
Men’s preferencesWomen’s preferences
Matching M ={(1,1), (2,3), (3,2), (4,4)}
Blocking pair (4,1)
Problem Definition (SMP)
Instance of size n (n women, n men) and strictly ordered preference list
Matching: 1-1 correspondence between men and women
If woman w and man m matched in M w and m are partners, w=pM(m), m=pM(w)
(w,m) block a match M if w and m are not partners, but w prefers m to pM(w) and m prefers w to pM(m)
A match for which there is at least one blocking pair is unstable
Solution: Properties
Stability checking (for a given matching M) is easy
Stable matching existence (not obvious) due to Gale and Shapley (1962)
Solution: Stability
for (m:=1 to n) do for (each w such that m prefers w to pM(m))
do if (w prefers m to pM(w)) then
report matching unstable stop endifReport matching stable
for (m:=1 to n) do for (each w such that m prefers w to pM(m))
do if (w prefers m to pM(w)) then
report matching unstable stop endifReport matching stable
Simple stability checking algorithmO(n2)
Solution
assign each person to be freewhile (some man m is free) do { w:=first woman on m’s list to whom m has not yet
proposed if (w is free) then assign m and w to be engaged {to each other} else if (w prefers m to her fiance m’) then assign m and w to be engaged and m’ to be
free else w rejects m {and m remains free}} end while
assign each person to be freewhile (some man m is free) do { w:=first woman on m’s list to whom m has not yet
proposed if (w is free) then assign m and w to be engaged {to each other} else if (w prefers m to her fiance m’) then assign m and w to be engaged and m’ to be
free else w rejects m {and m remains free}} end while
Basic Gale-Shapley man-oriented algorithm
Solution: Proof
Theorem: For any given SMP instance the G-S algorithm terminates with a stable matching
Proof: No man can be rejected by all woman Termination in O(n2) No blocking pairs
If m prefers w to pM(m), w must have rejected m at some point for a man she prefers better
Theorem: For any given SMP instance the G-S algorithm terminates with a stable matching
Proof: No man can be rejected by all woman Termination in O(n2) No blocking pairs
If m prefers w to pM(m), w must have rejected m at some point for a man she prefers better
Solution: Example
1 4 1 3 2
2 1 3 2 4
3 1 2 3 4
4 4 1 3 2
1 4 1 2 3
2 2 3 1 4
3 2 4 3 1
4 3 1 4 2
Men’s preferencesWomen’s preferences
Man 1 proposes to woman 4 (accepted)Partial matching M ={(4,1)}
Solution: Example
1 4 1 3 2
2 1 3 2 4
3 1 2 3 4
4 4 1 3 2
1 4 1 2 3
2 2 3 1 4
3 2 4 3 1
4 3 1 4 2
Men’s preferencesWomen’s preferences
Man 1 proposes to woman 4 (accepted)Partial matching M ={(4,1)}
Man 2 proposes to woman 2 (accepted)Partial matching M ={(2,2), (4,1)}
Solution: Example
1 4 1 3 2
2 1 3 2 4
3 1 2 3 4
4 4 1 3 2
1 4 1 2 3
2 2 3 1 4
3 2 4 3 1
4 3 1 4 2
Men’s preferencesWomen’s preferences
Man 1 proposes to woman 4 (accepted)Partial matching M ={(4,1)}
Man 2 proposes to woman 2 (accepted)Partial matching M ={(2,2), (4,1)}
Solution: Example
1 4 1 3 2
2 1 3 2 4
3 1 2 3 4
4 4 1 3 2
1 4 1 2 3
2 2 3 1 4
3 2 4 3 1
4 3 1 4 2
Men’s preferencesWomen’s preferences
Man 3 proposes to woman 2(accepted and women 2 rejects man 2)Partial matching M ={(2,3), (4,1)}
Solution: Example
1 4 1 3 2
2 1 3 2 4
3 1 2 3 4
4 4 1 3 2
1 4 1 2 3
2 2 3 1 4
3 2 4 3 1
4 3 1 4 2
Men’s preferencesWomen’s preferences
Man 3 proposes to woman 2(accepted and women 2 rejects man 2)Partial matching M ={(2,3), (4,1)}
Man 2 proposes to woman 3 (accepted)Partial matching M ={(2,3), (3,2), (4,1)}
Solution: Example
1 4 1 3 2
2 1 3 2 4
3 1 2 3 4
4 4 1 3 2
1 4 1 2 3
2 2 3 1 4
3 2 4 3 1
4 3 1 4 2
Men’s preferencesWomen’s preferences
Man 3 proposes to woman 2(accepted and women 2 rejects man 2)Partial matching M ={(2,3), (4,1)}
Man 2 proposes to woman 3 (accepted)Partial matching M ={(2,3), (3,2), (4,1)}
Solution: Example
1 4 1 3 2
2 1 3 2 4
3 1 2 3 4
4 4 1 3 2
1 4 1 2 3
2 2 3 1 4
3 2 4 3 1
4 3 1 4 2
Men’s preferencesWomen’s preferences
Man 4 proposes to woman 3(rejected, woman 3 prefers man 2)Partial matching M ={(2,3), (3,2), (4,1)}
Solution: Example
1 4 1 3 2
2 1 3 2 4
3 1 2 3 4
4 4 1 3 2
1 4 1 2 3
2 2 3 1 4
3 2 4 3 1
4 3 1 4 2
Men’s preferencesWomen’s preferences
Man 4 proposes to woman 3(rejected, woman 3 prefers man 2)Partial matching M ={(2,3), (3,2), (4,1)}
Man 4 proposes to woman 1 (accepted)Final Matching M ={(1,4), (2,3), (3,2), (4,1)}(Stable matching)
Solution: Example
1 4 1 3 2
2 1 3 2 4
3 1 2 3 4
4 4 1 3 2
1 4 1 2 3
2 2 3 1 4
3 2 4 3 1
4 3 1 4 2
Men’s preferencesWomen’s preferences
Man 4 proposes to woman 3(rejected, woman 3 prefers man 2)Partial matching M ={(2,3), (3,2), (4,1)}
Man 4 proposes to woman 1 (accepted)Final Matching M ={(1,4), (2,3), (3,2), (4,1)}(Stable matching)
Extensions/Variations
Stable Marriage Problem Sets of unequal size Unnacceptable partners Indifference
Stable Roommate Problem
Stable Resident/Hospital Problem
Real-World Application
Stable Resident/Hospital Problem (SRHP)
Largest and best-known application of SMP
Used by the National Resident Matching Program
(NRMP)
SRHP Application
R (residents), H (hospitals), qi:= # of available spots in hospital i
(r,h) is a blocking pair if r prefers h to his/her current hospital and h prefers r to at least one of its assigned residents
Solution: Transformation into a SMP Specialized algorithm
SRHP Application
History 1st dilemma: Early proposals
2nd dilemma: Tight acceptance
start
start
-1
-2
SRHP Application
Solution: Transformation into a SMP Specialized algorithm
SRHP InstanceResidents r1 (h1, h2, h3, …)
…
Hospitals h1 (r1, r2, r3, …), q1=3
…
SMP InstanceResidents r1 (h11, h12, h13, h2, h3, …)
…
Hospitals h11 (r1, r2, r3, …)
h12 (r1, r2, r3, …)
h13 (r1, r2, r3, …)
…
Related Hard Problems
Finding all different stable matchings
Maximum number of stable matchings
Parallelization
Conclusions
Stable matchings
Gale-Shapley algorithm
Math/Computer Science/Economics
Scientific support to decision-making
Questions?
http://yalma.fime.uanl.mx/~roger
AcknowledgementAcknowledgements:s:
Racing - BarçaRacing - BarçaEl SardineroEl SardineroThis Sunday 12:00 CDTThis Sunday 12:00 CDT
Top Related