Stable Marriage Algorithm

So, matching people up based on preferences, sounds easy right?

Imagine this scenario: We have two groups, we are going to match them up based on characteristics/preference.

Group1 = [‘andy’, ‘david’, ‘victoria’];

Group2 = [‘jae’, ‘jasmine’, ‘travis’] ;

people’s preferences

How do we find the highest utility? Andy would prefer to be with jae, but jae prefers victoria, but victoria prefers jasmine, but jasmine prefers david, but david prefers jae, and nobody fancies Travis!

One option is to use ‘brute force,’ just try all the possible options and pick the one with the highest utility.

This would work, but the number of possible outcomes explodes as the group gets larger.

This is a choose k of n permutation problem where k and n are both equal to three.

number of possible choices = n! / (n-k)! → 3! = 6

but what about matching 30 students with thirty mentors?

30! = 2.6 * 10^32

To give you some perspective, that’s more than the estimated number of stars in the entire observable universe.

okay, so brute force is out, what else is there?

Enter the stable marriage algorithm. Forgive the sexism, this algorithm was developed in 1962.

The two groups are husbands and wives. Husbands and wives want to get the best partner possible. The main points are that the wives are agnostic, they will say yes to whomever asks them as long as the person asking is better than their current partner. Wives are also not shy about dumping their match if something better comes along.

So code..well pseudo code or is it Sudo Code… it should be Sudo Code

While there are unmatched husbands, loop through the husband array
    When you find a husband who isn’t matched, find his best match        who will say yes
         Somebody who is unmatched will always say yes
         Somebody who is matched will say yes to somebody who is a better match
    If the wife is not matched, match the two and move on to the next unmatched husband
    Else If the wife is matched and will say yes, mark her existing match as unmatched and match the wife with the new husband.

As long as there at least as many wives as husbands, all the husbands will find a match.

How would this work in our situation:

Andy matches with Jae

David chooses Jae and Jae prefers david

Andy is no longer matched

David and Jae are matched

Victoria matches with jasmine

Andy matches with jasmine and jasmine prefers andy to victoria

Victoria is no longer matched and andy and jasmine are matched

Victoria matches with Travis

This isn’t necessarily the optimal outcome, but it is ‘stable’ in that you cannot switch any two people and get a higher overall utility.