Learn R Programming

Matching Algorithms in R and C++

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

Installation

matchingR may be installed from CRAN:

install.packages("matchingR")

The latest development release is available from GitHub:

devtools::install_github("jtilly/matchingR")

Examples

Gale-Shapley Algorithm for Two-Sided Markets

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 = 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

Irving's Algorithm for the Stable Roommate Problem

# 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

# 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

Documentation

Copy Link

Version

Install

install.packages('matchingR')

Monthly Downloads

365

Version

1.3.3

License

GPL (>= 2)

Issues

Pull Requests

Stars

Forks

Maintainer

Last Published

May 25th, 2021

Functions in matchingR (1.3.3)

cpp_wrapper_galeshapley_check_stability

C++ Wrapper to Check Stability of Two-sided Matching
cpp_wrapper_ttc_check_stability

Check if a one-sided matching for the top trading cycle algorithm is stable
galeShapley.checkStability

Check if a two-sided matching is stable
galeShapley.collegeAdmissions

Gale-Shapley Algorithm: College Admissions Problem
cpp_wrapper_galeshapley

C++ wrapper for Gale-Shapley Algorithm
galeShapley.checkPreferences

Check if preference order is complete
cpp_wrapper_irving

Computes a stable roommate matching
cpp_wrapper_ttc

Computes the top trading cycle algorithm
galeShapley.marriageMarket

Gale-Shapley Algorithm: Stable Marriage Problem
cpp_wrapper_irving_check_stability

Check if a matching solves the stable roommate problem
roommate.checkStability

Check if a roommate matching is stable
repcol

Repeat each column of a matrix n times
roommate

Compute matching for one-sided markets
roommate.checkPreferences

Check if preference order for a one-sided market is complete
reprow

Repeat each row of a matrix n times
rankIndex

Rank elements within column of a matrix
matchingR-package

matchingR: Matching Algorithms in R and C++
galeShapley.validate

Input validation of preferences
roommate.validate

Input validation for one-sided markets
toptrading

Compute the top trading cycle algorithm
matchingR-deprecated

Deprecated Functions in matchingR
toptrading.checkStability

Check if there are any pairs of agents who would rather swap houses with each other rather than be with their own two current respective partners.
sortIndexOneSided

Ranks elements with column of a matrix, assuming a one-sided market.
sortIndex

Sort indices of a matrix within a column