Fairer Matching for Hospitals and Roommates Comes With a Catch

Every year, hospitals match with medical residents, students with schools, and people with roommates. These decisions are often automated. The goal is a stable match: no pair of people would rather be with each other than who they actually got. But a perfectly stable match can be impossible, especially when someone must be left out. So researchers accept “almost stable” results — meaning a few people might wish they had been matched differently.

How should that mild dissatisfaction be spread? Older methods minimized the total number of complaints. That can be unfair: all the unhappiness might land on just a few unlucky people. The researchers propose a different rule, called minimax: make sure the worst-off person has as few complaints as possible. Instead of reducing the average amount of discomfort, they protect the last person in line.

There is a big catch. The study shows that even deciding if a matching can keep every person’s complaints down to just one is computationally impossible, meaning no fast algorithm can guarantee an answer. That holds even for simple roommate or marriage-style matching problems. The good news: if people only rank two choices, they found a quick solution. For general cases, they offer approximation methods that work well enough in practice.

What does this mean for you? If you’re waiting on a residency match, a school choice, or even an apartment-hunting algorithm, fairness may be limited by math. It is not a reason to distrust every matching system — but it is a clear warning that perfectly fair outcomes come at a hidden cost.