Top-Trading-Cycles and Chains Algorithm

Implements the Top Trading Cycle and Chains algorithm proposed by Roth et al. (2004) for the kidney exchange problem. The algorithm requires a rule to determine which chain will be used if there is more than one possibility. The chosen rule is to search for the longest chain and remove it from the problem (even the first kidney which was unassigned).

ttcc(nPatients = ncol(prefs), prefs, priority = NULL, seed = NULL)

Arguments

nPatients	integer indicating the number of patient/donor-pairs in the matching problem. Defaults to ncol(prefs).
prefs	matrix of dimension (nPatients + 1) x nPatients with column j containg patients jth ranking over kidneys in decreasing order of preferences (i.e. most preferred first). An entry with value (nPatients +1) indicates that the patient prefers the waiting list to all kidney below in his ranking (therefore they do not matter and can be neglected/NA).
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

ttcc returns a list with the matching and a vector containing the patients who are assigned to the waiting list. The matching comprises a data frame of the operations to be performed between patient-donor pairs (ind-obj).

References

Roth, A.; T. Sonmez; U. Unver (2004). Kidney Exchange. Quarterly Journal of Economics, 119 (2): 457-488.

Examples

##\dontrun{
## Compare Example 1 from Roth et al. (2004) on page 469 - 475
## generate matrix of patients' preference rankings over kidneys, a.k.a. Rank Order Lists (ROL)

prefs <- matrix(c( 9,10, 1,NA,NA,NA,NA,
                  11, 3, 5, 6, 2,NA,NA,
                   2, 4, 5, 6, 7, 8,13,
                   5, 9, 1, 8,10, 3,13,
                   3, 7,11, 4, 5,NA,NA,
                   3, 5, 8, 6,NA,NA,NA,
                   6, 1, 3, 9,10, 1,13,
                   6, 4,11, 2, 3, 8,NA,
                   3,11,13,NA,NA,NA,NA,
                  11, 1, 4, 5, 6, 7,13,
                   3, 6, 5,11,NA,NA,NA,
                  11, 3, 9, 8,10,12,NA),
              byrow = FALSE, ncol = 12); prefs
#>      [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [,12]
#> [1,]    9   11    2    5    3    3    6    6    3    11     3    11
#> [2,]   10    3    4    9    7    5    1    4   11     1     6     3
#> [3,]    1    5    5    1   11    8    3   11   13     4     5     9
#> [4,]   NA    6    6    8    4    6    9    2   NA     5    11     8
#> [5,]   NA    2    7   10    5   NA   10    3   NA     6    NA    10
#> [6,]   NA   NA    8    3   NA   NA    1    8   NA     7    NA    12
#> [7,]   NA   NA   13   13   NA   NA   13   NA   NA    13    NA    NA
priority <- 1:12
ttcc(prefs = prefs, priority = priority)
#> $matching
#>    ind obj
#> 1    1   9
#> 2    2  11
#> 3    3   2
#> 4    4   8
#> 5    5   7
#> 6    6   5
#> 7    7   6
#> 8    8   4
#> 9   10   1
#> 10  11   3
#> 11  12  12
#> 
#> $waiting_list
#> [1] 9
#> 
## The final matching differs slightly because in Round 3 another chain is chosen due to a different
## decision rule (compare Figure 3, p472. Here W1 instead of W2 is chosen)
##}