matchingMarkets (version 0.2-1)

daa: Deferred Acceptance Algorithm for two-sided matching markets

Description

Finds the student-optimal matching in the college admissions problem or the men-optimal matching in the 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)

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.

edgelist

edgelist of matches

Minimum required arguments

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