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

Value

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.

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.

Examples

##\dontrun{
## 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); s.prefs
#>      [,1] [,2] [,3] [,4] [,5] [,6]
#> [1,]    3    3    3    2    1    2
#> [2,]    2    5    1    5    3    4
#> [3,]    4    6   NA    6    2    5
#> [4,]    1   NA   NA    4   NA    6

## 1-b. Generate vector of house occupation objects ('obj') and their owners ('ind')
(houses <- 1:6)
#> [1] 1 2 3 4 5 6

## 1-c. Find assignment based on TTC algorithm
ttc(s.prefs = s.prefs, houses = houses, nHouses = 6, priority = 1:6)
#>    ind obj
#> 1    1   2
#> 21   2   5
#> 2    3   3
#> 11   4   6
#> 3    5   1
#> 22   6   4

## 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); s.prefs
#>      [,1] [,2] [,3] [,4] [,5]
#> [1,]    2    7    2    2    4
#> [2,]    6    1    1    4    3
#> [3,]    5    6    4    3    7
#> [4,]    1    5    7    6    1
#> [5,]    4    4    3    1    2
#> [6,]    3    3    6    7    5
#> [7,]    7    2    5    5    6
#> [8,]   NA   NA   NA   NA   NA

## 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); houses
#> [1]  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)
#>   ind obj
#> 1   1   2
#> 2   2   7
#> 3   3   1
#> 4   4   4
#> 5   5   3
##}