Such programs have large databases of patient-donor pairs, where the donor is willing to donate a kidney in order to help the patient, but cannot do so due to medical incompatibility.
The OKE problem has many variants, which differ in the allowed size of each exchange, the objective function, and other factors.
They may also have priorities, determined e.g. by medical urgency or by the time the patient have waited in the transplantation queue.
Other common objectives are: Initially, the problem was studied without any bound on the length of the exchange cycles.
Abraham, Blum and Sandholm[5] show that, with unbounded cycle length, a maximum-cardinality and maximum-weight exchange can be found in polynomial time.
This requirement aims to ensure the individual rationality constraint - to avoid the risk that a donor refuses to donate after his patient has received a kidney.
Roth, Sonmez and Unver[6] study two extensions of the simple maximum-cardinality exchange: In later years, logistic improvements allowed the execution of larger number of simultaneous operations.
Finding a maximum-cardinality exchange is called, in graph theoretic terms, maximum cycle packing.
Anderson, Ashlagi, Gamarnik and Roth[8] present two algorithms for finding a maximum-cardinality packing into cycles of length at most k and chains of unbounded length: Early theoretic works in OKE assumed that, once a set of exchanges is determined, all of them will be executed.
For example, the medical examination done just before the transplant might reveal that the donor is incompatible with the patient, even though in the database they are registered as compatible.