Stable Marrage
The Overview
Given a set of n number of males and a set of n number of females, have each group rate each member in ascending order of preference.
The algorithm terminates when a stable-perfect matching is found.
A unstable perfect matching is when women w is paired with man m, but there exists a situation where man m' prefers w, and w prefers m' back.
i.e. there exists a situation where the engagements should mutually change.
A stable perfect matching is when all men and women are paired in such a way that there exist no situation where man m and women w prefer each other and all are engaged.
A day is considered to be 1 full iteration in the algorithm. That is, every day every male proposes to his best preference. The first pseudo implementation does not have a clear concept of a 'day', but the second one does.
http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/01StableMatching.pdf
English-Code :: Gale-Shapely Algorithm:
Have each man propose the his first preference.
Have each women select her most preferred option from the from the current set of proposals, breaking a current engagement if necessary.
Note: If all man have unique women preferences (some permutation of the women), then everyone is engaged on day 1, although it may not necessarily be stable.
Continue until stable-perfect matching
Observations
Once matched a female does not become unmatched. She only trades up.
Once a male is matched, he can potentially become unmatched, and when he is unmatched, he can only trade down.
Running time: O(M∗F)
Pseudo-code
function stableMatching {
Initialize all m ∈ M and w ∈ W to free
while ∃ free man m who still has a woman w to propose to {
w = first woman on m’s list to whom m has not yet proposed
if w is free
(m, w) become engaged
else some pair (m', w) already exists
if w prefers m to m'
m' becomes free
(m, w) become engaged
else
(m', w) remain engaged
}
}Gale Shapely Algorithm
while (male_n is unmatched) {
Have male_n prepose to his first preference female_m
If female_n is unmatched, or prefers male_n over her current partner, then match female_m with male_n.
if male_n is rejected (continue - and have male_n propose to female_m+1)
if male_n is accepted, move on to the next male_n+1 in list.
continue until every male_n is matched
}Alternatively:
while (!every is matched) {
Have male_n propose to his best preference female_m
If female_m is unmatched, or prefers male_n over her current partner, then match female_m with male_n.
if male_n is rejected, continue to m_n+1 (do nothing)
continue to day_n+1 where every unmatched male proposes to his next best preference.
}Implementation see slide 14 http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/01StableMatching.pdf
Males and Females
abe, bob, col, dan, ed, fred, gav, hal, ian, jon
abi, bea, cath, dee, eve, fay, gay, hope, ivy, janRankings
abe: abi, eve, cath, ivy, jan, dee, fay, bea, hope, gay
bob: cath, hope, abi, dee, eve, fay, bea, jan, ivy, gay
col: hope, eve, abi, dee, bea, fay, ivy, gay, cath, jan
dan: ivy, fay, dee, gay, hope, eve, jan, bea, cath, abi
ed: jan, dee, bea, cath, fay, eve, abi, ivy, hope, gay
fred: bea, abi, dee, gay, eve, ivy, cath, jan, hope, fay
gav: gay, eve, ivy, bea, cath, abi, dee, hope, jan, fay
hal: abi, eve, hope, fay, ivy, cath, jan, bea, gay, dee
ian: hope, cath, dee, gay, bea, abi, fay, ivy, jan, eve
jon: abi, fay, jan, gay, eve, bea, dee, cath, ivy, hope
abi: bob, fred, jon, gav, ian, abe, dan, ed, col, hal
bea: bob, abe, col, fred, gav, dan, ian, ed, jon, hal
cath: fred, bob, ed, gav, hal, col, ian, abe, dan, jon
dee: fred, jon, col, abe, ian, hal, gav, dan, bob, ed
eve: jon, hal, fred, dan, abe, gav, col, ed, ian, bob
fay: bob, abe, ed, ian, jon, dan, fred, gav, col, hal
gay: jon, gav, hal, fred, bob, abe, col, ed, dan, ian
hope: gav, jon, bob, abe, ian, dan, hal, ed, col, fred
ivy: ian, col, hal, gav, fred, bob, abe, ed, jon, dan
jan: ed, hal, gav, abe, bob, jon, col, ian, fred, dannamespace {
typedef unordered_map<string, pair<string, unsigned>> cur_pref;
typedef unordered_map<string, unordered_map<unsigned, string>> pref;
typedef unordered_map<string, unordered_map<string, unsigned>> pref_inv;
}
// male string that maps a rating, by day, that maps to the women string
class stable_marriage {
public:
stable_marriage(const pref &male_p, const pref &female_p)
: male(male_p), female(female_p) {
day = 1; // aka ranking by day
unordered_map<string, unsigned> temp;
// create bi-direction
for (auto f : female_p) {
string female = f.first;
for (auto m : f.second) {
string male = m.second;
unsigned ranking = m.first;
auto &found = female_inv.find(female);
if (found == female_inv.end()) {
temp.insert(make_pair(male, ranking));
female_inv.insert(make_pair(female, temp));
temp.clear();
}
else {
found->second.insert(make_pair(male, ranking));
}
}
}
// debugging
print_pref(1); cout << endl; //pause();
print_pref(0); cout << endl; //pause();
print_inv_pref(); cout << endl; //pause();
}
void go() {
while (day <= 10) {
for (auto m : male) {
// male that will propose
string male = m.first;
// female that male will propose to
string prefers = m.second.find(day)->second;
// find if women is currently matched
auto &found = fm_pair.find(prefers);
if (found == fm_pair.end()) {
// match not found - find the ranking of the man who prefers the women,
// from womens perspective
unsigned women_perspective_ranking = female_inv.find(prefers)->second.find(male)->second;
// match the two pairs
fm_pair.insert(make_pair(prefers, make_pair(male, day)));
}
else {
// match has been found -> check if situation is mutual
if (male == "ian" && prefers == "dee") {
/// bugs....
auto one = female_inv.find(prefers);
auto two = one->second;
auto three = two.find(male);
auto four = three->second;
}
unsigned cur_engagement_rank = found->second.second;
unsigned proposed_engagement_rank = female_inv.find(prefers)->second.find(male)->second;
if (cur_engagement_rank > proposed_engagement_rank) {
// make a new engagement
found->second.first = male;
found->second.second = proposed_engagement_rank;
}
}
}
day++;
}
}
void print_results() {
for (auto i : fm_pair) cout << setw(5) << i.first << " : " << i.second.first << endl;
}
// https://rosettacode.org/wiki/Stable_marriage_problem#C.2B.2B
private:
unsigned day;
const pref male;
const pref female;
pref_inv female_inv;
// <"women", pair<"man", rank>>
cur_pref fm_pair;
void print_pref(bool males) {
if (males) {
cout << "MALE PREFERENCES" << endl;
for (auto m : male) {
cout << setw(5) << m.first << " : ";
for (auto f : m.second) {
cout << f.second << "(" << f.first << "), ";
}
cout << endl;
}
}
else {
cout << "FEMALE PREFERENCES" << endl;
for (auto f : female) {
cout << setw(5) << f.first << " : ";
for (auto m : f.second) {
cout << m.second << "(" << m.first << "), ";
}
cout << endl;
}
}
}
void print_inv_pref() {
cout << "FEMALE PREFERENCES-INVERSE" << endl;
for (auto f : female_inv) {
cout << setw(5) << f.first << " : ";
for (auto m : f.second) {
cout << "(" << m.second << ")" << m.first << ", ";
}
cout << endl;
}
}
};
int main() {
// unordered_map<string, unordered_map<unsigned, string>>
const pref males = {
{ "abe" ,{ { 1, "abi" },{ 2, "eve" },{ 3, "cath" },{ 4, "ivy" },{ 5, "jan" },{ 6, "dee" },{ 7, "fay" },{ 8, "bea" },{ 9, "hope" },{ 10, "gay" } } },
{ "bob" ,{ { 1, "cath"},{ 2, "hope"},{ 3, "abi" },{ 4, "dee" },{ 5, "eve" },{ 6, "fay" },{ 7, "bea" },{ 8, "jan" },{ 9, "ivy" },{ 10, "gay" } } },
{ "col" ,{ { 1, "hope"},{ 2, "eve" },{ 3, "abi" },{ 4, "dee" },{ 5, "bea" },{ 6, "fay" },{ 7, "ivy" },{ 8, "gay" },{ 9, "cath" },{ 10, "jan" } } },
{ "dan" ,{ { 1, "ivy" },{ 2, "fay" },{ 3, "dee" },{ 4, "gay" },{ 5, "hope" },{ 6, "eve" },{ 7, "jan" },{ 8, "bea" },{ 9, "cath" },{ 10, "abi" } } },
{ "ed" ,{ { 1, "jan" },{ 2, "dee" },{ 3, "bea" },{ 4, "cath" },{ 5, "fay" },{ 6, "eve" },{ 7, "abi" },{ 8, "ivy" },{ 9, "hope" },{ 10, "gay" } } },
{ "fred",{ { 1, "bea" },{ 2, "abi" },{ 3, "dee" },{ 4, "gay" },{ 5, "eve" },{ 6, "ivy" },{ 7, "cath" },{ 8, "jan" },{ 9, "hope" },{ 10, "fay" } } },
{ "gav" ,{ { 1, "gay" },{ 2, "eve" },{ 3, "ivy" },{ 4, "bea" },{ 5, "cath" },{ 6, "abi" },{ 7, "dee" },{ 8, "hope" },{ 9, "jan" },{ 10, "fay" } } },
{ "hal" ,{ { 1, "abi" },{ 2, "eve" },{ 3, "hope" },{ 4, "fay" },{ 5, "ivy" },{ 6, "cath" },{ 7, "jan" },{ 8, "bea" },{ 9, "gay" },{ 10, "dee" } } },
{ "ian" ,{ { 1, "hope"},{ 2, "cath"},{ 3, "dee" },{ 4, "gay" },{ 5, "bea" },{ 6, "abi" },{ 7, "fay" },{ 8, "ivy" },{ 9, "jan" },{ 10, "eve" } } },
{ "jon" ,{ { 1, "abi" },{ 2, "fay" },{ 3, "jan" },{ 4, "gay" },{ 5, "eve" },{ 6, "bea" },{ 7, "dee" },{ 8, "cath" },{ 9, "ivy" },{ 10, "hope" } } },
};
const pref females = {
{ "abi" ,{ { 1, "bob" },{ 2, "fred" },{ 3, "jon" },{ 4, "gav" },{ 5, "ian" } ,{ 6, "abe" },{ 7, "dan" } ,{ 8, "ed" },{ 9, "col" } ,{ 10, "hal" } } },
{ "bea" ,{ { 1, "bob" },{ 2, "abe" },{ 3, "col" },{ 4, "fred"},{ 5, "gav" } ,{ 6, "dan" },{ 7, "ian" } ,{ 8, "ed" },{ 9, "jon" } ,{ 10, "hal" } } },
{ "cath",{ { 1, "fred" },{ 2, "bob" },{ 3, "ed" },{ 4, "gav" },{ 5, "hal" } ,{ 6, "col" },{ 7, "ian" } ,{ 8, "abe"},{ 9, "dan" } ,{ 10, "jon" } } },
{ "dee" ,{ { 1, "fred" },{ 2, "jon" },{ 3, "col" },{ 4, "abe" },{ 5, "ian "} ,{ 6, "hal" },{ 7, "gav" } ,{ 8, "dan"},{ 9, "bob" } ,{ 10, "ed" } } },
{ "eve" ,{ { 1, "jon" },{ 2, "hal" },{ 3, "fred" },{ 4, "dan "},{ 5, "abe" } ,{ 6, "gav" },{ 7, "col" } ,{ 8, "ed" },{ 9, "ian" } ,{ 10, "bob" } } },
{ "fay" ,{ { 1, "bob" },{ 2, "abe" },{ 3, "ed" },{ 4, "ian" },{ 5, "jon" } ,{ 6, "dan" },{ 7, "fred"} ,{ 8, "gav"},{ 9, "col" } ,{ 10, "hal" } } },
{ "gay" ,{ { 1, "jon" },{ 2, "gav" },{ 3, "hal" },{ 4, "fred"},{ 5, "bob "} ,{ 6, "abe" },{ 7, "col" } ,{ 8, "ed" },{ 9, "dan" } ,{ 10, "ian" } } },
{ "hope",{ { 1, "gav" },{ 2, "jon" },{ 3, "bob" },{ 4, "abe" },{ 5, "ian" } ,{ 6, "dan" },{ 7, "hal" } ,{ 8, "ed" },{ 9, "col" } ,{ 10, "fred"} } },
{ "ivy" ,{ { 1, "ian" },{ 2, "col" },{ 3, "hal" },{ 4, "gav" },{ 5, "fred"} ,{ 6, "bob" },{ 7, "abe" } ,{ 8, "ed" },{ 9, "jon" } ,{ 10, "dan" } } },
{ "jan" ,{ { 1, "ed" },{ 2, "hal" },{ 3, "gav" },{ 4, "abe" },{ 5, "bob" } ,{ 6, "jon" },{ 7, "col" } ,{ 8, "ian"},{ 9, "fred"} ,{ 10, "dan" } } },
};
stable_marriage sm(males, females);
sm.go();
sm.print_results();
pause();
}Last updated