# ttc: Top-Trading-Cycles Algorithm for the house allocation problem In matchingMarkets: Analysis of Stable Matchings

## 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` matrix of individuals' preference rankings (Rank Order Lists) over objects. `X` 2-column-matrix of objects (`obj`) and their owners (`ind`).

## Value

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

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 matrix of individuals' preference rankings over objects, a.k.a. Rank Order Lists (ROL) P <- matrix(c(2, 5, 1, 4, 3, # ROL of individual 1 1, 5, 4, 3, 2, # ind 2 2, 1, 4, 3, 5, # ind 3 2, 4, 3,NA,NA, # ind 4 4, 3, 1, 2,NA), # ind 5 byrow=FALSE, nrow=5); P ## generate 2-column-matrix of objects ('obj') and their owners ('ind') X <- data.frame(ind=1:5, obj=5:1); X ## find assignment based on TTC algorithm ttc(P=P,X=X) ```

### Example output

```OpenJDK 64-Bit Server VM warning: Can't detect initial thread stack location - find_vma failed
[,1] [,2] [,3] [,4] [,5]
[1,]    2    1    2    2    4
[2,]    5    5    1    4    3
[3,]    1    4    4    3    1
[4,]    4    3    3   NA    2
[5,]    3    2    5   NA   NA
ind obj
1   1   5
2   2   4
3   3   3
4   4   2
5   5   1
ind obj
1    1   5
11   2   1
12   3   3
2    4   2
21   5   4
Warning message:
system call failed: Cannot allocate memory
```

matchingMarkets documentation built on Jan. 11, 2018, 3 p.m.