The only algorithm I have seen to compute a stable matching is the one by Gale an Shapley. Is there any other algorithm to compute a stable matching?
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ This seems a little vague without specifying what properties you would hope an additional algorithm to have. $\endgroup$– Huck BennettAug 6, 2014 at 14:56
-
$\begingroup$ I was not looking for any particular property. Thanks for the answers below. I will look into them. It is a bit unfair to select an answer, so after checking the provided references, I may end up flipping a coin to select a random correct answer... $\endgroup$– someoneAug 18, 2014 at 13:14
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
There is a totally different algorithm due to Subramanian which uses a fixed point approach. The first idea is to represent the knowledge that we have at any given point in time using intervals, which represent which women each man is considering, and vice versa. Using ideas similar to Gale-Shapley, we keep shrinking the intervals. In contrast to Gale-Shapley, this algorithm is symmetric with respect to gender. Eventually a fixed point is reached, and we can read the man-optimal and woman-optimal matchings. Subramanian found a neat way to implement this using three-valued logic and comparator networks. Check out for example this paper. Subramanian's approach was later elaborated by Feder.
answered Aug 7, 2014 at 1:58
$\begingroup$
$\endgroup$
Yes, there is a polynomial-time algorithm to find any stable matching.
Understanding the algorithm requires you to study a rotation poset. One of the good materials to learn the rotation poset is this book.
$\begingroup$
$\endgroup$
There is also a small set of linear constraints that form a polytope whose extreme points are the stable matchings. This allows you to find a stable matching optimizing any linear objective using linear programming. See Vande-Vate 89 ("Linear Programming Brings Marital Bliss"), or Vohra 12 for a different treatment ("Stable Matchings and Linear Programming")
answered Aug 7, 2014 at 11:47