# 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. ## English-Code :: Gale-Shapely Algorithm: 1. Have each man propose the his first preference. 2. Have each women select her most preferred option from the from the current set of proposals, breaking a current engagement if necessary. 1. 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. 3. 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 Males and Females ``` abe, bob, col, dan, ed, fred, gav, hal, ian, jon abi, bea, cath, dee, eve, fay, gay, hope, ivy, jan ``` Rankings ``` 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, dan ``` ```cpp namespace { typedef unordered_map> cur_pref; typedef unordered_map> pref; typedef unordered_map> 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 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> 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(); } ``` --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://maksimdan.gitbook.io/ecs122a-algorithm-design-lecture-notes/chapter1.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.