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

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

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

`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.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
( |

.

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

Want to suggest features or report bugs for rdrr.io? Use the GitHub issue tracker. Vote for new features on Trello.