Stable matching problem

Imagine two groups of people.

Each person has a list. They list who they like best. We want to find a fair match. A match is stable when no two people want to switch.

This can be a hard puzzle. Two men, Lloyd Shapley and Alvin Roth, won a prize for this work. They helped find ways to match people.

This helps in the real world. It helps new doctors find hospital jobs. It can even help assign rabbis to groups.

Finding these matches keeps things fair for everyone. It is a smart way to solve big problems.

Imagine two groups of people. Each person has a list of who they like best. We want to pair them up. A matching is stable if no two people want to switch. This means no two people would rather be with each other than their current partner.

In 1962, David Gale and Lloyd Shapley found a way to solve this. They made a set of steps called the Gale-Shapley algorithm. In this way, people propose to their favorite choice. The other person says "maybe" or "no." This repeats in rounds. It continues until everyone has a partner. This method always finds a stable match.

This math helps in the real world. It helps match new doctors to hospitals. It also helps assign rabbis to groups. Even computer networks use these ideas. They use them to send data to users quickly. Lloyd Shapley and Alvin Roth won a Nobel Prize for this work. They studied how to design these markets. They showed how to make stable matches for many people.

Imagine two groups of people trying to find the best partners. Each person has a list of who they like most. We want to create a matching where everyone is paired up. A matching is called stable if no two people want to switch. This means you cannot find a pair who both prefer each other over their current partners. If such a pair existed, the matching would be unstable.

In 1962, David Gale and Lloyd Shapley found a way to solve this. They created the Gale-Shapley algorithm to find stable matches. This method works in several rounds of proposals. First, each unengaged person proposes to their favorite choice. The other person says "maybe" or "no." If they say "maybe," they are provisionally engaged. In the next round, people propose to their next choice. A person can "trade up" if a better partner says "maybe."

This math is used for many important jobs in the real world. It helps match graduating medical students to their first hospital jobs. It is also used to assign rabbis to Jewish congregations. Even computer networks use these ideas to work well. They use it to send data to users as fast as possible. This helps reduce the time it takes for pages to load.

There are many different ways to have a stable matching. For example, three men and three women might have different lists. One stable match might give men their first choice. Another stable match might give women their first choice instead. In some cases, everyone might get their second choice. The number of stable matches can change based on the lists.

Math experts have studied these patterns for a long time. Lloyd Shapley and Alvin Roth won a Nobel Prize in 2012. They were honored for their work in market design. They studied how to make stable allocations for many people. There are even harder versions of this problem to solve. One version involves matching doctors to hospitals with different capacities.

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.