Resident-optimal matching in the hospital/residents problem with couples
Implements the Roth Peranson matching algorithm for the hospital/residents problem with couples as described in Roth and Peranson (1999). The function is based on an adoption of Bacchus (2018) and the SAT-solver of Sorenssen (2013).
hri2( nStudents = ncol(s.prefs), nColleges = ncol(c.prefs), nSlots = rep(1, nColleges), nCouples = ncol(co.prefs), s.prefs = NULL, c.prefs = NULL, co.prefs = NULL, randomization = "multiple", seed = NULL, check_consistency = TRUE, verbose = FALSE, ... )
nStudents: integer indicating the number of students (in the college admissions problem) or men (in the stable marriage problem) in the market. Defaults to ncol(s.prefs).nColleges: integer indicating the number of colleges (in the college admissions problem) or women (in the stable marriage problem) in the market. Defaults to ncol(c.prefs).nSlots: vector of length nColleges indicating the number of places (i.e. quota) of each college. Defaults to rep(1,nColleges) for the marriage problem.nCouples: integer indicating the number of couples (in the college admissions problem) or men (in the stable marriage problem) in the market. Defaults to ncol(co.prefs)s.prefs: matrix of dimension nColleges x nStudents with the jth column containing student j's ranking over colleges in decreasing order of preference (i.e. most preferred first).c.prefs: matrix of dimension nStudents x nColleges with the ith column containing college i's ranking over students in decreasing order of preference (i.e. most preferred first).co.prefs: matrix of dimension 4 x nCouplesPrefs in long format with the 1th and 2th columns containing student couple id's; 3th and 4th is a 2-tuple ranking over college preference for the couple (coupleStudent1.pref, coupleStudent2.pref) in decreasing order of preference by rows (i.e. most preferred first).randomization: determines at which level and in which order random lottery numbers for student priorities are drawn. The default is randomization = "multiple", where a student's priority is determined by a separate lottery at each college (i.e. local tie-breaking). For the second variant, randomization = "single", a single lottery number determines a student's priority at all colleges (i.e. global tie breaking). A third variant is common in the context of course allocation, where a "couple" represents a student who submits a preference ranking over single courses (first course) and combinations of courses (first and second course). Here, the option randomization = "single-course-first" gives applications for a student's single courses strictly higher priority than for course combinations. This ensures the fairness criterion that a student is only assigned a second course after single course applications of all students have been considered.seed: integer setting the state for random number generation.check_consistency: Performs additional consicentcy checks if the preference matrices are given by characters. Defaults to FALSE. Set to FALSE to reduce run-time.verbose: logical. When set to TRUE, writes information messages on the console (recommended). Defaults to FALSE, which suppresses such messages....: .hri2 returns a list of the following elements: - matchings: List of matched students and colleges.
hri2 requires the following combination of arguments, subject to the matching problem.
nStudents, nColleges: Residence hospital problem without couples and random preferencesnStudents, nColleges, nCouples, nSlots: Residence hospital problem with couples and random preferences.s.prefs, c.prefs, co.prefs, nSlots: Residence hospital problem with couples and given preferences.## Example with given preferences s.prefs <- matrix(c(4,2,3,5, 2,1,3,NA, 1,2,3,4), 4,3) c.prefs <- matrix(rep(1:5,5), 5,5) co.prefs <- matrix(c(rep(4,3), rep(5,3), 3,3,NA, 3,NA,3), 3,4) res <- hri2(s.prefs=s.prefs, c.prefs=c.prefs, co.prefs=co.prefs, nSlots=rep(1,5)) res$matchings # summary(res) ## Example with random preferences nStudents <- 50 nColleges <- 30 nCouples <- 4 nSlots <- sample(1:nStudents, nColleges) res <- hri2(nStudents=nStudents, nColleges=nColleges, nCouples=nCouples, nSlots=nSlots) res$matchings # summary(res) ## Example with characters in the preferences matrices s.prefs <- matrix(c("Micro1", NA, NA, "Micro2", "Micro1", "Macro", "Macro",NA ,NA), ncol = 3) colnames(s.prefs) <- c('Lea', 'Mia', 'Kai') c.prefs <- matrix(c("Niklas", "Kai", "Mia", "Anna", "Lea", "Kai", "Anna",NA, "Kai", "Mia", "Lea",NA), ncol = 3) colnames(c.prefs) <- c('Micro1', 'Micro2', 'Macro') col1 <- c(rep("Niklas",4),rep("Anna",5)) col2 <- c(rep("Jan",4),rep("Lisa",5)) col3 <- c("Micro1","Macro","Micro1",NA,"Macro", NA,"Micro2","Micro2","Macro") col4 <- c("Micro2","Micro1",NA,"Macro","Macro", "Micro1","Micro2","Macro",NA) co.prefs <- matrix(c(col1,col2,col3,col4), ncol = 4) res <- hri2(s.prefs=s.prefs, c.prefs=c.prefs, co.prefs=co.prefs, nSlots=c(2,1,1)) res$matching ## Example if students are allowed to apply and be accepted by two courses col12 <- c(rep(c(rep("Niklas",4),rep("Anna",2)),2)) col3 <- c("Micro1","Macro","Micro1","Macro","Macro","Macro") col4 <- c("Micro2","Micro1",NA,NA,"Micro1","Micro2") co.prefs <- matrix(c(col12,col3,col4), ncol = 4) res <- hri2(s.prefs=s.prefs, c.prefs=c.prefs, co.prefs=co.prefs, nSlots=c(2,1,1)) res$matching
Bacchus, F. (2018). Stable matching suite. GitHub repository.
Gale, D. and L.S. Shapley (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9--15.
Roth, A. E., & Peranson, E. (1999). The redesign of the matching market for American physicians: Some engineering aspects of economic design. American economic review, 89(4), 748-780.
Kojima, F., Pathak, P. A., & Roth, A. E. (2013). Matching with couples: Stability and incentives in large markets. The Quarterly Journal of Economics, 128(4), 1585-1632.
Sorenssen, N. (2013). minisat. GitHub repository.
Fahiem Bacchus, Sven Giegerich, Thilo Klein, Niklas Sorensson
Useful links