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’] ;
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.