matchingR (version 1.0.1)

matchingR-package: matchingR: Efficient Computation of the Gale-Shapley Algorithm in R and C++

Description

matchingR is an R Package that quickly computes the Gale-Shapley Algorithm for large scale matching markets. This package can be useful when the number of market participants is large or when very many matchings need to be computed (e.g. for extensive simulations or for estimation purposes). The package has successfully been used to simulate preferences and compute the matching with 30,000 participants on each side of the market. The algorithm computes the solution to the http://en.wikipedia.org/wiki/Stable_matching{stable marriage problem} and to the http://en.wikipedia.org/wiki/Hospital_resident{college admission problem}.

References

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

Examples

# stable marriage problem
nmen = 25
nwomen = 20
uM = matrix(runif(nmen*nwomen), nrow=nmen, ncol=nwomen)
uW = matrix(runif(nwomen*nmen), nrow=nwomen, ncol=nmen)
results = one2one(uM, uW)
checkStability(uM, uW, results$proposals, results$engagements)

# college admissions problem
nstudents = 25
ncolleges = 5
uStudents = matrix(runif(nstudents*ncolleges), nrow=nstudents, ncol=ncolleges)
uColleges = matrix(runif(nstudents*ncolleges), nrow=ncolleges, ncol=nstudents)
results = one2many(uStudents, uColleges, slots=4)
checkStability(uStudents, uColleges, results$proposals, results$engagements)