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

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

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 `j`th 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 `i`th 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 `1`th and `2`th columns containing student couple id's; `3`th and `4`th 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.
...	.

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.

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.

Examples

##\dontrun{
## Example with given preferences
(s.prefs <- matrix(c(4,2,3,5, 2,1,3,NA, 1,2,3,4), 4,3))
#>      [,1] [,2] [,3]
#> [1,]    4    2    1
#> [2,]    2    1    2
#> [3,]    3    3    3
#> [4,]    5   NA    4
(c.prefs <- matrix(rep(1:5,5), 5,5))
#>      [,1] [,2] [,3] [,4] [,5]
#> [1,]    1    1    1    1    1
#> [2,]    2    2    2    2    2
#> [3,]    3    3    3    3    3
#> [4,]    4    4    4    4    4
#> [5,]    5    5    5    5    5
(co.prefs <- matrix(c(rep(4,3), rep(5,3), 3,3,NA, 3,NA,3), 3,4))
#>      [,1] [,2] [,3] [,4]
#> [1,]    4    5    3    3
#> [2,]    4    5    3   NA
#> [3,]    4    5   NA    3
res <- hri2(s.prefs=s.prefs, c.prefs=c.prefs, co.prefs=co.prefs, nSlots=rep(1,5))
res$matchings
#>      student college
#> [1,]       1       4
#> [2,]       2       2
#> [3,]       3       1
#> [4,]       4       3
# 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
#>       student college
#>  [1,]       1       2
#>  [2,]       2      20
#>  [3,]       3      21
#>  [4,]       4      26
#>  [5,]       5      20
#>  [6,]       6       7
#>  [7,]       7       1
#>  [8,]       8      24
#>  [9,]       9      29
#> [10,]      10      10
#> [11,]      11      23
#> [12,]      12      26
#> [13,]      13      12
#> [14,]      14       5
#> [15,]      15       6
#> [16,]      16      14
#> [17,]      17       4
#> [18,]      18      13
#> [19,]      19      16
#> [20,]      20      13
#> [21,]      21      30
#> [22,]      22      12
#> [23,]      23      18
#> [24,]      24       5
#> [25,]      25       6
#> [26,]      26      21
#> [27,]      27      20
#> [28,]      28      17
#> [29,]      29       2
#> [30,]      30      11
#> [31,]      31      12
#> [32,]      32      27
#> [33,]      33       3
#> [34,]      34      20
#> [35,]      35      24
#> [36,]      36       7
#> [37,]      37      15
#> [38,]      38      16
#> [39,]      39       8
#> [40,]      40      20
#> [41,]      41       1
#> [42,]      42      20
#> [43,]      43       9
#> [44,]      44      28
#> [45,]      45      24
#> [46,]      46      15
#> [47,]      47      15
#> [48,]      48      21
#> [49,]      49      21
#> [50,]      50      27
#> [51,]      51      15
#> [52,]      52      10
#> [53,]      53       6
#> [54,]      54      20
#> [55,]      55      15
#> [56,]      56       3
#> [57,]      57       3
#> [58,]      58       1
# 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))
#> [1] "Input passed consistency test!"
res$matching
#>      student  college 
#> [1,] "Mia"    "Micro1"
#> [2,] "Kai"    "Macro" 
#> [3,] "Niklas" "Micro1"

## 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))
#> [1] "Input passed consistency test!"
res$matching
#>      student  college 
#> [1,] "Mia"    "Micro1"
#> [2,] "Kai"    "Macro" 
#> [3,] "Niklas" "Micro1"
##}