MyNixOS website logo
Description
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.

Matching Algorithms in R and C++

GitHub Actions Coverage Status CRAN_Status_Badge CRAN_Downloads

"You know that I'll never leave you. Not as long as she's with someone."

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

Metadata

Version

1.3.3

License

Unknown

Platforms (75)

    Darwin
    FreeBSD
    Genode
    GHCJS
    Linux
    MMIXware
    NetBSD
    none
    OpenBSD
    Redox
    Solaris
    WASI
    Windows
Show all
  • aarch64-darwin
  • aarch64-genode
  • aarch64-linux
  • aarch64-netbsd
  • aarch64-none
  • aarch64_be-none
  • arm-none
  • armv5tel-linux
  • armv6l-linux
  • armv6l-netbsd
  • armv6l-none
  • armv7a-darwin
  • armv7a-linux
  • armv7a-netbsd
  • armv7l-linux
  • armv7l-netbsd
  • avr-none
  • i686-cygwin
  • i686-darwin
  • i686-freebsd
  • i686-genode
  • i686-linux
  • i686-netbsd
  • i686-none
  • i686-openbsd
  • i686-windows
  • javascript-ghcjs
  • loongarch64-linux
  • m68k-linux
  • m68k-netbsd
  • m68k-none
  • microblaze-linux
  • microblaze-none
  • microblazeel-linux
  • microblazeel-none
  • mips-linux
  • mips-none
  • mips64-linux
  • mips64-none
  • mips64el-linux
  • mipsel-linux
  • mipsel-netbsd
  • mmix-mmixware
  • msp430-none
  • or1k-none
  • powerpc-netbsd
  • powerpc-none
  • powerpc64-linux
  • powerpc64le-linux
  • powerpcle-none
  • riscv32-linux
  • riscv32-netbsd
  • riscv32-none
  • riscv64-linux
  • riscv64-netbsd
  • riscv64-none
  • rx-none
  • s390-linux
  • s390-none
  • s390x-linux
  • s390x-none
  • vc4-none
  • wasm32-wasi
  • wasm64-wasi
  • x86_64-cygwin
  • x86_64-darwin
  • x86_64-freebsd
  • x86_64-genode
  • x86_64-linux
  • x86_64-netbsd
  • x86_64-none
  • x86_64-openbsd
  • x86_64-redox
  • x86_64-solaris
  • x86_64-windows