<p>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 <em>intervals</em>, 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 <a href="http://arxiv.org/abs/1208.2721">this paper</a>.
Subramanian's approach was later elaborated by Feder.</p>

CC BY-SA 3.0
2014-08-07T01:58:34.650Z
2014-08-07T01:58:34.650Z
Yuval Filmus
<p>Yes, there is a polynomial-time algorithm to find any stable matching.</p>

<p>Understanding the algorithm requires you to study a <em>rotation poset</em>.  One of the good materials to learn the rotation poset is this book.</p>

<p><a href="http://mitpress.mit.edu/books/stable-marriage-problem/">Dan Gusfield, Robert W. Irving: The Stable marriage problem - structure and algorithms. Foundations of computing series, MIT Press 1989</a></p>

CC BY-SA 3.0
2014-08-06T14:12:46.413Z
2014-08-06T14:12:46.413Z
Hiroki Yanagisawa
<p>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 ("<a href="http://cgm.cs.mcgill.ca/~avis/courses/360/2013/ktlaerid/LP-bliss.pdf" rel="nofollow">Linear Programming Brings Marital Bliss</a>"), or Vohra 12 for a different treatment ("<a href="http://www.currentscience.ac.in/Volumes/103/09/1051.pdf" rel="nofollow">Stable Matchings and Linear Programming</a>")</p>

CC BY-SA 3.0
2014-08-07T11:47:55.303Z
2014-08-07T11:47:55.303Z
Aaron Roth
<p>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?</p>

CC BY-SA 3.0
2014-08-06T14:56:57.067Z
This seems a little vague without specifying what properties you would hope an additional algorithm to have.
Huck Bennett
CC BY-SA 3.0
2014-08-18T13:14:32.357Z
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...
someone
<matching><stable>
Another algorithm for stable matching?
someone
# Another algorithm for stable matching?

(Asked by: username_0 on 2014-08-05)

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?

**Tags:** matching, stable

> **Comments:**
> **username_1**: This seems a little vague without specifying what properties you would hope an additional algorithm to have.  
> **username_0**: 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...  

---

## 3 answers

### Answer by username_2 on 2014-08-07. Score: 7

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](http://arxiv.org/abs/1208.2721).
Subramanian's approach was later elaborated by Feder.


---

### Answer by username_3 on 2014-08-06. Score: 6

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.

[Dan Gusfield, Robert W. Irving: The Stable marriage problem - structure and algorithms. Foundations of computing series, MIT Press 1989](http://mitpress.mit.edu/books/stable-marriage-problem/)


---

### Answer by username_4 on 2014-08-07. Score: 4

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](http://cgm.cs.mcgill.ca/~avis/courses/360/2013/ktlaerid/LP-bliss.pdf)"), or Vohra 12 for a different treatment ("[Stable Matchings and Linear Programming](http://www.currentscience.ac.in/Volumes/103/09/1051.pdf)")


---

