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:

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 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, 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

namespace {
    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();
}