Transcript Stable Marriage Problem - University of Arizona Math

Stable Marriage Problem
William Kozma Jr
ECE 443/543
History
• Gale-Shapley 1962, “College Admissions and
the Stability of Marriage”
• Introduced both monogamous and
polygamous versions
• Polygamous version used for years
• Assigned “job applicants” to “job positions”
The Problem
•
•
•
•
Exists two equal-sized sets
Each element ranks all elements in other set
Match is one-to-one between sets
Matching must be stable
– Cannot exists a member from each set which
would rather be matched with each other, than
with their current match
Example
Alice
Rank = {bob, adam}
Beth
Rank = {bob, adam}
adam
Rank = {Alice, Beth}
bob
Rank = {Alice, Beth}
Algorithm
• [Morning] Each Boy goes to the Girl on the
top of his list.
• [Afternoon] Girl selects the highest ranking
Boy visiting her. Sends rest home.
• [Night] All Boys not selected cross the top Girl
off their list.
Program: Input
• Rankings imputed in data file
• First line must contain size of each set
• List Rankings
file.txt
3
a
b
c
A
B
C
A
A
B
b
b
a
B
C
C
a
c
c
C
B
A
c
a
b
Program: Data Structures
• Allocate memory for,
– 2 arrays [iSize x iSize]: hold rankings
– 2 arrays [iSize]: list members of each set
– 2 arrays [iSize]: current position on respective list
• Initialize Boys position to 1 and Girls to -1
Program: Loop
• [Morning] *already done in position array
• [Afternoon] Each Girl searches Boy’s position
on his list to see if corresponds to her. Sets
her position to highest ranking Boy found.
• [Night] Each Boy checks of he is listing in any
of the Girls position. In not, increment his
ranking.
Program: Loop (cont)
• Initialize iCounter == 0 each loop iteration
• iCounter++ if rejection occurs
• Loop until iCounter == 0;
• Result is Stable Matching
Program: Demo
Program: Improvements
• In “real-world” all Girls make decisions
simultaneously
• Since program is linear, allow Boys to visit
more than 1 Girl per day
• If a Boy is rejected, automatically send him to
his next highest ranking Girl
• May not always result in less days, but will
never be worse.
Program: Demo 2
Questions?