The hardware and bandwidth for this mirror is donated by METANET, the Webhosting and Full Service-Cloud Provider.
If you wish to report a bug, or if you are interested in having us mirror your free-software or open-source project, please feel free to contact us at mirror[@]metanet.ch.
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
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
# 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(uM, uW)
matching$engagements
#> [,1]
#> [1,] 3
#> [2,] 1
matching$single.proposers
#> [1] 2
galeShapley.checkStability(uM, uW, matching$proposals, matching$engagements)
#> [1] TRUECollege Admissions Problem
# 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# 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# 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,] 4These binaries (installable software) and packages are in development.
They may not be fully stable and should be used with caution. We make no claims about them.