matchingMarkets (version 1.0-2)

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

Description

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.

Usage

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
)

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

# NOT RUN {
##\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
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
nSlots <- c(2,2,1)

## Boston mechanism
 iaa(s.prefs = s.prefs, c.prefs = c.prefs, nSlots = nSlots)$matchings

## Gale-Shapley algorithm
 iaa(s.prefs = s.prefs, c.prefs = c.prefs, nSlots = nSlots, acceptance="deferred")$matchings

## 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
 set.seed(123)
 hri2(nStudents=7, nSlots=c(3,3))$matchings
 ##}
# }