hri2 {matchingMarkets}

Resident-optimal matching in the hospital/residents problem with couples

Description

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).

Usage

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,
  ...
)

Arguments

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.

...

.

Value

hri2 returns a list of the following elements:

matchings

List of matched students and colleges.

summary

Detailed report of the matching result, including futher information on ranks.

Minimum required arguments

hri2 requires the following combination of arguments, subject to the matching problem.

nStudents, nColleges

Residence hospital problem without couples and random preferences

nStudents, 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.

Author(s)

Fahiem Bacchus, Sven Giegerich, Thilo Klein, Niklas Sorensson

References

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.

Examples

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