Sunday, April 16, 2017
Matchmaking how does it work
Matchmaking how does it work
Imagine that you have four daughters and you want to marry them. You carefully select four guys and let each of your daughters spend some time with each guy. Then all the daughters and all the guys mark their potential partners in the order of their priorities. How do you use this ranking to match your daughters to the guys to create four stable couples? Couple is considered stable if each of your daughters is happy with her partner and she wouldnt rather be with some other guy who simultaneously also prefers her to his current match.
Or take another matching game. Four medical residents need to be matched to work in the hospitals. Each of the residents spent some time practicing at each of the four hospitals in the program. Then all the residents and all the hospitals mark each other in the order of their preferences. Your task is to use this rating to create a satisfactory match, sending one resident to each of the four hospitals. Each resident should be sent to a hospital where he is happy. It may not necessarily be her or his first choice but there should be no other hospital that he would rather be at that simultaneously also wants him more than the current resident you sent there.
Try playing such match-making and when you are done, watch this video. Click to see Harvard Postdoc Emily Riehl explains the optimal matchmaking algorithm for such situations. You can share this with your 10+ year old kids.
You can also see the explanation of the same algorithm applied to the National Resident Matching Problem via this link.
Note that while this algorithm is simple and is always guaranteed to converge to the optimal result, the algorithm is not symmetric. The optimal solution for girls is different than the optimal solution for boys, and optimal solution for residents differs from the optimal solution for hospitals.
Top image by imaekelley, distributed under CCL.
Or take another matching game. Four medical residents need to be matched to work in the hospitals. Each of the residents spent some time practicing at each of the four hospitals in the program. Then all the residents and all the hospitals mark each other in the order of their preferences. Your task is to use this rating to create a satisfactory match, sending one resident to each of the four hospitals. Each resident should be sent to a hospital where he is happy. It may not necessarily be her or his first choice but there should be no other hospital that he would rather be at that simultaneously also wants him more than the current resident you sent there.
Try playing such match-making and when you are done, watch this video. Click to see Harvard Postdoc Emily Riehl explains the optimal matchmaking algorithm for such situations. You can share this with your 10+ year old kids.
You can also see the explanation of the same algorithm applied to the National Resident Matching Problem via this link.
Note that while this algorithm is simple and is always guaranteed to converge to the optimal result, the algorithm is not symmetric. The optimal solution for girls is different than the optimal solution for boys, and optimal solution for residents differs from the optimal solution for hospitals.
Top image by imaekelley, distributed under CCL.
Available link for download
