14
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Have you looked into R packages for matching algorithms? See here for example (JSS paper). This doesn't exactly address your example problem, but may be a place to start. $\endgroup$
    – CompEcon
    Dec 17, 2014 at 22:34
  • $\begingroup$ A relevant lecture (with some code) on the QuantEcon website. $\endgroup$
    – cc7768
    May 26, 2015 at 0:40
  • $\begingroup$ In our ReplicationWiki you can find replication material for many methods. An overview of empirical studies that used matching can be found here. 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, there is an example with MATLAB and one with R/ConG. $\endgroup$
    – Jan Höffler
    Feb 12, 2016 at 15:02
  • 1
    $\begingroup$ 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. 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, there is an example with MATLAB and one with R/ConG. $\endgroup$
    – Jan Höffler
    Feb 12, 2016 at 16:54

2 Answers 2

Reset to default
11
$\begingroup$

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). It's high level, free and open-source, and has a closely-related journal 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, 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:

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 and stable marriage 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 (one-to-one matching) and the hospital/residents problem, 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 (one-sided matching market).

  • ttc: Top-Trading-Cycles Algorithm. Finds stable matchings in the housing market problem.

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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