Top-Trading-Cycles Algorithm for a two sided matching problem

Implements the school matching algorithm proposed in Abdulkadiroglu and Sonmez (2003) for a matching problem in which both sides have preferences. Missing preferences are handled in the following ways: Suppose that a student only ranked colleges that are already matched to other students. This student is removed from the matching process and a list with all unmatchable students is printed. If full_return is set to TRUE, a vector with this students is returned as well. Now suppose during the matching process a student points to a college that still has capacities but does not rank any more students. We assume now that the college is indifferent over all other students (so we do not allow for free capacieties) and we match the student who wants to go there to the college.

ttc2(nStudents = ncol(s.prefs), nColleges = ncol(c.prefs),
  s.prefs = NULL, c.prefs = NULL, nSlots = NULL, priority = NULL,
  seed = NULL, full_return = FALSE)

Arguments

nStudents	integer indicating the number of students in the matching problem. Defaults to ncol(s.prefs).
nColleges	integer indicating the number of colleges in the matching problem. Defaults to ncol(c.prefs).
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).
nSlots	vector of length nColleges indicating the number of places (i.e. quota) of each college.
priority	(Optional) vector of length nStudents. Gives the prioirity ordering of the students in the search for cycles (Do not confuse it with the preferences!), if nothing is specified a random ordering is chosen.
seed	(Optional) integer setting the state for random number generation. Defaults to seed = NULL
full_return	(Optinal) If TRUE the return value is a list with the matching, the remaining seats and the unmatchable students is returned. Defaults to FALSE and only the matching is returned.

Value

ttc2 returns a data frame of the matching of students (ind) to colleges (obj) for the school market problem based on the Top-Trading-Cycles algorithm.

References

Abdulkadiroglu, A. and T. Sonmez (2003). School Choice: A Mechanism Design Approach. American Economic Review, 93 (3): 729-747.

Examples

##\dontrun{
## 1-a. Compare example from the Abdulkadiroglu et al. (2003) (in the Appendix, page 742-744)
## 1-b. Generate matrix of students' preference rankings over schools, a.k.a. Rank Order Lists (ROL)
s.prefs <- matrix(c(
                  2,1,3,4,
                  1,2,3,4,
                  3,2,1,4,
                  3,4,1,2,
                  1,3,4,2,
                  4,1,2,3,
                  1,2,3,4,
                  1,2,4,3),
                  byrow = FALSE, ncol = 8); s.prefs
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
#> [1,]    2    1    3    3    1    4    1    1
#> [2,]    1    2    2    4    3    1    2    2
#> [3,]    3    3    1    1    4    2    3    4
#> [4,]    4    4    4    2    2    3    4    3

## 1-c. Generate matrix of schools' preference rankings over students, a.k.a. Rank Order Lists (ROL)
c.prefs <- matrix(c(
                  1,2,3,4,5,6,7,8,
                  3,5,4,8,7,2,1,6,
                  5,3,1,7,2,8,6,4,
                  6,8,7,4,2,3,5,1),
                  byrow = FALSE, ncol = 4); c.prefs
#>      [,1] [,2] [,3] [,4]
#> [1,]    1    3    5    6
#> [2,]    2    5    3    8
#> [3,]    3    4    1    7
#> [4,]    4    8    7    4
#> [5,]    5    7    2    2
#> [6,]    6    2    8    3
#> [7,]    7    1    6    5
#> [8,]    8    6    4    1

## 1-d. Generate capacities
nSlots <- c(2,2,3,3)

## 1-e. Find assignment based on TTC algorithm
ttc2(s.prefs = s.prefs, c.prefs = c.prefs, nSlots = nSlots)
#>   ind obj
#> 1   1   2
#> 2   2   1
#> 3   3   3
#> 4   4   3
#> 5   5   1
#> 6   6   4
#> 7   7   2
#> 8   8   4

## 2-a. Generate college preferences with college 1 only ranking student 1
c.prefs <- matrix(c(
                   1,rep(NA,7),
                   3,5,4,8,7,2,1,6,
                   5,3,1,7,2,8,6,4,
                   6,8,7,4,2,3,5,1),
                   byrow = FALSE, ncol = 4); c.prefs
#>      [,1] [,2] [,3] [,4]
#> [1,]    1    3    5    6
#> [2,]   NA    5    3    8
#> [3,]   NA    4    1    7
#> [4,]   NA    8    7    4
#> [5,]   NA    7    2    2
#> [6,]   NA    2    8    3
#> [7,]   NA    1    6    5
#> [8,]   NA    6    4    1

## 2-b. Find assignment based on TTC algorithm
ttc2(s.prefs = s.prefs, c.prefs = c.prefs, nSlots = nSlots, priority = 1:8)
#>   ind obj
#> 1   1   2
#> 2   2   1
#> 3   3   3
#> 4   4   3
#> 5   5   1
#> 6   6   4
#> 7   7   2
#> 8   8   4

## If all schools have the same preferences the two sided ttc and the serial dictator yield
## the same outcome if the preferences are taken to be the prioirty order for the serial dictator

# Preferences are the same for all schools:
c.prefs <- matrix(c(
                  5,3,1,7,2,8,6,4,
                  5,3,1,7,2,8,6,4,
                  5,3,1,7,2,8,6,4,
                  5,3,1,7,2,8,6,4),
                  byrow = FALSE, ncol = 4)
priority <- c.prefs[,1]

match_ttc <- ttc2(s.prefs = s.prefs, c.prefs = c.prefs, nSlots = nSlots); match_ttc
#>   ind obj
#> 1   1   2
#> 2   2   2
#> 3   3   3
#> 4   4   3
#> 5   5   1
#> 6   6   4
#> 7   7   1
#> 8   8   4
match_sd <- rsd(prefs = s.prefs, priority = priority, nSlots = nSlots); match_sd
#>   ind obj
#> 1   1   2
#> 2   2   2
#> 3   3   3
#> 4   4   3
#> 5   5   1
#> 6   6   4
#> 7   7   1
#> 8   8   4
all(match_ttc == match_sd)
#> [1] TRUE
##}