ttcc {matchingMarkets}

Top-Trading-Cycles and Chains Algorithm

Description

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).

Usage

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).

Author(s)

Thilo Klein, Alexander Sauer

References

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

Examples

## 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)
priority <- 1:12
ttcc(prefs = prefs, priority = priority)
## 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)