Constraint model to produce all stable matchings in the hospital/residents problem with incomplete lists

Share:

Description

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.

Usage

1
2
3
hri(nStudents = ncol(s.prefs), nColleges = ncol(c.prefs), nSlots = rep(1,
  nColleges), s.prefs = NULL, c.prefs = NULL, seed = NULL, s.min = NULL,
  c.min = NULL)

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

seed

integer setting the state for random number generation.

s.min

integer, when specified produces incomplete preference lists with the length of each student's list randomly sampled from the range [s.min, nrow(s.prefs)].

c.min

integer, when specified produces incomplete preference lists with the length of each college's list randomly sampled from the range [c.min, nrow(c.prefs)].

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.

Author(s)

Thilo Klein

References

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

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

Examples

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
######################
## Marriage problem ## 
######################

## 3 men, 2 women, random preferences:
hri(nStudents=7, nColleges=6, seed=4)

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

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

## 7 students, 2 colleges with 3 slots each, random preferences:
hri(nStudents=7, nSlots=c(3,3), seed=21)

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