All stable matchings in the hospital/residents problem with incomplete lists

Finds all stable matchings in either the hospital/residents problem (a.k.a. college admissions problem) or the related stable marriage problem. Dependent on the problem, the results comprise the student and college-optimal or the men and women-optimal matchings. The implementation allows for incomplete preference lists (some agents find certain agents unacceptable) and unbalanced instances (unequal number of agents on both sides). The function uses the Prosser (2014) constraint encoding based on either given or randomly generated preferences.

hri(nStudents = ncol(s.prefs), nColleges = ncol(c.prefs),
  nSlots = rep(1, nColleges), s.prefs = NULL, c.prefs = NULL,
  s.range = NULL, c.range = NULL, randomization = NULL,
  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.
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).
s.range	range of two intergers `s.range = c(s.min, s.max)`, where `s.min < s.max`. Produces incomplete preference lists with the length of each student's list randomly sampled from the range `[s.min, s.max]`. Note: interval is only correct if either c.range or s.range is used.
c.range	range of two intergers `c.range = c(c.min, c.max)`, where `c.min < c.max`. Produces incomplete preference lists with the length of each college's list randomly sampled from the range `[c.min, c.max]`. Note: interval is only correct if either c.range or s.range is used.
randomization	determines at which level 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).
seed	integer setting the state for random number generation.
check_consistency	Performs consicentcy checks (Checks if there are columns in the preference matrices that only contains zeros and drops them and checks the matrixes for consistencies if they are given by characters). Defaults to `TRUE` but changing it to `FALSE` might reduce the running-time for large problems.
...	.

Value

hri returns a list of the following elements.

s.prefs.smi

student-side preference matrix for the stable marriage problem with incomplete lists (SMI).

c.prefs.smi

college-side preference matrix for the stable marriage problem with incomplete lists (SMI).

s.prefs.hri

student-side preference matrix for the college admissions problem (a.k.a. hospital/residents problem) with incomplete lists (HRI).

c.prefs.hri

college-side preference matrix for the college admissions problem (a.k.a. hospital/residents problem) with incomplete lists (HRI).

matchings

edgelist of matched students and colleges, inculding the number of the match (matching) and two variables that indicate the student-optimal match (sOptimal) and college-optimal match (cOptimal)

Minimum required arguments

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

nStudents, nColleges: Marriage problem with random preferences.
s.prefs, c.prefs: Marriage problem with given preferences.
nStudents, nSlots: College admissions problem with random preferences.
s.prefs, c.prefs, nSlots: College admissions problem with given preferences.

References

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

Morizumi, Y., T. Hayashi and Y. Ishida (2011). A network visualization of stable matching in the stable marriage problem. Artificial Life Robotics, 16:40--43.

Prosser, P. (2014). Stable Roommates and Constraint Programming. Lecture Notes in Computer Science, CPAIOR 2014 Edition. Springer International Publishing, 8451: 15--28.

Examples

##\dontrun{
## -----------------------
## --- Marriage problem 

## 7 men, 6 women, random preferences:
 hri(nStudents=7, nColleges=6, seed=4)
#> $s.prefs.smi
#>      1 2 3 4 5 6 7
#> [1,] 4 5 1 6 4 4 3
#> [2,] 1 6 5 4 5 2 4
#> [3,] 2 4 2 3 2 6 2
#> [4,] 5 1 4 5 3 5 1
#> [5,] 6 2 3 2 6 1 5
#> [6,] 3 3 6 1 1 3 6
#> 
#> $c.prefs.smi
#>      1 2 3 4 5 6
#> [1,] 4 4 2 7 3 4
#> [2,] 2 3 7 2 4 2
#> [3,] 5 7 5 4 7 1
#> [4,] 1 5 3 1 2 7
#> [5,] 3 6 6 6 5 3
#> [6,] 6 2 1 3 6 6
#> [7,] 7 1 4 5 1 5
#> 
#> $matchings
#>    matching college slots student sOptimal cOptimal sRank cRank
#> 1         1       1     1       3        1        0     1     5
#> 2         1       2     2       5        1        0     3     4
#> 3         1       3     3       7        1        0     1     2
#> 4         1       4     4       1        1        0     1     4
#> 5         1       5     5       2        1        0     1     4
#> 6         1       6     6       4        1        0     1     1
#> 7         2       1     1       1        0        1     2     4
#> 8         2       2     2       5        0        1     3     4
#> 9         2       3     3       7        0        1     1     2
#> 10        2       4     4       2        0        1     3     2
#> 11        2       5     5       3        0        1     2     1
#> 12        2       6     6       4        0        1     1     1
#> 
#> attr(,"class")
#> [1] "hri"

## 3 men, 2 women, given preferences:
 s.prefs <- matrix(c(1,2, 1,2, 1,2), 2,3)
 c.prefs <- matrix(c(1,2,3, 1,2,3), 3,2)
 hri(s.prefs=s.prefs, c.prefs=c.prefs)
#> $s.prefs.smi
#>      1 2 3
#> [1,] 1 1 1
#> [2,] 2 2 2
#> 
#> $c.prefs.smi
#>      1 2
#> [1,] 1 1
#> [2,] 2 2
#> [3,] 3 3
#> 
#> $matchings
#>   matching college slots student sOptimal cOptimal sRank cRank
#> 1        1       1     1       1        1        1     1     1
#> 2        1       2     2       2        1        1     2     2
#> 
#> attr(,"class")
#> [1] "hri"

## 3 men, 2 women, given preferences:
 s.prefs <- matrix(c("x","y", "x","y", "x","y"), 2,3)
 colnames(s.prefs) <- c("A","B","C")
 c.prefs <- matrix(c("A","B","C", "A","B","C"), 3,2)
 colnames(c.prefs) <- c("x","y")
 hri(s.prefs=s.prefs, c.prefs=c.prefs)
#> $s.prefs.smi
#>      A   B   C  
#> [1,] "x" "x" "x"
#> [2,] "y" "y" "y"
#> 
#> $c.prefs.smi
#>      x   y  
#> [1,] "A" "A"
#> [2,] "B" "B"
#> [3,] "C" "C"
#> 
#> $matchings
#>   matching college slots student sOptimal cOptimal sRank cRank
#> 1        1       x     x       A        1        1     1     1
#> 2        1       y     y       B        1        1     2     2
#> 
#> attr(,"class")
#> [1] "hri"

## --------------------------------
## --- College admission problem 

## 7 students, 2 colleges with 3 slots each, random preferences:
 hri(nStudents=7, nSlots=c(3,3), seed=21)
#> $s.prefs.smi
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7]
#> [1,]    4    4    4    1    4    4    1
#> [2,]    5    5    5    2    5    5    2
#> [3,]    6    6    6    3    6    6    3
#> [4,]    1    1    1    4    1    1    4
#> [5,]    2    2    2    5    2    2    5
#> [6,]    3    3    3    6    3    3    6
#> 
#> $c.prefs.smi
#>      [,1] [,2] [,3] [,4] [,5] [,6]
#> [1,]    2    2    2    5    5    5
#> [2,]    1    1    1    7    7    7
#> [3,]    3    3    3    6    6    6
#> [4,]    7    7    7    2    2    2
#> [5,]    4    4    4    3    3    3
#> [6,]    5    5    5    4    4    4
#> [7,]    6    6    6    1    1    1
#> 
#> $s.prefs.hri
#>      1 2 3 4 5 6 7
#> [1,] 2 2 2 1 2 2 1
#> [2,] 1 1 1 2 1 1 2
#> 
#> $c.prefs.hri
#>      1 2
#> [1,] 2 5
#> [2,] 1 7
#> [3,] 3 6
#> [4,] 7 2
#> [5,] 4 3
#> [6,] 5 4
#> [7,] 6 1
#> 
#> $matchings
#>    matching college slots student sOptimal cOptimal sRank cRank
#> 1         1       1     1       1        1        0     4     2
#> 2         1       1     2       3        1        0     5     3
#> 3         1       1     3       7        1        0     3     4
#> 4         1       2     6       2        1        0     3     4
#> 5         1       2     4       5        1        0     1     1
#> 6         1       2     5       6        1        0     2     3
#> 7         2       1     2       1        0        1     5     2
#> 8         2       1     1       2        0        1     4     1
#> 9         2       1     3       3        0        1     6     3
#> 10        2       2     4       5        0        1     1     1
#> 11        2       2     6       6        0        1     3     3
#> 12        2       2     5       7        0        1     5     2
#> 
#> attr(,"class")
#> [1] "hri"

## 7 students, 2 colleges with 3 slots each, given preferences:
 s.prefs <- matrix(c(1,2, 1,2, 1,NA, 1,2, 1,2, 1,2, 1,2), 2,7)
 c.prefs <- matrix(c(1,2,3,4,5,6,7, 1,2,3,4,5,NA,NA), 7,2)
 hri(s.prefs=s.prefs, c.prefs=c.prefs, nSlots=c(3,3))
#> $s.prefs.smi
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7]
#> [1,]    1    1    1    1    1    1    1
#> [2,]    2    2    2    2    2    2    2
#> [3,]    3    3    3    3    3    3    3
#> [4,]    4    4   NA    4    4   NA   NA
#> [5,]    5    5   NA    5    5   NA   NA
#> [6,]    6    6   NA    6    6   NA   NA
#> 
#> $c.prefs.smi
#>      [,1] [,2] [,3] [,4] [,5] [,6]
#> [1,]    1    1    1    1    1    1
#> [2,]    2    2    2    2    2    2
#> [3,]    3    3    3    4    4    4
#> [4,]    4    4    4    5    5    5
#> [5,]    5    5    5   NA   NA   NA
#> [6,]    6    6    6   NA   NA   NA
#> [7,]    7    7    7   NA   NA   NA
#> 
#> $s.prefs.hri
#>      1 2  3 4 5  6  7
#> [1,] 1 1  1 1 1  1  1
#> [2,] 2 2 NA 2 2 NA NA
#> 
#> $c.prefs.hri
#>      1  2
#> [1,] 1  1
#> [2,] 2  2
#> [3,] 3  4
#> [4,] 4  5
#> [5,] 5 NA
#> [6,] 6 NA
#> [7,] 7 NA
#> 
#> $matchings
#>   matching college slots student sOptimal cOptimal sRank cRank
#> 1        1       1     1       1        1        1     1     1
#> 2        1       1     2       2        1        1     2     2
#> 3        1       1     3       3        1        1     3     3
#> 4        1       2     4       4        1        1     4     3
#> 5        1       2     5       5        1        1     5     4
#> 
#> attr(,"class")
#> [1] "hri"

## 7 students, 2 colleges with 3 slots each, given preferences:
 s.prefs <- matrix(c("x","y", "x","y", "x",NA, "x","y",
                     "x","y", "x","y", "x","y"), 2,7)
 colnames(s.prefs) <- c("A","B","C","D","E","F","G")
 c.prefs <- matrix(c("A","B","C","D","E","F","G",
                     "A","B","C","D","E",NA,NA), 7,2)
 colnames(c.prefs) <- c("x","y")
 hri(s.prefs=s.prefs, c.prefs=c.prefs, nSlots=c(3,3))
#> $s.prefs.smi
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7]
#> [1,]    1    1    1    1    1    1    1
#> [2,]    2    2    2    2    2    2    2
#> [3,]    3    3    3    3    3    3    3
#> [4,]    4    4   NA    4    4   NA   NA
#> [5,]    5    5   NA    5    5   NA   NA
#> [6,]    6    6   NA    6    6   NA   NA
#> 
#> $c.prefs.smi
#>      [,1] [,2] [,3] [,4] [,5] [,6]
#> [1,]    1    1    1    1    1    1
#> [2,]    2    2    2    2    2    2
#> [3,]    3    3    3    4    4    4
#> [4,]    4    4    4    5    5    5
#> [5,]    5    5    5   NA   NA   NA
#> [6,]    6    6    6   NA   NA   NA
#> [7,]    7    7    7   NA   NA   NA
#> 
#> $s.prefs.hri
#>      A   B   C   D   E   F   G  
#> [1,] "x" "x" "x" "x" "x" "x" "x"
#> [2,] "y" "y" NA  "y" "y" NA  NA 
#> 
#> $c.prefs.hri
#>      x   y  
#> [1,] "A" "A"
#> [2,] "B" "B"
#> [3,] "C" "D"
#> [4,] "D" "E"
#> [5,] "E" NA 
#> [6,] "F" NA 
#> [7,] "G" NA 
#> 
#> $matchings
#>   matching college slots student sOptimal cOptimal sRank cRank
#> 1        1       x     1       A        1        1     1     1
#> 2        1       x     2       B        1        1     2     2
#> 3        1       x     3       C        1        1     3     3
#> 4        1       y     4       D        1        1     4     3
#> 5        1       y     5       E        1        1     5     4
#> 
#> attr(,"class")
#> [1] "hri"

## 7 students, 3 colleges with 3 slots each, incomplete preferences:
 hri(nStudents=7, nSlots=c(3,3,3), seed=21, s.range=c(1,3))
#> $s.prefs.smi
#>       [,1] [,2] [,3] [,4] [,5] [,6] [,7]
#>  [1,]    7    1    1    7    1    1    4
#>  [2,]    8    2    2    8    2    2    5
#>  [3,]    9    3    3    9    3    3    6
#>  [4,]    1   NA   NA    4   NA    4    7
#>  [5,]    2   NA   NA    5   NA    5    8
#>  [6,]    3   NA   NA    6   NA    6    9
#>  [7,]   NA   NA   NA   NA   NA    7   NA
#>  [8,]   NA   NA   NA   NA   NA    8   NA
#>  [9,]   NA   NA   NA   NA   NA    9   NA
#> 
#> $c.prefs.smi
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9]
#> [1,]    5    5    5    7    7    7    7    7    7
#> [2,]    6    6    6    6    6    6    4    4    4
#> [3,]    2    2    2    4    4    4    6    6    6
#> [4,]    3    3    3   NA   NA   NA    1    1    1
#> [5,]    1    1    1   NA   NA   NA   NA   NA   NA
#> 
#> $s.prefs.hri
#>       1  2  3  4  5 6  7
#> [1,]  3  1  1  3  1 1  2
#> [2,]  1 NA NA  2 NA 2  3
#> [3,] NA NA NA NA NA 3 NA
#> 
#> $c.prefs.hri
#>      1  2  3
#> [1,] 5  7  7
#> [2,] 6  6  4
#> [3,] 2  4  6
#> [4,] 3 NA  1
#> [5,] 1 NA NA
#> 
#> $matchings
#>   matching college slots student sOptimal cOptimal sRank cRank
#> 1        1       1     3       2        1        1     3     3
#> 2        1       1     1       5        1        1     1     1
#> 3        1       1     2       6        1        1     2     2
#> 4        1       2     4       7        1        1     1     1
#> 5        1       3     8       1        1        1     2     4
#> 6        1       3     7       4        1        1     1     2
#> 
#> attr(,"class")
#> [1] "hri"

 s.prefs <- matrix(c('S1', 'S2', NA,
                     'S3', 'S1', NA,
                     'S1', NA, NA,
                      NA, NA,NA,
                     'S2', 'S1', 'S5'),
                   nrow = 3, ncol = 5)
 # Note that we explicitly allow for the existence of entries refering to colleges
 # that do not exist. A warning is generated and the entry is ignored.
 colnames(s.prefs) <- c('A', 'B', 'C', 'D', 'E')
 c.prefs <- matrix(c('B', 'C','D', 'A',
                     'C', 'D', NA, NA,
                     'D', 'B', 'A', 'E'),
                   nrow = 4, ncol = 3)
 colnames(c.prefs) <- c('S1', 'S2', 'S3')
 hri(s.prefs=s.prefs, c.prefs=c.prefs, nSlots=c(3,3,3), check_consistency = TRUE)
#> Warning: Someone applied to a college (named S5) that has no ranking. This preference entries will be deleted! 
#> [1] "Dropped s.prefs column(s): D, E"
#> [1] "Dropped c.prefs column(s): S2"
#> $s.prefs.smi
#>      [,1] [,2] [,3]
#> [1,]    1    4    1
#> [2,]    2    5    2
#> [3,]    3    6    3
#> [4,]   NA    1   NA
#> [5,]   NA    2   NA
#> [6,]   NA    3   NA
#> 
#> $c.prefs.smi
#>      [,1] [,2] [,3] [,4] [,5] [,6]
#> [1,]    2    2    2    2    2    2
#> [2,]    3    3    3   NA   NA   NA
#> [3,]    1    1    1   NA   NA   NA
#> 
#> $s.prefs.hri
#>      A    B    C   
#> [1,] "S1" "S3" "S1"
#> [2,] NA   "S1" NA  
#> 
#> $c.prefs.hri
#>      S1  S3 
#> [1,] "B" "B"
#> [2,] "C" NA 
#> [3,] "A" NA 
#> 
#> $matchings
#>   matching college slots student sOptimal cOptimal sRank cRank
#> 1        1      S1     2       A        1        1     2     3
#> 2        1      S1     1       C        1        1     1     2
#> 3        1      S3     4       B        1        1     1     1
#> 
#> attr(,"class")
#> [1] "hri"
## --------------------
## --- Summary plots

## 200 students, 200 colleges with 1 slot each
 res <- hri(nStudents=200, nColleges=200, seed=12)
 plot(res)
 plot(res, energy=TRUE)
##}