iaa: Immediate Acceptance Algorithm (a.k.a. Boston mechanism) for...
In matchingMarkets: Analysis of Stable Matchings

Description Usage Arguments Value Minimum required arguments Author(s) References Examples

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.

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

`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 `j`th 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 `i`th 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.

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.

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.

Thilo Klein

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.

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

## Boston mechanism for 7 students, 2 colleges with 3 slots each
 set.seed(123)
 iaa(nStudents=7, nSlots=c(3,3))

## Gale-Shapley algorithm
 set.seed(123)
 iaa(nStudents=7, nSlots=c(3,3), acceptance="deferred")

## Same results for the Gale-Shapley algorithm with hri() function
 set.seed(123)
 hri(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)
 iaa(s.prefs=s.prefs, c.prefs=c.prefs, nSlots=c(3,3))

OpenJDK 64-Bit Server VM warning: Can't detect initial thread stack location - find_vma failed
$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

$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

$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"
$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

Warning message:
system call failed: Cannot allocate memory