iaa {matchingMarkets}

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
)

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.

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.

Author(s)

Thilo Klein

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

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