Description Author(s) References See Also Examples

matchingR is an R package which quickly computes a variety of matching algorithms for one-sided and two-sided markets. This package implements

the Gale-Shapley Algorithm to compute the stable matching for two-sided markets, such as the stable marriage problem and the college-admissions problem

Irving's Algorithm to compute the stable matching for one-sided markets such as the stable roommates problem

the top trading cycle algorithm for the indivisible goods trading problem.

All matching algorithms are implemented in `C++`

and can therefore be
computed quickly. The package may be useful when the number of market
participants is large or when many matchings need to be computed (e.g. for
extensive simulations or for estimation purposes). The Gale-Shapley
function of this package has successfully been used to simulate preferences
and compute the 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 that 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 the Boston Public School Match (and many more)

the matching of kidney donors to recipients in kidney exchanges.

Jan Tilly, Nick Janetos

Gale, D. and Shapley, L.S. (1962). College admissions and the
stability of marriage. *The American Mathematical Monthly*, 69(1):
9–15.

Irving, R. W. (1985). An efficient algorithm for the "stable
roommates" problem. *Journal of Algorithms*, 6(4): 577–595

Shapley, L., & Scarf, H. (1974). On cores and indivisibility.
*Journal of Mathematical Economics*, 1(1), 23-37.

Useful links:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 | ```
# stable marriage problem
set.seed(1)
nmen <- 25
nwomen <- 20
uM <- matrix(runif(nmen * nwomen), nrow = nwomen, ncol = nmen)
uW <- matrix(runif(nwomen * nmen), nrow = nmen, ncol = nwomen)
results <- galeShapley.marriageMarket(uM, uW)
galeShapley.checkStability(uM, uW, results$proposals, results$engagements)
# college admissions problem
nstudents <- 25
ncolleges <- 5
uStudents <- matrix(runif(nstudents * ncolleges), nrow = ncolleges, ncol = nstudents)
uColleges <- matrix(runif(nstudents * ncolleges), nrow = nstudents, ncol = ncolleges)
results <- galeShapley.collegeAdmissions(
studentUtils = uStudents,
collegeUtils = uColleges,
slots = 4
)
results
# check stability
galeShapley.checkStability(
uStudents,
uColleges,
results$matched.students,
results$matched.colleges
)
# stable roommate problem
set.seed(2)
N <- 10
u <- matrix(runif(N^2), nrow = N, ncol = N)
results <- roommate(utils = u)
results
# check stability
roommate.checkStability(utils = u, matching = results)
# top trading cycle algorithm
N <- 10
u <- matrix(runif(N^2), nrow = N, ncol = N)
results <- toptrading(utils = u)
results
# check stability
toptrading.checkStability(utils = u, matching = results)
``` |

```
Loading required package: Rcpp
[1] TRUE
$unmatched.students
[1] 7 9 12 19 25
$unmatched.colleges
integer(0)
$matched.colleges
[,1] [,2] [,3] [,4]
[1,] 13 6 14 18
[2,] 5 4 1 15
[3,] 22 10 21 17
[4,] 16 3 2 8
[5,] 24 23 11 20
$matched.students
[,1]
[1,] 2
[2,] 4
[3,] 4
[4,] 2
[5,] 2
[6,] 1
[7,] NA
[8,] 4
[9,] NA
[10,] 3
[11,] 5
[12,] NA
[13,] 1
[14,] 1
[15,] 2
[16,] 4
[17,] 3
[18,] 1
[19,] NA
[20,] 5
[21,] 3
[22,] 3
[23,] 5
[24,] 5
[25,] NA
[1] TRUE
[,1]
[1,] 5
[2,] 7
[3,] 4
[4,] 3
[5,] 1
[6,] 8
[7,] 2
[8,] 6
[9,] 10
[10,] 9
[1] TRUE
[,1]
[1,] 7
[2,] 9
[3,] 3
[4,] 4
[5,] 6
[6,] 5
[7,] 8
[8,] 1
[9,] 2
[10,] 10
[1] TRUE
```

Embedding an R snippet on your website

Add the following code to your website.

For more information on customizing the embed code, read Embedding Snippets.