matchingR-package: matchingR: Matching Algorithms in R and C++

In matchingR: Matching Algorithms in R and C++

Description

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.

Author(s)

Jan Tilly, Nick Janetos

References

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.

See Also

Useful links:

• https://github.com/jtilly/matchingR/

• Report bugs at https://github.com/jtilly/matchingR/issues/

Examples

# 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)

Example output

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

matchingR documentation built on May 25, 2021, 9:07 a.m.