matchingMarkets (version 1.0-4)

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

Description

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.

Usage

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

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.

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.

verbose

logical. When set to TRUE, writes information messages on the console (recommended). Defaults to FALSE, which suppresses such messages.

Author

Thilo Klein, Alexander Sauer

References

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

Examples

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

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

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

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

## 2-b. Find assignment based on TTC algorithm
ttc2(s.prefs = s.prefs, c.prefs = c.prefs, nSlots = nSlots, priority = 1:8)

## 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_sd <- rsd(prefs = s.prefs, priority = priority, nSlots = nSlots)
all(match_ttc == match_sd)