Skip to main content

On Hardness of Matching Problems

The need to establish matching may be as old as mankind itself. People marry each other for companionship and reproduction. International trade brings goods and capital to where they are valued the most. Resources, from seats in the popular Introduction to Wines class to carbon emission quota, need to be allocated judiciously because they’re finite. In fact, matching is so natural to us that it almost happens subconsciously. We sell to the highest bidder and buy from the cheapest seller. We court the most desirable potential mate until we settle down. Perhaps this mentality is the reason why when Gale and Shapley first published their landmark paper, it received little response from the academia or the society.
Since then however, matching market problem became a hot research topic, culminating in Roth and Shapley’s receiving the Nobel Prize in Economics in 2012. Finding a good matching in general turns out to be paramount in every economic activity we partake in, yet is an extremely nontrivial problem.
A natural first step is to define “goodness”, and that alone is no easy task. Assigning a value of “goodness” to each matching sounds promising, but except in markets with transferable utility, where one can quantify their likeness of individual items, it does not work very well: one cannot give a number to the fuzzy feeling of “I prefer A to B.” Pareto efficiency, a concept borrowed from economics, where “goodness” is defined to be the state where nobody can gain without someone else suffering, is tantalizing. However, it is so general that sometimes we find it counterintuitive. For example, if we can improve everybody’s matching by just having one person take a worse assignment, would one consider it an improvement? Pareto says no, but others may find it worthwhile to sacrifice one person for “the greater good.” Pareto efficiency also does not address equality at all. Say, I have two kids and two candy. I can give both of them to my favorite child, or one each. Either way, it will be Pareto efficient, but you will tell me it’s wrong to pick a favorite. In a two-sided market, marriage for example, stability is the standard for good matching. A stable matching means no two unmarried person may run away together because they prefer each other to their current mate. However, Gale-Shapley, the standard algorithm that produces such matching, suffers from a huge flaw: it is possible for participants to lie about their preference so they get more desirable mate. In technical term, the algorithm is not strategy-proof. Once we pile on different requirements for a good matching, we face a grim reality: sometimes, such matching simply does not exist. For example, Roth proved in 1982 that in two-sided markets, it is impossible for an algorithm to be both stable and strategy-proof.
It is important to design the model to accurately reflect the generally accepted notion of “goodness.” Throughout its history, National Residency Matching Program (NRMP), where medical students are matched with residency positions, has been constantly subject to criticism. In the initial version of the algorithm, Students and hospitals that are each other’s first preference was matched together, and then hospitals that ranked the student second while student ranked the hospital first, and so forth. Students then noted that if they are rejected by their first preference, even if their second preference ranked them first, they could still end up in a place they dislike, because their second preference was filled up. NRMP had to change the algorithm to what would later be named Gale-Shapley. Still, the version they used has been found to favor hospitals over applicants, and it is possible for individuals to gain a strategic advantage by lying about their preferences. A new algorithm, which addressed some of its shortcomings, was adopted in May 1997.
Computing the good matching, as it turns out, is not trivial either. Even in the simplest case, for example, the classic Gale-Shapley algorithm, the time needed is proportional to the square of the scale of the problem. That is, when the number of man or woman double, time spent solving the problem increases fourfold. In Computer Science, we say the algorithm’s time complexity is O(n2). To be fair, it is quite fast – until mid-20th century, people need that much time just to sort n numbers. But in real life, the problems tend to be quite large. Suppose we intend to employ Gale-Shapley algorithm to match applicants to colleges. According to College Board, in 2014 there are more than 1.6 millions college-bounds seniors who took the SAT. At that scale, it takes hours, if not days, to compute a matching. Furthermore, some very simple models of matching are computationally intractable. In the maximum matching problem, we match as many men and women whose compatibility is given, as possible. This problem has a relatively efficient algorithm. Now we consider adding another gender, and we need to produce man-woman-other triples. This problem is called 3-dimensional matching, and so far people have not found any efficient algorithm to solve it, i.e. the best-known algorithm’s running time increases exponentially as we scale the problem up.
Finally, real world situation is almost never as simple as the mathematical models may suggest. For example, in NRMP, each hospital may have more than one opening. Couples may want to work at the same place, or at least close to each other. Also we have second-year students in the matching. All these factors should be taken into account when designing the model. Then, one must take utmost care to reconcile these sometimes-incompatible goals.
Matching theory is powerful, and it directly impacts many aspects of our life, from which dorm we live in, to whom we spend the rest of our lives with. Yet as we see, to successfully turn theory in practice, one must be careful to determine goal, weigh priorities, and carefully design a model that both encode our input data necessary as well as being computationally tractable within the budget. Practitioners should keep these in mind.

Roth, A. E. The Economics of Matching: Stability and Incentives. Mathematics of Operations Research. 1982,7.
Roth, A. E. The Origins, History, and Design of the Resident Match. JAMA: The Journal of the American Medical Association. 2003,7.
Roth, A.E; Peranson, E. The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design. The American Economic Review. 1999,89.


Leave a Reply

You must be logged in to post a comment.