Top-Trading-Cycles Algorithm for the house allocation problem

Share:

Description

Finds the stable matching in the house allocation problem with existing tenants. Uses the Top-Trading-Cycles Algorithm proposed in Abdulkadiroglu and Sonmez (1999).

Usage

1
ttc(P = NULL, X = NULL)

Arguments

P

list of individuals' preference rankings over objects.

X

2-column-matrix of objects (obj) and their owners (ind).

Value

ttc returns a 2-column matrix of the stable matching solution for the housing market problem based on the Top-Trading-Cycles algorithm.

Author(s)

Thilo Klein

References

Abdulkadiroglu, A. and Sonmez, T. (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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
## generate list of individuals' preference rankings over objects
P <- list()
P[[1]] <- c(2,5,1,4,3)    # individual 1
P[[2]] <- c(1,5,4,3,2)    # individual 2
P[[3]] <- c(2,1,4,3,5)    # individual 3
P[[4]] <- c(2,4,3,1,5)    # individual 4
P[[5]] <- c(4,3,1,2,5); P # individual 5

## generate 2-column-matrix of objects ('obj') and their owners ('ind')
X <- data.frame(ind=1:5, obj=1:5); X

## find assignment based on TTC algorithm
ttc(P=P,X=X)