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

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

iaa(nStudents = ncol(s.prefs), nColleges = ncol(c.prefs),
  nSlots = rep(1, nColleges), s.prefs = NULL, c.prefs = NULL,
  acceptance = "immediate", short_match = TRUE, seed = 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 `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.
short_match	(Optional) If `FALSE` then in the returned matching, free capacities will be indicated with 0 entries. If `TRUE`, free capacities will not be reported in the returned matching but an additonal data.frame is returned that contains free capacities. Defaults to `TRUE`.
seed	(Optional) integer setting the state for random number generation.

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.

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

##\dontrun{
## --------------------------------
## --- College admission problem

s.prefs <- matrix(c(1,2,3,
                    1,2,3,
                    1,2,3,
                    2,1,3,
                    2,1,3),
                  byrow = FALSE, ncol = 5, nrow = 3); s.prefs
#>      [,1] [,2] [,3] [,4] [,5]
#> [1,]    1    1    1    2    2
#> [2,]    2    2    2    1    1
#> [3,]    3    3    3    3    3
c.prefs <- matrix(c(1,4,2,3,5,
                    5,2,3,4,1,
                    1,2,3,4,5),
                  byrow = FALSE, ncol = 3, nrow = 5); c.prefs
#>      [,1] [,2] [,3]
#> [1,]    1    5    1
#> [2,]    4    2    2
#> [3,]    2    3    3
#> [4,]    3    4    4
#> [5,]    5    1    5
nSlots <- c(2,2,1)

## Boston mechanism
 iaa(s.prefs = s.prefs, c.prefs = c.prefs, nSlots = nSlots)$matchings
#>   college student
#> 1       1       1
#> 2       1       2
#> 4       2       4
#> 3       2       5
#> 5       3       3

## Gale-Shapley algorithm
 iaa(s.prefs = s.prefs, c.prefs = c.prefs, nSlots = nSlots, acceptance="deferred")$matchings
#>   college student
#> 1       1       1
#> 2       1       4
#> 4       2       2
#> 3       2       5
#> 5       3       3

## Same results for the Gale-Shapley algorithm with hri2() function (but different format)
 set.seed(123)
 iaa(nStudents=7, nSlots=c(3,3), acceptance="deferred")$matchings
#>   college student
#> 1       1       1
#> 2       1       2
#> 3       1       6
#> 5       2       4
#> 4       2       5
#> 6       2       7
 set.seed(123)
 hri2(nStudents=7, nSlots=c(3,3))$matchings
#> normal hri problem without couples
#>      student college
#> [1,]       1       1
#> [2,]       2       1
#> [3,]       4       2
#> [4,]       5       2
#> [5,]       6       1
#> [6,]       7       2
 ##}