7
$\begingroup$

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?.

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? and did not find anything that would do the job.

Improve this question
$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – ml0105
    Commented Mar 24, 2016 at 22:50
  • 2
    $\begingroup$ @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). $\endgroup$
    – Martin Van der Linden
    Commented Mar 25, 2016 at 2:22
  • $\begingroup$ I stand corrected (and apologize for misinformation!) $\endgroup$
    – ml0105
    Commented Mar 25, 2016 at 4:19

2 Answers 2

Reset to default
2
$\begingroup$

The 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 (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.

Improve this answer
$\endgroup$
2
$\begingroup$

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 is a little tutorial for Mac OS, which worked for me as of today.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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