Does ‘Perfect Match’ Actually Lead to Perfect Matching? – Matching Algorithm Created by Cornellians
In February 2019, a group of Cornell students came up with a matchmaking quiz to pair students with potential ‘perfect matches’. The algorithm does this in two steps:
First, they score your compatibility with other students based on a range of interests and topics, such as politics, hobbies and qualities one looks for in a partner.
Then, the algorithm generates a list of optimal perfect matches according to this criteria.
This is a perfect example of matching markets, and creating a perfect matching. What this algorithm attempts to do is create a matching where each node (student) is matched with another node (student). This way it tries to ensure that there is no student who is left without a matching.
However, this system does not actually lead to what would be a perfect matching. As we talked about in class, a perfect matching is created when:
- Each node is connected by an edge to another node
- No two nodes on the left are connected to the same one on the right
Let’s consider what happens when the results of ‘Perfect Match’ come in. Instead of matching each student with one potential match, it actually matches each student to 4 to 7 matches. So while no student is left without a match, they actually end up with too many matches.
What would this lead to? Well, say we have a group of 4 students on the left and 4 students on the right. If student A on the right has four potential matches, who are all on the left, this will mean student A will have 4 edges connecting them to the left. Let’s also say that students 1 and 3 were also matched with B, C and D.
Furthermore, let’s say the students have valuations for their matches, and they rank them from who they like best to who they like least. It may even be possible that students only like one of their matches, and do not want to consider the rest of them. So if students 1, 2, 3 and 4 all value student A at a value of 10, and the rest of their matches at 0, then this would form a constricted set and a perfect matching would never be possible.
Furthermore, if student B values student 1 as their best match and does not want anyone else, and student C values student 3 as their best match and does not want anyone else, they will not be happy being matched with anybody else. Furthermore, even if D is neutral between 1 and 3, neither 1 or 3 want to be matched with D.
A and 1 would end up together, but no one else would get the matching that they wanted.
Hence, the ‘Perfect Match’ algorithm could leave multiple students not having a perfect match at all!
Source: https://perfectmatch.ai/