How College Admissions is like Online Dating
In our class, we have learned different procedures to achieve matching in different contexts: Search queries and page rank, sellers and buyers, auctions, bipartite graphs with constricted sets. But what does this look like in online dating, which is basically matching (There is a site literally called Match!)? Everyone generally knows that Hinge stands out from the many online dating apps and services for its distinctive interface and user experience. And many also might know at least one person in their lives who has had success on Hinge- in other words, found a significant other. They are the lucky ones, or are they? It turns out that Hinge’s effectiveness can be attributed to a Nobel Prize winning algorithm called the Gale-Shapley algorithm. The algorithm addresses the stable matching problem, which is also called the stable marriage problem. There are two groups of equal size who have their own preferences and will be matched accordingly such that everyone is partnered and every matching is stable. Now in the real world, this sounds really unlikely: Everyone is different, everyone is particular, and millions of people use Hinge, which means unstable matchings must be very common, and stable matchings are rare. An unstable matching occurs when a member of one group is matched to another but prefers someone else in the other group, and that person must also feel the same way. Gale and Shapley’s algorithm solves this problem by running multiple iterations:
Suppose there are two groups of eligible singles, A and B. In the first round, have each member of A propose, or send a like, to a member of B he/she prefers. B can say maybe to person A they most prefer and no to all the other suitors. Now these people are “provisionally” engaged, or “matched”. In the following rounds, members of A will propose to members of B they most prefer and have not yet proposed to. It does not matter if person A proposes to a person B who is already engaged to or “matched” with someone else. Members of B will again reply maybe to the person they are currently engaged to or if they prefer the new person who proposed to them, they can break up with their current partner and say maybe to the new person. Now their partner is single, and the whole process will repeat until everyone is matched to the person he/she most prefers. But of course, not every person is going to signal to someone that he/she is interested in him/her, so this brings strategies into the picture and raises the question: do both groups “win” equally. As it turns out, Gale and Shapley’s algorithm as just described produces the matchings that are best for group A but worst for group B. Whoever is doing the proposing gets the best value. Moreover, the proposing group’s strategy is truthful (there is no benefit to lying about preferences), but the receiving group can lie about their preferences and end up in a better match for them.
So in Hinge, everyone is reviewing each other’s profiles and sending likes, which Hinge learns from and adapts by showing people who match their tastes. College admissions and resident matching are also closely related to the stable matching problem, except universities and hospitals can take more than one student. Students apply to colleges, focusing on their top choices, which they can either waitlist or reject. Students who have not yet been waitlisted by a college continue to apply to their target schools and/or safety schools. This will also repeat until every student has applied and been matched to a college they are willing to go to. This sounds a lot like the existence procedure, except there are no prices, and one could say that there are students, colleges, or singles who are realistically left out. Regardless, in this ever growing world, don’t lose hope! It’s already been proven that everyone will find their special someone.
Sources:
https://thetab.com/uk/2020/05/20/this-is-how-the-nobel-prize-winning-hinge-algorithm-actually-works-157740
https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley_algorithm