8
$\begingroup$

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 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. (As a side question, is the Gale-Shapley allocation Pareto efficient?)

Edit I meant to say, in the second paragraph, "it seems like the problem IS "discrete". So my apologies there.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Giskard Nov 6 '15 at 20:38
  • $\begingroup$ That part wasn't so much a question as a comment anyway. $\endgroup$ – Kitsune Cavalry Nov 6 '15 at 21:58
  • $\begingroup$ @denesp Actually, I'm pretty sure the Top-Trading Cycle Procedure is used in organ donations. $\endgroup$ – ml0105 Nov 7 '15 at 8:33
  • $\begingroup$ @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. $\endgroup$ – FooBar Nov 7 '15 at 10:21
  • $\begingroup$ @ml0105 You are correct, I mixed up the two algorithms. $\endgroup$ – Giskard Nov 7 '15 at 12:26
7
$\begingroup$

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/

$\endgroup$
  • $\begingroup$ Wow I somehow meant to ask why the model DID seem discrete, oops. Thank you for addressing that. $\endgroup$ – Kitsune Cavalry Nov 7 '15 at 16:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.