ttc function

Top-Trading-Cycles Algorithm with existing tenants

Implements an algorithm for the house allocation problem proposed by Abdulkadiroglu and Sonmez (1999) for a matching problem in which there are both vacant houses and existing tenants.

ttc(
  nStudents = ncol(s.prefs),
  nHouses = length(houses),
  s.prefs,
  houses,
  priority = NULL,
  seed = NULL
)

Arguments

• nStudents: integer indicating the number of students. Defaults to ncol(s.prefs).
• nHouses: integer indicating the number of houses. Defaults to length(houses).
• s.prefs: matrix of dimension nHouses x nStudents with column j containing student jth ranking over houses in decreasing order of preferences (i.e. most preferred first).
• houses: vector of length nHouses which represents the occupation of the houses. Entry in k contains j if student j is living in house k and NA if house k is vacant.
• 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

Returns

ttc returns a data frame of the matching of students (int) to houses (obj) for the house allocation problem based on the Top-Trading-Cycles algorithm.

Examples

## 1-a. Generate matrix of individuals' preference rankings over objects,
## a.k.a. Rank Order Lists (ROL).
s.prefs <- matrix(c(3,2,4,1,        # ROL of student 1
                   3,5,6, NA,
                   3,1, NA,NA,
                   2,5,6,4,
                   1,3,2,NA,
                   2,4,5,6), nrow = 4, ncol = 6, byrow = FALSE)

## 1-b. Generate vector of house occupation objects ('obj') and their owners ('ind')
houses <- 1:6

## 1-c. Find assignment based on TTC algorithm
ttc(s.prefs = s.prefs, houses = houses, nHouses = 6, priority = 1:6)

## 2-a.Compare the example in the paper Abdulkadiroglu et al. (1999)
## on page 246-248 (section 5.1 An Example):
## generate matrix of students' preference rankings over houses, a.k.a. Rank Order Lists (ROL)
s.prefs <- matrix(c(2,6,5,1,4,3,7,NA,
                 7,1,6,5,4,3,2,NA,
                 2,1,4,7,3,6,5,NA,
                 2,4,3,6,1,7,5,NA,
                 4,3,7,1,2,5,6,NA), byrow = FALSE, ncol= 5)

## 2-b. Generate house occupation, so student 1 lives in house 1, ..., student 4 lives in house 4
## and the other houses are vacant.
houses <- c(1,2,3,4,NA,NA,NA,NA)

## 2-c. Generate priority ordering
priority <- 1:5

## 2-d. Find assigment
ttc(s.prefs = s.prefs, houses = houses, priority = priority)

References

Abdulkadiroglu, A. and T. Sonmez (1999). House Allocation with Existing Tenants. Journal of Economic Theory, 88 (2): 233-260.

Shapley, L. and H. Scarf (1974). On Cores and Indivisibility. Journal of Mathematical Economics, 1(1): 23-37.

Author(s)

Thilo Klein, Alexander Sauer