The musical Fiddler on the Roof takes place in a small Jewish village in Imperial Russia. Its residents (cast-members) hold specialized employment. Yente is the "matchmaker," taking pride in her ability to arrange successful marriages through the wonders of song and dance. In the inexorable march of technological progress since the early 20th century, matchmaking has since been streamlined and automated.
The Stable Marriage Problem
Suppose there are bachelors (men), all of whom would like to marry a woman, and bachelorettes (women), all of whom would like to marry a man (excuse the heteronormativity, this problem was formulated at a less inclusive point in history). They come to you, the matchmaker, and ask you to pair them up. There’s just one problem: you don’t know anything about them.
To remedy this, each person gives you a list of partial rank-ordered preferences. Each man "ranks" the women based on who he would like to marry, most to least, and each woman does the same. The lists don’t have to be complete—some of the women may be left off a man’s list, and vice versa. Anyone left off a list is assumed to be "unacceptable" for the list-maker (they would prefer to remain single than be matched to them). The lists must, however, be strictly ordered—no one is allowed to be indifferent between two partners.
For the matches you make, they expect none to be unacceptable (no one is matched with someone they didn’t put on their list), and all to be "stable." Stable, in this case, means that no two people wish to break away from their assigned matches and "elope" with each other. (Both of these conditions will become clearer in the example). Let’s do some matching!
The Deferred Acceptance Algorithm (Gale and Shapley, 1962)
Once we have our preference lists in order, the algorithm works as follows:
Step 1: Pick one of the two sides (either men or women) as the "proposing side" (this has some strategic implications, but we won’t worry about that). Let’s assume women are proposing to men.
Step 2: In the first round, have each woman "propose" to their top choice.
Step 3: For each of the men, there will be one of three scenarios:
- They receive no proposals, in which case they do nothing
- They receive one proposal they find acceptable and (tentatively) accept it
- They receive multiple proposals, in which case they (tentatively) accept whichever one is the most desirable, and reject the others
Step 4: In the next round, everyone who was rejected initially proposes to their second choice. This works as before, except now some of the men may have already tentatively accepted a proposal from someone else. In this case, the man compares his new proposals with the one he’s accepted and sees which he prefers. He tentatively accepts his best offer and rejects everyone else.
Step 5: In each subsequent round, women who were rejected in the previous round propose to their top choice among men they haven’t already proposed to.
Step 6: The procedure ends once there’s a round where no one gets rejected. The result is the final (stable) matching.
Intuitively, the algorithm works by letting everyone iterate to find their “best” option. The proposing side (in this case, the women), go down in order of their preferences, meaning that if they end up matched with their nth choice, their 1st through n-1th choices must have already rejected them in favor of someone they liked more.
An Example
Consider a situation with three men (Andy, Bill, and Carl), and three women (Ally, Brie, and Cat). Below are everyone’s preferences:
For clarity, the chart is saying that Andy’s first choice is Ally, his second choice Brie, and his third choice Cat, while Bill prefers Ally to Cat to Brie, etc.
First, let’s see what happens if we don’t use the algorithm. Let’s pair them up as follows:
{(Andy, Brie), (Bill, Cat), (Carl, Ally)}
At first, these look fine—every man is with one woman, and no one is paired with someone not on their list. But notice that Andy likes Ally more than Brie (his assigned match), and Ally likes Andy more than Carl (her assigned match). Thus, both Andy and Ally would be better off by breaking away from their matches and getting with each other. This is what’s known as a "blocking pair," and renders our assignment unstable.
Now let’s see what happens when we run deferred acceptance:
In the first round, Ally proposes to Andy, and Brie and Cat both propose to Carl. Andy accepts Ally’s offer, while Carl (who prefers Brie to Cat), rejects Cat.
In the second round, Cat (the only person rejected), goes to her second choice, Andy. Andy prefers Ally (his current match) to Cat, and thus rejects Cat.
In the third round, Cat proposes to her third choice, Bill, who accepts her.
Our final matches are {(Andy, Ally), (Bill, Cat), (Carl, Brie)}.
Here are the steps represented in a table:
Huzzah, a stable matching! (Curtains fall, the audience breaks out in fervent applause)
Applications
Matching algorithms like Gale-Shapley are central to market design and have many real-world applications. Generally, when optimal allocations are in question, the economic solution is to create a market with a medium of exchange (money) and a signal of scarcity (prices). However, certain situations like marriage or organ donation preclude the use of traditional markets, either for ethical and legal reasons, or because it would be weird. Thus, "priceless" algorithms like deferred acceptance are deployed to make matches equitably.
References
Gale, D., and L. S. Shapley. “College Admissions and the Stability of Marriage.” The American Mathematical Monthly, vol. 69, no. 1, 1962, pp. 9–15. JSTOR, https://doi.org/10.2307/2312726. Accessed 5 July 2024.
Comments