<p>I know this is a bit out of date, but there is a new package available on CRAN now called 'matchingR' which I believe is much faster than the package recommended above. You can install it with </p>

<p><code>install.packages('matchingR')</code></p>

<p>Also, <a href="https://github.com/jtilly/matchingR" rel="nofollow">here's a link to the source</a>.</p>

CC BY-SA 3.0
2015-05-25T21:54:00.820Z
2015-05-25T21:54:00.820Z
NickJ
<p>While answering a comment, I realized I had a post-worth response. R has become the &quot;default language&quot; for a lot of computational research statistics (for a number of reasons; nice NYT article <a href="http://www.nytimes.com/2009/01/07/technology/business-computing/07program.html?pagewanted=all&amp;_r=0" rel="noreferrer">here</a>). It's high level, free and open-source, and has a closely-related <a href="http://www.jstatsoft.org/" rel="noreferrer">journal</a> for publishing statistical algorithms. Citations and peer review are key for academia, so you get a lot of well-described code posted to the R archives (CRAN) with descriptions posted to JStat. This spills over into a lot of blogs and quick demonstration code posts.</p>
<p>That is to say, there's an enormous user-create code base for R. When I need to find an algorithm online, I'll often first look to the massive R codebase. A quick search for R code turned up the following:</p>
<p>From an <a href="http://plausibel.blogspot.com/2012/01/illustrating-deferred-acceptance.html" rel="noreferrer">R blogger</a>, with code (see the gist link):</p>
<blockquote>
<p>The Deferred Acceptance Algorithm (DAA) goes back to Gale and Shapley (1962). They introduce a rather simple algorithm that finds a stable matching for example for college admissions or in a marriage market. ... Variations of this algorithm are used in Hospital assignments in the USA, whereby recently graduated doctors submit preferences over hospitals, and hospitals submit preferences over graduates. ... Here I'm going to use R to make a little simulation of this</p>
</blockquote>
<p>From an install-able github repository for <a href="https://github.com/thiloklein/matchingMarkets" rel="noreferrer">matching markets</a>:</p>
<blockquote>
<p>R package <code>matchingMarkets</code> comes with two estimators:</p>
<ul>
<li><p><code>stabit</code>: Implements a Bayes estimator that estimates agents' preferences and corrects for sample selection in matching markets when the selection process is a one-sided matching game (i.e. group formation).</p>
</li>
<li><p><code>stabit2</code>: Implements the Bayes estimator for a two-sided matching game (i.e. the <a href="http://en.wikipedia.org/wiki/Stable_marriage_problem#Similar_problems" rel="noreferrer">college admissions</a> and <a href="http://en.wikipedia.org/wiki/Stable_marriage_problem" rel="noreferrer">stable marriage</a> problems).</p>
</li>
</ul>
<p>and three algorithms that can be used to simulate matching data:</p>
<ul>
<li><p><code>hri</code>: Constraint model for the hospital/residents problem. Finds <em>all</em> stable matchings in two-sided matching markets. Implemented for both the <a href="http://en.wikipedia.org/wiki/Stable_marriage_problem" rel="noreferrer">stable marriage problem</a> (one-to-one matching) and the <a href="http://en.wikipedia.org/wiki/Stable_marriage_problem#Similar_problems" rel="noreferrer">hospital/residents problem</a>, a.k.a. college admissions problem (many-to-one matching).</p>
</li>
<li><p><code>sri</code>: Constraint model for the stable roommates problem. Finds all stable matchings in the <a href="https://en.wikipedia.org/wiki/Stable_roommates_problem" rel="noreferrer">roommates problem</a> (one-sided matching market).</p>
</li>
<li><p><code>ttc</code>: Top-Trading-Cycles Algorithm. Finds stable matchings in the <a href="https://en.wikipedia.org/wiki/Top_trading_cycle" rel="noreferrer">housing market problem</a>.</p>
</li>
</ul>
<p>Functions <code>hri</code> and <code>sri</code> allow for <strong>incomplete preference lists</strong> (some agents find certain agents unacceptable) and <strong>unbalanced instances</strong> (unequal number of agents on both sides).</p>
</blockquote>
<p>Hopefully one of these can help. The second one in particular looks extremely useful, particularly if it provides an empirical estimator.</p>

CC BY-SA 3.0
2014-12-18T12:42:52.793Z
2016-09-03T13:32:25.260Z
2020-06-17T09:40:54.643Z
CompEcon
<p>The question of designing matching procedure (between high-schools and students, med intern and hospitals, kidney donors and receivers,...) has been widely studied by economists and vastly contributed to Roth and Shapley receiving the Nobel memorial price in economics.</p>

<p>I was wondering if you knew about any freely available <strong>code</strong> out there (ideally in a relatively high-level language) able to <strong>compute solutions</strong> to the main kind matching problems for some of the <strong>most famous algorithms</strong> proposed in the literature. I am thinking of writing one, but I'd rather not it already exists. </p>

<p>I am <strong>chiefly interested</strong> in some piece of code to compute the solution to <strong>Deferred Acceptance</strong> algorithm in a <strong>school choice</strong> problem, but anything else would be appreciated.</p>

CC BY-SA 3.0
2016-02-12T15:02:51.217Z
In our ReplicationWiki you can find replication material for many methods. An overview of empirical studies that used matching can be found [here](http://replication.uni-goettingen.de/wiki/index.php/Matching). You can also see if replications are already known. If you only want cases with data and code and want to see what software was used you can [use the search form like here](http://tinyurl.com/ReplicationWiki-matching), there is an example with MATLAB and one with R/ConG.
Jan Höffler
CC BY-SA 3.0
2016-02-12T16:54:54.863Z
In the ReplicationWiki (that I work on) you can find replication material for many methods. An overview of empirical studies that used matching can be found [here](http://replication.uni-goettingen.de/wiki/index.php/Matching). You can also see if replications are already known. If you only want cases with data and code and want to see what software was used you can [use the search form like here](http://tinyurl.com/ReplicationWiki-matching), there is an example with MATLAB and one with R/ConG.
Jan Höffler
CC BY-SA 3.0
2014-12-17T22:34:01.653Z
Have you looked into R packages for matching algorithms? See [here](http://cran.r-project.org/web/packages/Matching/index.html) for example ([JSS paper](http://www.jstatsoft.org/v42/i07/paper)). This doesn't exactly address your example problem, but may be a place to start.
CompEcon
CC BY-SA 3.0
2015-05-26T00:40:23.373Z
A relevant [lecture](http://quant-econ.net/py/schelling.html) (with some code) on the QuantEcon website.
cc7768
<algorithms><mechanism-design>
Available code for computing solutions to matching algorithms?
Martin Van der Linden
# Available code for computing solutions to matching algorithms?

(Asked by: username_0 on 2014-12-16)

The question of designing matching procedure (between high-schools and students, med intern and hospitals, kidney donors and receivers,...) has been widely studied by economists and vastly contributed to Roth and Shapley receiving the Nobel memorial price in economics.

I was wondering if you knew about any freely available **code** out there (ideally in a relatively high-level language) able to **compute solutions** to the main kind matching problems for some of the **most famous algorithms** proposed in the literature. I am thinking of writing one, but I'd rather not it already exists.

I am **chiefly interested** in some piece of code to compute the solution to **Deferred Acceptance** algorithm in a **school choice** problem, but anything else would be appreciated.

**Tags:** algorithms, mechanism-design

> **Comments:**
> **username_2**: Have you looked into R packages for matching algorithms? See [here](http://cran.r-project.org/web/packages/Matching/index.html) for example ([JSS paper](http://www.jstatsoft.org/v42/i07/paper)). This doesn't exactly address your example problem, but may be a place to start.  
> **username_3**: A relevant [lecture](http://quant-econ.net/py/schelling.html) (with some code) on the QuantEcon website.  
> **username_1**: In our ReplicationWiki you can find replication material for many methods. An overview of empirical studies that used matching can be found [here](http://replication.uni-goettingen.de/wiki/index.php/Matching). You can also see if replications are already known. If you only want cases with data and code and want to see what software was used you can [use the search form like here](http://tinyurl.com/ReplicationWiki-matching), there is an example with MATLAB and one with R/ConG.  
> **username_1**: In the ReplicationWiki (that I work on) you can find replication material for many methods. An overview of empirical studies that used matching can be found [here](http://replication.uni-goettingen.de/wiki/index.php/Matching). You can also see if replications are already known. If you only want cases with data and code and want to see what software was used you can [use the search form like here](http://tinyurl.com/ReplicationWiki-matching), there is an example with MATLAB and one with R/ConG.  

---

## 2 answers

### Answer by username_2 on 2014-12-18. Score: 11 | Accepted answer

While answering a comment, I realized I had a post-worth response. R has become the "default language" for a lot of computational research statistics (for a number of reasons; nice NYT article [here](http://www.nytimes.com/2009/01/07/technology/business-computing/07program.html?pagewanted=all&_r=0)). It's high level, free and open-source, and has a closely-related [journal](http://www.jstatsoft.org/) for publishing statistical algorithms. Citations and peer review are key for academia, so you get a lot of well-described code posted to the R archives (CRAN) with descriptions posted to JStat. This spills over into a lot of blogs and quick demonstration code posts.

That is to say, there's an enormous user-create code base for R. When I need to find an algorithm online, I'll often first look to the massive R codebase. A quick search for R code turned up the following:

From an [R blogger](http://plausibel.blogspot.com/2012/01/illustrating-deferred-acceptance.html), with code (see the gist link):

> The Deferred Acceptance Algorithm (DAA) goes back to Gale and Shapley (1962). They introduce a rather simple algorithm that finds a stable matching for example for college admissions or in a marriage market. ... Variations of this algorithm are used in Hospital assignments in the USA, whereby recently graduated doctors submit preferences over hospitals, and hospitals submit preferences over graduates. ... Here I'm going to use R to make a little simulation of this

From an install-able github repository for [matching markets](https://github.com/thiloklein/matchingMarkets):

> R package `matchingMarkets` comes with two estimators:
>
> * `stabit`: Implements a Bayes estimator that estimates agents' preferences and corrects for sample selection in matching markets when the selection process is a one-sided matching game (i.e. group formation).
> * `stabit2`: Implements the Bayes estimator for a two-sided matching game (i.e. the [college admissions](http://en.wikipedia.org/wiki/Stable_marriage_problem#Similar_problems) and [stable marriage](http://en.wikipedia.org/wiki/Stable_marriage_problem) problems).
>
> and three algorithms that can be used to simulate matching data:
>
> * `hri`: Constraint model for the hospital/residents problem. Finds *all* stable matchings in two-sided matching markets. Implemented for both the [stable marriage problem](http://en.wikipedia.org/wiki/Stable_marriage_problem) (one-to-one matching) and the [hospital/residents problem](http://en.wikipedia.org/wiki/Stable_marriage_problem#Similar_problems), a.k.a. college admissions problem (many-to-one matching).
> * `sri`: Constraint model for the stable roommates problem. Finds all stable matchings in the [roommates problem](https://en.wikipedia.org/wiki/Stable_roommates_problem) (one-sided matching market).
> * `ttc`: Top-Trading-Cycles Algorithm. Finds stable matchings in the [housing market problem](https://en.wikipedia.org/wiki/Top_trading_cycle).
>
> Functions `hri` and `sri` allow for **incomplete preference lists** (some agents find certain agents unacceptable) and **unbalanced instances** (unequal number of agents on both sides).

Hopefully one of these can help. The second one in particular looks extremely useful, particularly if it provides an empirical estimator.


---

### Answer by username_4 on 2015-05-25. Score: 1

I know this is a bit out of date, but there is a new package available on CRAN now called 'matchingR' which I believe is much faster than the package recommended above. You can install it with

`install.packages('matchingR')`

Also, [here's a link to the source](https://github.com/jtilly/matchingR).


---

