Stable matching problem

The stable matching problem is a fundamental concept in mathematics, economics, and computer science. It involves finding a way to pair elements from two equal-sized sets based on their specific preferences. A matching is a bijection, meaning every element in one set is paired with exactly one element from the other. The goal is to reach a state of stability. A matching is considered unstable if there is a pair of individuals who both prefer each other over their current partners. In a stable matching, no such pair exists, ensuring that no two people have an incentive to abandon their current partners to be together.

To understand the mechanism, consider the Gale–Shapley algorithm, also known as the deferred acceptance algorithm. This process functions through a series of rounds or iterations. In the first round, every unengaged man proposes to the woman he ranks highest on his preference list. Each woman then responds to her suitors. She says "maybe" to the suitor she prefers most and "no" to everyone else. She becomes provisionally engaged to her top choice, and he becomes provisionally engaged to her.

Subsequent rounds follow a specific sequence to refine these pairings. Each unengaged man proposes to the most-preferred woman to whom he has not yet proposed. Even if a woman is already engaged, she must consider the new proposal. A woman will say "maybe" if she is currently unengaged or if she prefers the new man over her current provisional partner. If she prefers the new man, she rejects her current partner, who then becomes unengaged again. This allows participants to "trade up" for better matches. The process continues until every person is successfully engaged.

This algorithm is highly efficient, completing in a time related to the number of participants, $n$. It is guaranteed to produce a stable matching for any equal number of participants. Interestingly, the outcome depends on who initiates the proposals. The Gale–Shapley algorithm always yields the stable matching that is best for all men and worst for all women. For the men, the mechanism is truthful, meaning no man can get a better match by lying about his preferences. However, the algorithm is non-truthful for women, as they may be able to improve their matches by misrepresenting their rankings.

There can be multiple different stable matchings for a single set of preferences. For instance, in a group of three men and three women, one stable solution might give men their first choice while giving women their third. Another solution might result in everyone receiving their second choice. The set of all possible stable matchings forms a structure known as a finite distributive lattice. In a random instance of the problem, the average number of stable matchings grows asymptotically. However, in instances designed to maximize these matches, the number can be an exponential function of $n$.

History shows the deep impact of this mathematical discovery. In 1962, David Gale and Lloyd Shapley proved that a stable matching is always possible for any equal number of participants. Their work laid the foundation for modern market design. This significance was recognized in 2012, when Lloyd S. Shapley and Alvin E. Roth were awarded the Nobel Memorial Prize in Economic Sciences. They were honored for their theories on stable allocations and their practical work in market design.

Real-world applications of stable matching are widespread. One famous use is the assignment of graduating medical students to their first hospital appointments. Another application is the assignment of rabbis from Hebrew Union College to Jewish congregations. In computer science, the client-server model uses these principles. Content delivery networks must balance server traffic while finding servers close to users to reduce loading times. This task resembles a version of the traveling salesman problem.

There are also more complex variations of this problem. The stable roommates problem involves a single pool of participants rather than two distinct classes. The hospitals/residents problem, or college admissions problem, allows one side to have a numerical capacity for multiple matches. Under the rural hospitals theorem, even in these complex cases, the set of assigned doctors and the number of filled positions remain the same in all stable matchings. Other advanced versions include matching with contracts or matching involving couples, which can become NP-complete.