matchingMarkets (version 0.1-1)

daa: Deferred Acceptance Algorithm for two-sided matching markets

Description

Finds the student-optimal matching in the http://en.wikipedia.org/wiki/Hospital_resident{college admissions} problem or the men-optimal matching in the http://en.wikipedia.org/wiki/Stable_matching{stable marriage} problem. Uses the Gale-Shapley (1962) Deferred Acceptance Algorithm with student/male offer based on given or randomly generated preferences.

Usage

daa(nStudents = ncol(s.prefs), nColleges = ncol(c.prefs), nSlots = rep(1,
  nColleges), s.prefs = NULL, c.prefs = 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 ith column containing student i's ranking over colleges in decreasing order of preference (i.e. most preferred first).

c.prefs

matrix of dimension nStudents x nColleges with the jth column containing college j's ranking over students in decreasing order of preference (i.e. most preferred first).

Value

• daa returns a list with the following elements.
• s.prefs
  student-side preference matrix.
• c.prefs
  college-side preference matrix.
• iterations
  number of interations required to find the stable matching.
• matches
  identifier of students/men assigned to colleges/women.
• match.mat
  matching matrix of dimension nStudents x nColleges.
• singles
  identifier of single (or unmatched) students/men.

References

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

Oswald, F. (2013). Deferred Acceptance Algorithm with male offer. GitHub Gist, Available at https://gist.github.com/floswald/1628636

Examples

######################
## Marriage problem ##
######################

## 3 men, 2 women, random preferences:
daa(nStudents=3, nColleges=2)

## 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)
daa(s.prefs=s.prefs, c.prefs=c.prefs)

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

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

## 7 students, 2 colleges with 3 slots each, given preferences:
s.prefs <- matrix(c(1,2, 1,2, 1,2, 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,6,7), 7,2)
daa(s.prefs=s.prefs, c.prefs=c.prefs, nSlots=c(3,3))