A Stylistic Queueing-Like Model for the Allocation of Organs on the Public List
Israel David and Michal Moatty-Assa
Department of Industrial Engineering and Management
Ben-Gurion University of the Negev, Beer-Sheba, Israel
Abstract
Allocating live organs for transplantation is a complex and intricate problem due to unsatisfied demand for live organs, physiological differences between candidates and donors, and the pursuit for equity amongst population groups with regard to waiting time and the likelihood of getting a transplant. Almost invariably, allocation rules world-wide are centered in the so-called “point system”. This heuristic policy has never been validated mathematically. More sophisticated policies have failed to find favor within the medical community. We present a simplified analytical model for the allocation system. The emphasis is on mathematical tractability and on establishing a platform for gaining insights into the complex dynamic candidate-donor system. We adopt a "utilitarian" objective function which maximizes clinical efficiency (life years beyond transplantation). Waiting time equity is provided by sorting the line of candidates by arrival time in the usual way, and then implementing the individually-optimal policy sequentially for these candidates. The model simplifies real-life in assuming only one "aggregate" genetic characteristic for each individual (recipient or donor), and in assuming a fixed, known, lifespan of a candidate under dialysis.
Keywords: organ-sharing, transplantation, dynamic programming.
Corresponding author: I. David. Fax: + 972 8 6472958 e-mail:
June 2009
1. Introduction
In analyzing the optimal allocation problem in the multi-candidate case, we follow Alalouf and David (2008) in adopting policies which are based on the following principles:
1. "FIFT" underlying queue: an arriving kidney is offered to the candidate who is at the head of the line. This line is sorted by the time of arrival (registering to the system). If the candidate declines the offer (see 2 below), this offer is passed to the next candidate in the line, and so forth. This is to follow the FIFO famous rule in Queueing theory (in the realm of transplants it is FIFT – First Come First Transplanted). This rule is the "most equitable", or fair, in terms of waiting times.
2. A candidate who is offered acts according to the individually optimal policy along the lines described in Chapter 2 above. Thus, she will maximize a utilitarian objective function in taking into account the various factors which affect her status, such as her position in the queue, the gene classification of the candidates standing in front of her, and her own gene classification. (Note that the optimization problem of the second down to the last candidate in the line is more complicated than that of the first one.)
It is not claimed, nor is it generally true, that the above policy is the optimal utilitarian socially optimal policy. (For one, it ignores "golden opportunities" for candidates down the line who possess rare antigens.) However, in the quest for policies which are simultaneously "efficient" and "fair", the above policy seems promising. Altogether, it seems to have a potential of analytical tractability. To this end, however, we make a few concessions in the modeling. These simplifying assumptions will be assumed to hold true throughout the rest of this work. There are two simplifying assumptions, and they relate to the candidates' life time, which is assumed constant, and the number of possible mismatches, which is only two.
2. Model definition
We assume that each person, either a candidate or a donor, is characterized by only one genetic characteristic. (That is, as if there is only one relevant HLA site, which contains one antigen drawn from a given antigen distribution, or, alternatively, the existing antigen HLA structure may be aggregated in some way to be considered one trait.) Thus, from now on, the value of the reward X is high (denoted by R) in case of a match between the antigen (single characteristic) of the donor (offer) to that of the recipient (candidate), and low otherwise (and then it is denoted by r). The distribution of X takes then the form depicted in Table 1.
Table 1: the reward (in life years) from a kidney of both types
Mismatch- Level / /"A" (I = 0) / R / p
"B" (I = 1) / r /
p of Table 1 is the frequency of the antigen of the given candidate. It is one of the values of , which, as in Chapter 2, constitute the population antigen distribution.
The kidney arrival process is again Poisson, and so is the arrival process of new candidates. These two processes are assumed statistically independent. The parameter of the candidate arrival process is , and that of the kidney process is . However, we use simply , at times, for either parameter, when no confusion arises given the context.
As regards the lifetime expectancy of candidates, we assume a deterministic lifetime of length T years, identical for all candidates under dialysis treatment. (In the final, most complex model that we analyze, we relax this last identity assumptions, and candidates have individual life-spans while waiting, etc.). Once a candidate is transplanted, she may live forever as far as our model is concerned (this means that there is no "feedback" to the queue and that each candidate contributes R, r, or 0 to the total objective. The latter value relates to the unfortunate event of death while waiting for transplant).
We denote , the expected profit from a random kidney offer for a candidate with antigen frequency p. We recall that the inter-arrival times of kidneys (offers) are independent random variables with exponential distribution. The number of offers arriving to the system in a time interval of length is Poisson-distributed with a parameter proportional to t.
3. The case of one candidate in the system (n = 1)
This section is devoted to redoing Chapter 2, namely, to explore the individually optimal candidate policy, under the new assumptions of our model. As our model assumes only one "aggregate" antigen, only one critical time needs to be computed – the one after which both the best and the second-best offers are acceptable. We are able to present closed-form expressions both for this critical time and for the functional form of the value function of the problem.
We are at the footsteps of David and Yechiali (1985) to formulate a typical dynamic programming stopping model, to maximize the “utilitarian” objective function of the candidate. Mathematically, it is the expected value of the offer she accepts within her lifetime .
We define:
– Value of the random kidney that arrives, i.e the random reward (measured in life years) of transplanting the kidney – in view of the waiting single candidate.
Y – Lifetime of the candidate, (Deterministic).
S – Inter-arrival time of offers. .
– "The value of the problem", that is, the optimal expected reward gained from time when an offer arrives, onwards.
– The optimal expected future reward attained if rejecting an offer at time .
In defining a bivariate real function
, (1)
for and a realization x of X, we have:
We also see from (1) that serves as a "control limit" function. (It is in terms of David and Yechiali (1985).)
The optimal critical time for the single candidate in the new model
Intuitively speaking, all that is needed to define the optimal policy, is to find the critical moment , denoted by, in which the candidate decides to compromise and accept every possible kidney. To formalize, we start with the following lemma:
Lemma 1: is continuous on , and is monotone decreasing (to zero) over that region.
Proof: In David and Yechiali (1985) continuity and decreasing monotonicity are proven for lifetime distributions which are IFR. Now, a cumulative distribution function G is IFR (in the most general definition of this notion) if
decreases in t (2)
(The LHS expression in (2) is the conditional probability to live x more units of time.)
Now it may be easily checked that (2) holds in our case of deterministic lifetime:
So
for . It is then clearly nonincreasing in (taken over ).
is obvious. Q.E.D
Lemma 1, together with Eq. (1), gives rise to Figure 1 below.
Figure 1: The objective function of the first candidate for all t
As mentioned, an optimal decision policy will be one that maximizes the candidate’s total expected reward. The compromising point of the candidate will be the moment that the candidate is indifferent between accepting a “bad” offer, or surely accepting the next offer without conditions (no matter if the offer is “bad” or “good”). In other words, the compromising point is when the future expected reward equals r - the minimum reward value a candidate can receive.
To find an explicit solution for , we rely on the continuity of at , and on the fact that (see again Figure 1) we can explicitly express in the region (in this region both types of kidneys are optimally acceptable). If we denote by N the discrete random variable that indicates the number of offers (kidneys) arriving in the time interval , then N has a Poisson distribution with parameter . Thus,
(3)
On the other hand, by continuity,
. (4)
Equating the RHS of (3) and of (4), and further denoting by the expected offer value , we get:
(5)
having bounded by zero we finally get:
(6)
Solving for the value function U(t)
By the definition of V and U (see subsection 3.2.1 above) and by conditioning on the next inter-arrival time (s), we have
(7)
(We have made use of the continuous "Law of Total Expectation").
Theorem 1 (Explicit solution of ):
a. For
b. For we have , where
. has been specified in Eq.(6).
Proof: Part a is clear from Eq. (3) and the discussion which preceeds it (see Figure 1 again). To prove ., let be in the time interval . Then:
,
the max being if , and r otherwise. Making the change of variables in (7), we get:
.
Expanding the integrals:
Denoting
, (8)
we get:
. (9)
An integral equation of the form
(10)
is called a Volterra equation of the second type. (See e.g. Hildebrand 1965, or Arfken 1985, p.865). Here, as in our case, is the unknown, is a known function and so is (which is called the kernel of the integral). This equation admits an explicit solution in terms of the so-called resolvent kernel. However, more specifity may be achieved in our specific case when the kernel involves the exponential function (we follow here Polyanin and Manzhirov 1998, see also the internet site http://eqworld.ipmnet.ru/en/solutions/ie/ie-toc2.htm). Rewriting (9) as
(11)
we get the form
(12)
for which the explicit solution is:
. (13)
It is only left then to plug the various expressions of our case, see (11), into (13). We get:
(14)
We substitute (see (8)) in the integrand in (14) and get the following expression for the integral which appears in the R.H.S of (14):
(15)
Both terms are immediate to integrate. The first integral is expanded as:
.
In sum, the first integral in (15) is:
(16)
The second integral is treated in a similar manner:
Substituting this final expression, along with Eq. (16), in Eq. (14), we get:
We define two auxiliary functions:
Upon rewriting the last expression for with and , plugging into it of (8) again, and with algebric manipulations we get:
(17)
(note that ). Q.E.D.
Observing that (see Eq. (5)), and substituting in (17) yield the value r, which attests to the continuity of V at . Finally, We recall that for For in the time interval we then have , and for in the time interval we have . Thus, Theorem 1 also specifies explicitly "the value of the problem" U(t) for all
In particular, we may wish to obtain U(0). If , U(0)=. In the more fortunate case, . Observing that and using Eq. (17) we get:
. (18)
Expression (18) satisfies , with equality for , as may be expected. Furthermore, the R.H.S. of (18) boils down to if . Monotonicity of in T, in r, in p and in l may also be easily established. Figure 2 below depicts for the fixed values and (note that the "monetary" values R and r could have been scaled so that one of them would equal unity).
4. The case of two candidates in the system (n = 2)
Problem reformulation - the case of two candidates in the system
In this section we deal with the case of two candidates in the system. In this case, offers are first presented to the first candidate and if the offer is rejected it is offered to the next candidate (successor). Our goal is to find the optimal decision policy for each candidate. It is obvious that the policy of the first candidate will not be different from the optimal policy presented in the previous section, because the coming offers are not affected by the second candidate. Thus we focus on finding the optimal decision policy of the second candidate, taking into consideration the new element in her problem, that is, the behavior of a new "player". Not only are we able to present explicit solutions for this case as well, but the analysis of sheds important light on the case of general n.
Further definitions:
On top of the model definition (see 3.1) we introduce the arrival times of the first and second candidate respectively. Without loss of generality, we set . All quantities and functions of section 3.2 are now doubled, with appropriate subscripts 1 or 2, to apply for the two candidates, in the straightforward manner. Note, however that and are the frequencies of antigens of the first and second candidate, and is the probability that an arriving kidney which is eligible to the i’th candidate in time-interval I would be of her own type. We use and . The donor kidneys arrival rate is denoted (as in the previous section simply by . We let be the (variable) arrival rate experienced by the second candidate. (Indeed, this candidate “sees” a non-homogeneous Poisson process of coming offers, see below). The symbol will denote any of the possible constant values of , pertinent to a sub-interval I. Finally, for the sake of clarity only, we take (this assumption will be relaxed in the next section where individual fixed lifetimes are permitted). In this section represents, as before, the “compromising” time of the first candidate, which is taken here as a known parameter. Furthermore, we skip here some desirable monotonicity and continuity proofs for the second candidate threshold function and value function. We are left then with the problem of determining , the critical time for the second candidate.