Description Usage Arguments Value Minimum required arguments Author(s) References Examples
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.
1 2 3 |
nStudents |
integer indicating the number of students (in the college admissions problem)
or men (in the stable marriage problem) in the market. Defaults to |
nColleges |
integer indicating the number of colleges (in the college admissions problem)
or women (in the stable marriage problem) in the market. Defaults to |
nSlots |
vector of length |
s.prefs |
matrix of dimension |
c.prefs |
matrix of dimension |
seed |
integer setting the state for random number generation. |
s.range |
range of two intergers |
c.range |
range of two intergers |
... |
. |
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
( |
.
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.
Thilo Klein
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | ## -----------------------
## --- 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))
## 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))
## --------------------
## --- Summary plots
## Not run:
## 200 students, 200 colleges with 1 slot each
res <- hri(nStudents=200, nColleges=200, seed=12)
plot(res)
plot(res, energy=TRUE)
## End(Not run)
|
Add the following code to your website.
For more information on customizing the embed code, read Embedding Snippets.