Matching Algorithms in R and C++

Computes matching algorithms quickly using Rcpp. 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. Implements Irving's Algorithm for the stable roommate problem. Implements the top trading cycle algorithm for the indivisible goods trading problem.


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] TRUE

College 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=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,]    4

News

matchingR 1.3

  • Allow colleges to have different numbers of slots #31
  • Change row names in vignette #34
  • Remove need for microbenchmark package #35
  • Registration of entry points in compiled code

matchingR 1.2.2

This is a minor update.

  • Colleges may have different numbers of slots in the college admissions problem (#30)

matchingR 1.2.1

This is a minor update.

  • Fixed bug in galeShapley.checkStability that resulted in UBSAN throwing an error

matchingR 1.2

  • Fixed a bug in the stable roommate matching algorithm that caused problems on Mac OS X / clang
  • Changed function names throughout the package (deprecated old function names)
  • Updated documentation
  • Added tests
  • Removed option to define preferences in row major order

matchingR 1.1.1

This is a minor update.

  • It fixes a memory leak warning in the stable roommate algorithm.
  • It includes minor edits of the vignettes and documentation.
  • We have substantially shortened the computational performance vignette so that the package can be built and checked faster

matchingR 1.1

This is a major update that added additional algorithms to the package.

  • Added algorithm to compute a solution to the stable roommate problem (roommate)
  • Added top trading cycle algorithm (toptrading)
  • Switched the layout of preference matrices from row order to column order to make the code faster
  • Added two vignettes: An introductory vignette to the package in general and a computational performance vignette

matchingR 1.0.1

Initial release that computes two versions of the Gale-Shapley algorithm:

  • Stable Marriage Problem
  • College Admissions Problem

Reference manual

It appears you don't have a PDF plugin for this browser. You can click here to download the reference manual.

install.packages("matchingR")

1.3.0 by Jan Tilly, 2 years ago


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


Report a bug at https://github.com/jtilly/matchingR/issues/


Browse source code at https://github.com/cran/matchingR


Authors: Jan Tilly , Nick Janetos


Documentation:   PDF Manual  


Task views: Optimization and Mathematical Programming


GPL (>= 2) license


Depends on Rcpp

Suggests testthat, knitr

Linking to Rcpp, RcppArmadillo


Imported by seqgendiff.


See at CRAN