# Gale-Shapley Follow-up Literature and General Questions

The Gale-Shapley Algorithm is a way of matchmaking between two different entities of people. It guarantees that every individual player is matched and that the matches are stable.

What sort of literature has been done building off of this? How does social welfare change when the two entities do not have the same number of individuals in them, so that not everyone can be matched? Are there faster ways to match individuals with each other (lower runtime)? And most importantly, what sort of applications does the Gale-Shapley algorithm have in economics?

It seems like a very weird game theoretic model just because when I read the proof for the validity of the algorithm, it seems like the problem is "discrete"; that is, optimizing who gets matched with who and finding a Pareto efficient result can't be solved through maximizing a continuous function.

As a side question, is the Gale-Shapley allocation Pareto efficient?

• Gale-Shapley is used in university admission procedures and kidney exchanges. The allocation is Pareto-efficient, because it is stable. I am afraid I don't understand the part of your question about discreteness. Commented Nov 6, 2015 at 20:38
• That part wasn't so much a question as a comment anyway. Commented Nov 6, 2015 at 21:58
• @denesp Actually, I'm pretty sure the Top-Trading Cycle Procedure is used in organ donations. Commented Nov 7, 2015 at 8:33
• @KitsuneCavalry For future reference: This site is best set up for one question per question (i.e., one thread per question). There is no downside to posting 2-3 questions on the same subject at the same time, if answering one doesn't make the others redundant. Commented Nov 7, 2015 at 10:21
• @ml0105 You are correct, I mixed up the two algorithms. Commented Nov 7, 2015 at 12:26

How does social welfare change when the two entities do not have the same number of individuals in them, so that not everyone can be matched?

The algorithm works fine in this case. The important assumption is still that the underlying graph is bipartite (and that preferences are transitive). If we allow for members of a given type to propose to each other, then we lose convergence. Suppose we have three players: $A, B, C$. We have $A$'s preferences as $(B, C, A)$; $B$'s preferences as $(C, A, B)$; and $C$'s preferences as $(A, B, C)$. So $A$ proposes to $B$, which accepts. Then $B$ proposes to $C$, which accepts. This unmatches $A$. Next, $C$ proposes to $A$, which accepts. This unmatches $B$. We then repeat.

Are there faster ways to match individuals with each other (lower runtime?)

Gale-Shapley has a runtime complexity of $\Theta(n^{2})$. In graph theory, most bipartite matching algorithms take $\Omega(|E| \sqrt{|V|})$ time. In the worst case, $|E| = |V|^{2}/4$. So I wouldn't bank on much better.

Additionally, this isn't a problem that lends itself well to a divide and conquer approach. It's really a greedy problem. You might be able to get the expected runtime down by selecting a random ordering for proposing. The analysis would be involved though.

It seems like a very weird game theoretic model just because when I read the proof for the validity of the algorithm, it doesn't seem like the problem is "discrete"; that is, optimizing who gets matched with who and finding a Pareto efficient result can't be solved through maximizing a continuous function.

Actually, it's a discrete model. In more traditional fields of economics, we have continuous variables. So linear programming makes sense. We could actually formulate an integer-linear program for the stable-marriage problem if we look at it from a graph theoretic perspective. Matching problems can be formulated in the language of flows. And we can write flow problems as LPs. The flow constraints form a convex polytope. If the graph is bipartite, the vertices of the polytope are the matchings. The trick here is that we have to add additional constraints to ensure we end up with the correct matching (since the matching from the Gale-Shapley algorithm is unique, regardless of the order in which the men propose).

Even if we go to the trouble of formulating the linear program, solving an LP for this problem by hand or by a computer is less efficient than using the algorithm.

(As a side question, is the Gale-Shapley allocation Pareto efficient?)

The matching generated by the Gale-Shapely algorithm is in the core. An imputation belonging to the core satisfies the property that no coalition can collude their initial endowments and improve its members' outcomes. An imputation is Pareto optimal if no set of agents can improve their outcomes without another player's outcome being less favorable. So core allocations are Pareto optimal.

For more on Gale-Shapley, check out my blog: https://michaellevet.wordpress.com/2015/05/22/algorithmic-game-theory-stable-marriage-problem/

• Wow I somehow meant to ask why the model DID seem discrete, oops. Thank you for addressing that. Commented Nov 7, 2015 at 16:39

This is a very old question but I just want to add a few notes not covered in ml0105's great answer.

1. What sort of literature has been done building off of this? ... What sort of applications does the Gale-Shapley algorithm have in economics?

The most practical application is school matching. Thousands of school districts around the world assign new students to schools every spring and they use some algorithm to make these assignments. In the US, it's known as "school lottery", but in many cases, the actual algorithms used are variations of Gale-Shapley's deferred acceptance algorithm. This is because students' preference lists and school priorities resemble the preference lists of men and women in Gale-Shapley's setting. A relevant literature (and thousands of papers that spawned from it) is Abdulkadiroğlu, A., & Sönmez, T. (2003). School choice: A mechanism design approach. American economic review, 93(3), 729-747.

Another practical example is the National Resident Matching Program. Students coming out of med schools must do residency at hospitals before becoming doctors. An algorithm assigns them to hospitals. This algorithm (at least the one used in the US) is one based on Gale-Shapley's deferred acceptance algorithm. A relevant literature is Roth, A. E., & Peranson, E. (1999). The redesign of the matching market for American physicians: Some engineering aspects of economic design. American economic review, 89(4), 748-780.

2. How does social welfare change when the two entities do not have the same number of individuals in them, so that not everyone can be matched?

Being unmatched is a valid outcome. If there are 3 men and 2 women, one man will bound to be unmatched but as long as that man cannot form a blocking pair with a woman, the resulting matching is stable.

3. Optimizing who gets matched with who and finding a Pareto efficient result can't be solved through maximizing a continuous function.

While Gale-Shapley defines a discrete problem, we can also define an equivalent linear programming problem. The optimal solution of that LP will be either the men-optimal stable matching or the women-stable stable matching. A relevant literature is Vate, J. H. V. (1989). Linear programming brings marital bliss. Operations Research Letters, 8(3), 147-153.

4. As a side question, is the Gale-Shapley allocation Pareto efficient?

Because preferences are strict in Gale-Shapley, this can be proved to be true by proving that Pareto inefficient allocations are not stable.

Suppose the Gale-Shapley allocation $$\mu$$ is not Pareto efficient. Then there is an allocation $$\nu$$ where one person is strictly better off and no other person is worse off. If that person is unilaterally better off while everybody else is with their match, then $$\mu$$ was individually irrational, contradicting stability. If a man is strictly better off with a woman $$w$$ who is different from the one assigned to him by $$\mu$$, then since $$w$$ has strict preferences, $$w$$ prefers this man more than her match at $$\mu$$. Thus this couple becomes a blocking pair, contradicting stability.