Immediate Acceptance Algorithm (a.k.a. Boston mechanism) for two-sided matching markets

Usage

iaa(nStudents = ncol(s.prefs), nColleges = ncol(c.prefs), nSlots = rep(1,
  nColleges), s.prefs = NULL, c.prefs = NULL, acceptance = "immediate")

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).
acceptance
if acceptance="deferred" returns the solution found by the student-proposing Gale-Shapley deferred acceptance algorithm; if acceptance="immediate" (the default) returns the solution found by the Boston mechanism.

Value

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

matchings
edgelist of matches

singles
identifier of single (or unmatched) students/men.

Description

Finds the optimal assignment of students to colleges in the college admissions problem based on the Boston mechanism. The option acceptance="deferred" instead uses the Gale-Shapley (1962) Deferred Acceptance Algorithm with male offer. The function works with either given or randomly generated preferences.

Minimum required arguments

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

Kojima, F. and M.U. Unver (2014). The "Boston" school-choice mechanism. Economic Theory, 55(3): 515--544.

Examples

## -------------------------------- ## --- College admission problem ## Boston mechanism for 7 students, 2 colleges with 3 slots each set.seed(123) iaa(nStudents=7, nSlots=c(3,3))
$s.prefs [,1] [,2] [,3] [,4] [,5] [,6] [,7] [1,] 1 1 2 2 2 2 2 [2,] 2 2 1 1 1 1 1 $c.prefs [,1] [,2] [1,] 1 5 [2,] 6 4 [3,] 2 7 [4,] 7 3 [5,] 4 6 [6,] 5 2 [7,] 3 1 $iterations [1] 3 $matchings college student 1 1 1 2 1 2 3 1 6 5 2 4 4 2 5 6 2 7 $singles [1] 3
## Gale-Shapley algorithm set.seed(123) iaa(nStudents=7, nSlots=c(3,3), acceptance="deferred")
$s.prefs [,1] [,2] [,3] [,4] [,5] [,6] [,7] [1,] 1 1 2 2 2 2 2 [2,] 2 2 1 1 1 1 1 $c.prefs [,1] [,2] [1,] 1 5 [2,] 6 4 [3,] 2 7 [4,] 7 3 [5,] 4 6 [6,] 5 2 [7,] 3 1 $iterations [1] 3 $matchings college student 1 1 1 2 1 2 3 1 6 5 2 4 4 2 5 6 2 7 $singles [1] 3
## Same results for the Gale-Shapley algorithm with hri() function set.seed(123) hri(nStudents=7, nSlots=c(3,3))
$s.prefs.smi [,1] [,2] [,3] [,4] [,5] [,6] [,7] [1,] 1 1 4 4 4 4 4 [2,] 2 2 5 5 5 5 5 [3,] 3 3 6 6 6 6 6 [4,] 4 4 1 1 1 1 1 [5,] 5 5 2 2 2 2 2 [6,] 6 6 3 3 3 3 3 $c.prefs.smi [,1] [,2] [,3] [,4] [,5] [,6] [1,] 1 1 1 5 5 5 [2,] 6 6 6 4 4 4 [3,] 2 2 2 7 7 7 [4,] 7 7 7 3 3 3 [5,] 4 4 4 6 6 6 [6,] 5 5 5 2 2 2 [7,] 3 3 3 1 1 1 $s.prefs.hri [,1] [,2] [,3] [,4] [,5] [,6] [,7] [1,] 1 1 2 2 2 2 2 [2,] 2 2 1 1 1 1 1 $c.prefs.hri [,1] [,2] [1,] 1 5 [2,] 6 4 [3,] 2 7 [4,] 7 3 [5,] 4 6 [6,] 5 2 [7,] 3 1 $matchings matching college slots student sOptimal cOptimal sRank cRank 1 1 1 1 1 1 1 1 1 2 1 1 3 2 1 1 3 3 3 1 1 2 6 1 1 5 2 4 1 2 5 4 1 1 2 2 5 1 2 4 5 1 1 1 1 6 1 2 6 7 1 1 3 3 attr(,"class") [1] "hri"
## 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) iaa(s.prefs=s.prefs, c.prefs=c.prefs, nSlots=c(3,3))
$s.prefs [,1] [,2] [,3] [,4] [,5] [,6] [,7] [1,] 1 1 1 1 1 1 1 [2,] 2 2 2 2 2 2 2 $c.prefs [,1] [,2] [1,] 1 1 [2,] 2 2 [3,] 3 3 [4,] 4 4 [5,] 5 5 [6,] 6 6 [7,] 7 7 $iterations [1] 3 $matchings college student 1 1 1 2 1 2 3 1 3 4 2 4 5 2 5 6 2 6 $singles [1] 7