matchingR is an R package which quickly computes the Gale-Shapley algorithm, Irving's algorithm for the stable roommate problem, and the top trading cycle algorithm for large matching markets. The package provides functions to compute the solutions to the
stable marriage problem, the
college admission problem, the
stable roommates problem, and the
house allocation problem.
The package may be useful when the number of market participants is large or when many matchings need to be computed (e.g., for simulation or estimation purposes). It has been used in practice to compute the Gale-Shapley stable matching with 30,000 participants on each side of the market.
Matching markets are common in practice and widely studied by economists. Popular examples include
- the National Resident Matching Program which matches graduates from medical school to residency programs at teaching hospitals throughout the United States
- the matching of students to schools including the New York City High School Match or the Boston Public School Match (and many more)
- the matching of kidney donors to recipients in kidney exchanges.
matchingR may be installed from CRAN:
install.packages("matchingR")The latest development release is available from GitHub:
devtools::install_github("jtilly/matchingR")
Stable Marriage Problem
library(matchingR) # stable marriage problem with three men and two women uM = matrix(c(1.0, 0.5, 0.0, 0.5, 0.0, 0.5), nrow = 2, ncol = 3, byrow = TRUE) uW = matrix(c(0.0, 1.0, 0.5, 0.0, 1.0, 0.5), nrow = 3, ncol = 2, byrow = TRUE) matching = galeShapley.marriageMarket(uM, uW) matching$engagements #> [,1] #> [1,] 3 #> [2,] 1 matching$single.proposers #> [1] 2 galeShapley.checkStability(uM, uW, matching$proposals, matching$engagements) #> [1] TRUE
College Admissions Problem
library(matchingR) # college admissions problem with five students and two colleges with two slots each set.seed(1) nStudents <- 5 nColleges <- 2 uStudents <- matrix(runif(nStudents * nColleges), nrow = nColleges, ncol = nStudents) uStudents #> [,1] [,2] [,3] [,4] [,5] #> [1,] 0.2655087 0.5728534 0.2016819 0.9446753 0.62911404 #> [2,] 0.3721239 0.9082078 0.8983897 0.6607978 0.06178627 uColleges <- matrix(runif(nStudents * nColleges), nrow = nStudents, ncol = nColleges) uColleges #> [,1] [,2] #> [1,] 0.2059746 0.4976992 #> [2,] 0.1765568 0.7176185 #> [3,] 0.6870228 0.9919061 #> [4,] 0.3841037 0.3800352 #> [5,] 0.7698414 0.7774452 matching <- galeShapley.collegeAdmissions(uStudents, uColleges, slots = c(2, 2)) matching$matched.students #> [,1] #> [1,] NA #> [2,] 2 #> [3,] 2 #> [4,] 1 #> [5,] 1 matching$matched.colleges #> [,1] [,2] #> [1,] 5 4 #> [2,] 3 2 galeShapley.checkStability(uStudents, uColleges, matching$matched.students, matching$matched.colleges) #> [1] TRUE
library(matchingR) # stable roommate problem with four students and two rooms set.seed(2) n <- 4 u <- matrix(runif(n ^ 2), nrow = n, ncol = n) u #> [,1] [,2] [,3] [,4] #> [1,] 0.1848823 0.9438393 0.4680185 0.7605133 #> [2,] 0.7023740 0.9434750 0.5499837 0.1808201 #> [3,] 0.5733263 0.1291590 0.5526741 0.4052822 #> [4,] 0.1680519 0.8334488 0.2388948 0.8535485 results <- roommate(utils = u) results #> [,1] #> [1,] 2 #> [2,] 1 #> [3,] 4 #> [4,] 3
library(matchingR) # top trading cycle algorithm with four houses set.seed(2) n <- 4 u <- matrix(runif(n ^ 2), nrow = n, ncol = n) u #> [,1] [,2] [,3] [,4] #> [1,] 0.1848823 0.9438393 0.4680185 0.7605133 #> [2,] 0.7023740 0.9434750 0.5499837 0.1808201 #> [3,] 0.5733263 0.1291590 0.5526741 0.4052822 #> [4,] 0.1680519 0.8334488 0.2388948 0.8535485 results <- toptrading(utils = u) results #> [,1] #> [1,] 2 #> [2,] 1 #> [3,] 3 #> [4,] 4