<p>The <a href="https://github.com/thiloklein/matchingMarkets" rel="nofollow">matchingMarkets</a> package in the R software now implements two constraint encoding functions to find <strong>all stable matchings</strong> in the three most common matching problems: </p>

<ul>
<li><p><code>hri</code>: <a href="http://matchingmarkets.org/reference.html" rel="nofollow">college admissions problem</a> (including the student and college-optimal matchings) and stable marriage problem (including men and women-optimal matching)</p></li>
<li><p><code>sri</code>: stable roommates problem. </p></li>
</ul>

<p>What's more, it also allows for <strong>incomplete preference lists</strong> (some agents find certain agents unacceptable) and <strong>unbalanced instances</strong> (unequal number of agents on both sides) for all three problems.</p>

<p>If you use Python, you can run R code using <code>rpy2</code>.</p>

CC BY-SA 3.0
2016-09-01T16:04:35.797Z
2016-10-06T18:51:34.057Z
2016-10-06T18:51:34.057Z
kleindotuk
<p>Patrick Prosser has some great java code at <a href="http://www.dcs.gla.ac.uk/~pat/roommates/distribution/" rel="nofollow">http://www.dcs.gla.ac.uk/~pat/roommates/distribution/</a> which, among other things, can compute <em>all</em> the stable matchings in roommate problems.</p>

<p>The code is for roommates problems, but Patrick's code allows preferences over roommates to include unacceptable roommates. To implement a two-sided market, just make sure any roommates on one side of the market views any other roommate on the same side of the market as unacceptable, and you're good to go.</p>

<p>If (like myself) you are not used to java, you might struggle a little to get the code working. <a href="https://martinvdlinden.wordpress.com/2016/04/01/finding-all-stable-matchings-in-roommate-and-marriage-problems/" rel="nofollow">Here</a> is a little tutorial for Mac OS, which worked for me as of today.</p>

CC BY-SA 3.0
2016-04-01T17:55:44.803Z
2016-04-01T17:55:44.803Z
Martin Van der Linden
<p>Do you know of any publicly available code in python or R (or any other free high level language) that returns <strong>all</strong> the stable matchings for any one-to-one matching problem?</p>

<hr>

<p><strong>Note</strong>: This is related but different from <a href="https://economics.stackexchange.com/questions/1638/available-code-for-computing-solutions-to-matching-algorithms">Available code for computing solutions to matching algorithms?</a>. </p>

<p>In this other question, I asked for code implementing famous mechanisms such as the deferred acceptance mechanism. Some of these mechanisms find <strong>one</strong> stable matching among others. Here I am looking for code that finds <strong>all</strong> stable matchings.</p>

<p>I have inspected the packages recommended in the answers I got to <a href="https://economics.stackexchange.com/questions/1638/available-code-for-computing-solutions-to-matching-algorithms">Available code for computing solutions to matching algorithms?</a> and did not find anything that would do the job.</p>

CC BY-SA 3.0
2016-03-24T22:50:39.083Z
In a bipartite matching setting, there are only two stable matchings- the proposer optimal stable matching and the acceptor optimal stable matching. Running Gale-Shapley for both cases will yield the desired result.
ml0105
CC BY-SA 3.0
2016-03-25T02:22:23.540Z
@ml0105 : We must not have the same model in mind. In the bipartite matching setting I have in mind (the one from Gale and Shapley's original 1962 paper), there can be a large number of stable matchings (and a lot has been written about them, notably about their lattice structure when paired with the appropriate binary relation). For a simple example, look for instance at Example 3.7 in Klaus, B., & Klijn, F. (2006). "Median Stable Matching for College Admissions" which features 3 stable matchings (sorry if you can't access it, I wanted to reproduce it here but it's too long for a comment).
Martin Van der Linden
CC BY-SA 3.0
2016-03-25T04:19:31.307Z
I stand corrected (and apologize for misinformation!)
ml0105
<mechanism-design><r><algorithms><python><matching>
Code finding all stable matchings in one-to-one problem
Martin Van der Linden
# Code finding all stable matchings in one-to-one problem

(Asked by: username_0 on 2016-03-24)

Do you know of any publicly available code in python or R (or any other free high level language) that returns **all** the stable matchings for any one-to-one matching problem?

---

**Note**: This is related but different from [Available code for computing solutions to matching algorithms?](https://economics.stackexchange.com/questions/1638/available-code-for-computing-solutions-to-matching-algorithms).

In this other question, I asked for code implementing famous mechanisms such as the deferred acceptance mechanism. Some of these mechanisms find **one** stable matching among others. Here I am looking for code that finds **all** stable matchings.

I have inspected the packages recommended in the answers I got to [Available code for computing solutions to matching algorithms?](https://economics.stackexchange.com/questions/1638/available-code-for-computing-solutions-to-matching-algorithms) and did not find anything that would do the job.

**Tags:** mechanism-design, r, algorithms, python, matching

> **Comments:**
> **username_1**: In a bipartite matching setting, there are only two stable matchings- the proposer optimal stable matching and the acceptor optimal stable matching. Running Gale-Shapley for both cases will yield the desired result.  
> **username_0**: @username_1 : We must not have the same model in mind. In the bipartite matching setting I have in mind (the one from Gale and Shapley's original 1962 paper), there can be a large number of stable matchings (and a lot has been written about them, notably about their lattice structure when paired with the appropriate binary relation). For a simple example, look for instance at Example 3.7 in Klaus, B., & Klijn, F. (2006). "Median Stable Matching for College Admissions" which features 3 stable matchings (sorry if you can't access it, I wanted to reproduce it here but it's too long for a comment).  
> **username_1**: I stand corrected (and apologize for misinformation!)  

---

## 2 answers

### Answer by username_2 on 2016-09-01. Score: 2 | Accepted answer

The [matchingMarkets](https://github.com/thiloklein/matchingMarkets) package in the R software now implements two constraint encoding functions to find **all stable matchings** in the three most common matching problems:

* `hri`: [college admissions problem](http://matchingmarkets.org/reference.html) (including the student and college-optimal matchings) and stable marriage problem (including men and women-optimal matching)
* `sri`: stable roommates problem.

What's more, it also allows for **incomplete preference lists** (some agents find certain agents unacceptable) and **unbalanced instances** (unequal number of agents on both sides) for all three problems.

If you use Python, you can run R code using `rpy2`.


---

### Answer by username_0 on 2016-04-01. Score: 2

Patrick Prosser has some great java code at <http://www.dcs.gla.ac.uk/~pat/roommates/distribution/> which, among other things, can compute *all* the stable matchings in roommate problems.

The code is for roommates problems, but Patrick's code allows preferences over roommates to include unacceptable roommates. To implement a two-sided market, just make sure any roommates on one side of the market views any other roommate on the same side of the market as unacceptable, and you're good to go.

If (like myself) you are not used to java, you might struggle a little to get the code working. [Here](https://martinvdlinden.wordpress.com/2016/04/01/finding-all-stable-matchings-in-roommate-and-marriage-problems/) is a little tutorial for Mac OS, which worked for me as of today.


---

