Thomas Masanet

Beno Ît

D E Lorraine

Agence De

TOWARD ORGAN SHORTAGE RESILIENT ALLOCATION POLICIES USING REAL-TIME QUEUEING MODELS FOR LIVER TRANSPLANTATION

We report in this paper on the potential interest of real-time queueing models to optimize organ allocation policies. We especially focus on building organ shortage resilient policies in terms of equity, as we experienced differential impact of the COVID epidemic organ shortage on transplant access, according to the cause of liver failure. Patient's death on the waiting list or dropout for being too sick, resulting from the absence of a timely available organ, is chosen as the main equity metric. Results obtained with the composite allocation score used in France is challenged against the so-called Early Simulated Deadline First (ESDF) real-time queueing discipline, under increasing levels of organ shortage, by extensive simulations. The ESDF policy is a variant of the well-know Earliest Deadline First (EDF) policy, which was shown as optimal in various contexts in the queueing literature. In the present case, the time to the deadline represents the remaining life duration of patients -which is of course unknown. So we propose to simulate a fictional life-duration, and give priority to the earliest simulated deadline. This leads to a simple and comprehensive representation of the system at hand by a Markov process. Our simulation results clearly show that the ESDF policy allows to maintain equity between indications, conversely to the scoring policy, which was not resilient to increasing levels of organ shortage.

1. Introduction 1.1. Liver allocation in France. Due to organ shortage, the allocation of organs for transplantation is a worldwide sensitive issue. Organs for transplantation are considered as scarce resources, as the needs exceed graft offer. For vital organs such as Heart or Liver, the absence of a timely available organ leads to the patient's adverse outcomes on the waiting list: death or dropout for being too sick for transplantation (DDTS). Organ allocation policies try to answer to the various medical needs of transplant candidates in a suitable, efficient, equitable and traceable manner. To achieve the best use of this scarce resource, many countries moved from centre-based to patient-based allocation policies. In some cases, sequential allocation priorities related to patients conditions can be defined, as is the case for example for patients with fulminant hepatitis. In most cases, the overlaps of patients' medical conditions do not permit to rank patients according to simple categorical criteria. In this situation, multivariate allocation scores have been demonstrated to offer efficient tools, both to support patient-based allocation policies and to optimise organ allocation in weighting the influence of various, and sometimes contradictory, equity, efficacy and feasibility allocation criteria. The Model for End-stage Liver Disease (MELD) has been demonstrated to be a good predictor of risk of death for cirrhotic patients [START_REF] Wiesner | Meld and peld: application of survival models to liver allocation[END_REF], [START_REF] Merion | The survival benefit of liver transplantation[END_REF] and is widely used to prioritise liver transplant candidates. It has also been demonstrated to identify patients with an individual benefit from Liver Transplantation (LTx), and permits to avoid too early transplantation, when the risks related to the liver disease is lower than the risk of tranpslant surgical procedure [START_REF] Merion | The survival benefit of liver transplantation[END_REF].

In France, the Agence de la biomédecine (ABM) is responsible for the allocation of organ and the management of the waiting lists. ABM, in collaboration with transplant professionals and patients associations defines and implement the organ allocation policy. The Liver allocation policy comprises a national "Super-Urgency" priority for patients with fulminant hepatitis or early primary graft non function [START_REF] Adam | Liver allocation for emergency patients in france: needs and limits of a high urgency priority[END_REF]. Liver are allocated to patients sharing the same blood type with the donor. In absence of SU patients, the liver allocation score (LAS) is computed for each active patient on the national waiting list [START_REF] Jacquelinet | Règles d'attribution des greffons hépatiques[END_REF][START_REF] Calmus | Nouvelles règles d'attribution des greffons hépatiques[END_REF]. LAS assigns them a priority rank and therefore allows the allocation of an organ to the patient with the highest score [START_REF]Handbook of liver allocation in france[END_REF]. The LAS takes into account the MELD score for cirrhotic patients (CIRRH), combined with the time spent on the waiting list for hepatocellular carcinomas (HCC) and other indications (OTHER). To handle logistic constraints, the final score includes an interaction between the LAS and the distance between organ procurement and transplant centers using a gravity model [START_REF] Bayer | Removing administrative boundaries using a gravity model for a national liver allocation system[END_REF]. For some indications, referred as to "MELD exceptions" (MXP), MELD does not reflect properly the risk of death on the waiting list. According to their condition, these patients are granted with 650 to 800 additional points to the score within 0, 3, 6 or 9 months, by expert advice. The exact, or approximate, analysis of the process under study often leads to the construction of efficient tools to control, optimize or at least, simulate the system in the long run. To do so, the central question is that of the construction of efficient service disciplines (that act as a control of the system at hand) that can be implemented sequentially, so as to optimize a given performance parameter. In the so-called real-time context, the incoming elements have a bounded life-time, or patience in the system, and the timely execution is of critical importance. Of particular interest, in such context, is the Earliest deadline first (EDF) policy, prioritizing the customers in line having the least remaining patience time (time to the deadline) at current time. EDF policies can also model reneging, offering a mean to handle items with elapsed deadlines.

The outcome of patients in the transplant waiting list typically stands in the field of applications of such real-time queueing systems. In the present settings, the patience time stand for the life duration of the patients, and the reneging, for their death on the waiting list, when their life duration has elapsed. 1.4. Outline. In this work, we show that a practically relevant variant of the EDF policy, which we call ESDF (for Earliest Simulated Deadline First) allows to efficiently control the system at hand, by providing a simple representation of the system, that is amenable to extensive simulations. Second, we show that ESDF tends to be more organ shortage-resilient in terms of equity between indications, in comparison with the more classical Score policy.

The remainder of this paper is organized as follows. In Section 2, we describe the population and study design for our simulations. Then, in Section 3 we present in detail the mathematical model at hand, namely, a bipartite stochastic matching model with impatient items, as recently introduced in [START_REF] Aveklouris | Matching impatient and heterogeneous demand and supply[END_REF][START_REF] Jonckheere | Generalized max-weight policies in stochastic matching[END_REF][START_REF] Masanet | Perfect sampling of stochastic matching models with reneging[END_REF][START_REF] Aveklouris | A fluid approximation for a matching model with general reneging distributions[END_REF], ruled by the original ESDF matching policy. In Section 4, we detail the calibration of the parameters of our mathematical model and in Section 5, we describe our simulation procedure. Our results are presented and analyzed in Section 6. Section 7 concludes this work. Additional materials (mathematical developments and the presentation of additional algorithms in our simulation scheme) are presented in Section 8.

Population and study design

2.1. Population. This study used aggregated data from the French national database CRISTAL. CRISTAL is a national database initiated in 1996 and administered by the ABM that prospectively collects data on all organ transplant candidates in France along with their outcomes [START_REF] Strang | The french organ transplant data system[END_REF]. The ABM is also in charge of the evaluation of all transplant activity including outcome of patients on the waiting list and after transplantation. Data are entered into the registry by each center and updated at least every three months. Data collection is mandatory. Withdrawal from the waiting list and patient death are prospectively notified. The study was conducted according to the French law indicating that research studies based on the national registry CRISTAL are part of the transplant assessment activity and do not require institutional reviewboard approval. These data were used as input for the new mathematical model presented in this paper and for the survival times generation (analyses made by the ABM). Inverse transformation method was used to simulate the individual patient survival time on the waiting list [START_REF]Lsam user's guide[END_REF], [START_REF] Bender | Generating survival times to simulate cox proportional hazards models[END_REF]. We also used a cox model and the inverse transformation method to simulate the transition time to cirrhosis or others status to MELD exception status.

Study design.

To mimic the impact of changes in organ shortage, we simulate the outcome of patients under various levels of liver donors. LTx and DDTS crude rates were selected as the evaluation endpoint. They were computed from the incident cohort of newly enlisted patients during the first 2 years of the study period. We'll observed the outcome of those patients on the whole 10 years study period.

We simulate 8 scenarios: 2 matching policies (described in section 3.3) and 4 levels of organ shortage defined by the decrease in the percent of liver donors available (0%, 15%, 30% and 50%). Each scenario is performed 10 times to average the variations inherent to the random settings.

Mathematical model

3.1. A matching model. We consider a general stochastic matching model (GM), as was defined in [START_REF] Mairesse | Stability of the stochastic matching model[END_REF] (extending e.g. the classical references [START_REF] Caldentey | FCFS infinite bipartite matching of servers and customers[END_REF], [START_REF] Adan | Exact FCFS matching rates for two infinite multitype sequences[END_REF] and [START_REF] Bušić | Stability of the bipartite matching model[END_REF] to single arrivals): 'items' (donors and recipients) enter one by one in the system, and each of them belongs to a determinate class. We let V be the set of classes, and fix a compatibility graph G = (V, E) between classes. Upon arrival, any incoming item of class, say, i ∈ V is either matched with an item present in the system, of a class j such that i shares an edge with j in G, if any, or if no such item is available, it is stored in the system to wait for its match. Whenever several possible matches are possible for an incoming item i, a matching policy Φ determines what is the match of i without ambiguity. Each matched pair (organ/recipient) departs the system right away, representing the transplant between the two considered item.

Recipients and donors classes. The set of classes is denoted by V = D ∪ R, where D is the set of donor classes, and R is the set of recipient classes. For any i ∈ V , we suppose that the inter-arrival times (i.e. the durations between two consecutive arrivals) are IID (Independants and identically distributed) with the distribution ξ i .

Each system corresponds to one single blood group, so there is a single donor class d, i.e., we set D = {d}. Each class in R is characterized by a triplet (a 1 , a 2 , a 3 ), where:

(1) a 1 gives the Indication of the patient. They are 4 possible indications which indicate the nature of the patient affection and which are denoted by the following terms: CIRRH for cirrhotic patients, HCC for hepatocellular carcinoma patients, MXP for patients with a MELD exception and OTHER for every other possibility.

(2) a 2 is the MELD class of the patient. There are 6 different MELD classes which regroup different intervals of possible MELD value for patients: [START_REF] Aveklouris | Matching impatient and heterogeneous demand and supply[END_REF][START_REF] Dertouzos | Control robotics: The procedural control of physical processes[END_REF], [START_REF] Doytchinov | Real-time queues in heavy traffic with earliest-deadline-first queue discipline[END_REF][START_REF] Masanet | Perfect sampling of stochastic matching models with reneging[END_REF], [START_REF] Merion | The survival benefit of liver transplantation[END_REF][START_REF] Wiesner | Meld and peld: application of survival models to liver allocation[END_REF] [START_REF] Aveklouris | Matching impatient and heterogeneous demand and supply[END_REF][START_REF] Dertouzos | Control robotics: The procedural control of physical processes[END_REF], [START_REF] Doytchinov | Real-time queues in heavy traffic with earliest-deadline-first queue discipline[END_REF][START_REF] Masanet | Perfect sampling of stochastic matching models with reneging[END_REF] and [START_REF] Merion | The survival benefit of liver transplantation[END_REF][START_REF] Wiesner | Meld and peld: application of survival models to liver allocation[END_REF].

(3) a 3 (0 or 1) indicates if the patient awaits a MELD exception. A MELD exception is given to the patients whose life quality is greatly impacted by their condition. The decision to transplant patients with MELD exception is then based on life quality, more than survival considerations. OTHER and CIRRH patients with MELD classes [START_REF] Aveklouris | Matching impatient and heterogeneous demand and supply[END_REF][START_REF] Dertouzos | Control robotics: The procedural control of physical processes[END_REF], [START_REF] Doytchinov | Real-time queues in heavy traffic with earliest-deadline-first queue discipline[END_REF][START_REF] Masanet | Perfect sampling of stochastic matching models with reneging[END_REF] and [START_REF] Merion | The survival benefit of liver transplantation[END_REF][START_REF] Wiesner | Meld and peld: application of survival models to liver allocation[END_REF]

have R = R 1 ⊔ R 2 .
As the patients and organs we consider all have the same blood type, all the patients in R and all the donors in D are compatible. Nevertheless, as patients who are awaiting a MELD exception cannot be transplanted, the set E of possible matchings is given by E = R 1 × D. In other words, the compatibility graph we consider in this work is the bipartite graph

G = (D ∪ R, R 1 × D).
Patience times. To stand for the timely constraint on the recipient's end, and in line with the recent extensions proposed in [START_REF] Aveklouris | Matching impatient and heterogeneous demand and supply[END_REF], [START_REF] Jonckheere | Generalized max-weight policies in stochastic matching[END_REF], [START_REF] Masanet | Perfect sampling of stochastic matching models with reneging[END_REF] and [START_REF] Aveklouris | A fluid approximation for a matching model with general reneging distributions[END_REF], the GM model is enriched with an impatience parameter. Specifically, we suppose that a subset R ′ ⊆ R of the classes of recipients are assigned a patience time upon arrival. If the considered item has not been matched at the end of its patience time, namely, the corresponding recipient did not find a transplant, then it leaves the system forever. The initial patience times of items of class i ∈ R ′ are IID, from a probability distribution µ i . Likewise, for all i ∈ R ′ , we assume that all elements of class i are assigned predictive, or simulated patience times, which are independent of the actual patience times, and IID with the distribution µ ′ i (which is for most classes, but not all, equal to µ i ). These fictional patience times will be needed hereafter, to define a particular class of matching policies. If the predictive patience of a given recipient elapses before its match, and before reneging (i.e. before its death), then the corresponding item is still in line, and we must draw again another predictive patience time. We denote by γ i,c , the distribution of predictive patience times of items of class i, conditional on having spent a time c in the system. Change of classes. Last, we suppose that our matching model with impatience is dynamic, in the sense that items of classes in R, i.e., recipients, can change classes and residual patience time within the system, while maintaining the same place in the system. Specifically, we let E 2 be the subset of V × V gathering the set of couples (i, j) such that a transition can be made from class i to class j. Then, for all (i, j) ∈ E 2 we let λ i,j be the rate of transition time for a patient from class i to class j, meaning that as soon as it becomes of class i (or enter the system being of class i), and provided that it does not leave the queue for a transplant or a reneging before that, an item will transition to class j after an exponential time (independent of everything else) of distribution Exp (λ i,j ). For any i ∈ R ′ and c ∈ R * + , we also define µ i,c as the distribution of patience times of items transitioning to class i after having spent a time c in the system, and µ ′ i,c , the generic predictive patience time of an item transitioning to class i after a time c spent in the system.

Model Dynamics.

From the items' point of view, the typical dynamics is as follows: A recipient r of class i arrives in the system, say, at time T , and is assigned an initial waiting time set at 0. If i ∈ R ′ , r also gets assigned a patience time P 1 of law µ i . This means that the patience time of r is theoretically due to end at time T + P 1 . The recipient r also gets assigned a predictive patience P ′ 1 of law µ i .

For all j ∈ R such that (i, j) ∈ E 1 , we draw an exponential random variable of law C i,j ∼ Exp(λ i,j ). Then, if one of these exponential clocks (take the smallest one, say it is C i,j ) rings before P 1 (if i ∈ R ′ ), and before r could find an organ for a match according to the policy Φ, then, at time T + C i,j , r changes class to j ∈ R, and if j ∈ R ′ , r is assigned a new patience time P 2 ∼ µ j,Ci,j and a new predictive patience time P ′ 2 ∼ µ ′ j,Ci,j . In the case of patient receveing a Meld exception, the waiting time is reset at 0, to mimic the fact that expert decisions only take into account the time since the patient has received a Meld exception. We denote by E 3 , the subset of E 2 describing transitions where the waiting time is reset to 0.

If the remaining predictive patience of an item hits 0 after a time c without any of the aforementioned events happening, and while it is of class i, we perform a new draw of a remaining predictive patience time, following the distribution γ i,c .

Markov chain. The state space of the model is

X = (V × R + × R × R) * .
Any word x ∈ X of length |x| can be written as

x = x 1 x 2 ⋯ x |x| ∶= (C 1 , D 1 , P 1 1 , P 1 2 )(C 2 , D 2 , P 2 1 , P 2 2 ) ⋯ (C |x| , D |x| , P |x| 1 , P |x| 2 ),
where for i ∈ 1, |x| , the variables C i , D i , P i 1 and P i 2 respectively denote the class, the waiting time in the system, the remaining patience time and the predictive patience time of the i-th item in the system in the order of arrivals. If the class of the i-th item lies outside R, i.e., it has no patience time and predictive patience time, then we just use the convention P i 1 = P i 2 = +∞. The system is then updated at exponential rates when one of those two events occurs on the time interval [0, h] (as is classically the case for exponential clocks, the probability that more than one event occurs on [0, h] is a o(h)):

(1) After a time h, a new item (C, 0, P 1 , P 2 ) enters the system, in which case we first update the state by decreasing the patience and predictive patience by h and increasing the waiting time by h for every item in the list. Then, any negative patience means that the corresponding item has reneged, and is deleted from the system. Therefore, we update the system to the new state

(1) x ′ = θ ((C 1 , D 1 + h, P 1 1 -h, P 1 2 -h) ⋯ (C |x| , D |x| + h, P |x| 1 -h, P |x| 2 -h)) ,
where for all y ∈ X, θ(y) is the state of X composed of the items of y having patience times in R + ∪ {+∞}, appearing in the same order as in y, and where any item j whose predictive patience has reached negative values on [0, h] has its predictive patience re-drawn from γ C j ,D j +h . Then we update to state x ′′ according to the matching policy, i.e:

(1a) If the new item cannot be matched, we add the item at the lost spot in line in the system, and so

x ′′ = x ′ (C, 0, P 1 , P 2 );
(1b) Else, the new item is matched with an item in x ′ , say item x ′ j , and then we just set

x ′′ = Ψ |j (x ′ ),
where for all y ∈ X, Ψ |j (y) is the word obtained from y by just deleting its j-th letter.

( . Depending on the type of transitions we then update the waiting time of the item to

) 2
Di = ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ 0 if (C i , Ci ) ∈ E 3 ; D i + h else.
The new state of the system is then updated as x ′′ , obtained from by substituting the letter ( Ci , Di ,

P i 1 , P i 1 ) to (C i , D i + h, P i 1 -h, P i 2 -h) in x ′ .
This dynamics characterizes a Continuous-time Markov chain (CTMC) which we denote by {X t }, and is reminiscent of the measure-valued Markov representations of EDF queues proposed in [START_REF] Doytchinov | Real-time queues in heavy traffic with earliest-deadline-first queue discipline[END_REF], [START_REF] Decreusefond | Fluid limit of a heavily loaded edf queue with impatient customers[END_REF] and [START_REF] Moyal | On queues with impatience: stability, and the optimality of earliest deadline first[END_REF]. For completeness, we write explicitly the infinitesimal generator of that CTMC in Section 8.1.

Matching policies.

Similarly to [START_REF] Mairesse | Stability of the stochastic matching model[END_REF][START_REF] Jonckheere | Generalized max-weight policies in stochastic matching[END_REF][START_REF] Masanet | Perfect sampling of stochastic matching models with reneging[END_REF], we now formalize the notion of matching policy.

Definition 1. In a dynamic matching system with impatience, a matching policy

Φ is a map from X × (V × R + × R + × R) to X such that for all x = x 1 x 2 ⋯x |x| ∈ X,, for all y = (C, D, P 1 , P 2 ) ∈ (V × R + × R + × R), Φ(x, y) = ⎧ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎩ xy if no class in x is compatible with C;
Ψ |j (x) else, if the policy chooses the item corresponding to x j .

A matching policy Φ is said to be patience-independent, if for all x and y, Φ(x, y) is independent of the patience of items in x and of the patience of y.

In what follows, we consider three different matching policies.

EDF. Standing for Earliest Deadline First, the EDF policy consists of matching the incoming item with the stored compatible item that has the lowest remaining patience, if any.

SCORE.

We say that Φ is a SCORE policy, if for all

x = (C 1 , D 1 , P 1 1 , P 1 2 ) ⋯ (C |x| , D |x| , P |x| 1 , P |x| 2 ) ∈ X,
the choice of j in Definition 1 is made based on the sole knowledge of the

S ((C i , D i )) , i ∈ 1, |x| ,
where S is a measurable map from V × R + to R + . In other words, the choice of match induced by Φ is made based on the sole knowledge of the classes and waiting times of the items in line. This policy corresponds to a simplified version of the score allocation, currently used in the France transplant system.

ESDF. Similarly to the EDF policy, the ESDF (Earliest Simulated Deadline First) policy consists of matching the item in the system that has the smallest remaining predictive patience among those which are compatible with the incoming item, if any.

As is well known in real-time queueing theory, the EDF policy, which prioritizes the elements that are the closest to their reneging time, is optimal in terms of feasibility [START_REF] Dertouzos | Control robotics: The procedural control of physical processes[END_REF], tardiness [START_REF] Moyal | Convex comparison of service disciplines in real time queues[END_REF] and loss probability under various statistical assumptions (see e.g. [START_REF] Panwar | Optimal scheduling policies for a class of queues with customer deadlines to the beginning of service[END_REF] and [START_REF] Moyal | On queues with impatience: stability, and the optimality of earliest deadline first[END_REF]). However, the very implementation of the EDF policy requires the full knowledge of the patience times of all customers in the system.

In the context of organ transplants, assuming the full knowledge of patience times is clearly unrealistic, as it amounts to the knowledge of the residual lifetimes in line, for all recipients. Thus, we aim at using policies that do not require this full knowledge, such as SCORE or ESDF. In particular, the ESDF policy can be seen as a proxy for EDF: instead of giving priority to the recipients that have the shortest remaining lifetime (an information that is clearly not available), we emulate the lifetime by simulating a survival time upon arrival (what we call the predictive patience), from the same probability distribution. Then, priority is given to the recipient that has the smallest residual predictive patience amongst all recipients in line for which a transplant is feasible.

Calibrating the parameters

In this section, we describe the precise parameters that were used for the liver transplant model and simulation. Transplanted recipients are censored on their transplant date, since we could not observe their death while they were in the waiting list (this is the so-called censored at transplant). The patience time distribution is calibrated as follows.

Definition 2. We assume that the patience times of classes in R ′ are IID from a Cox model. In other words, we have the following expression for the instant risk of death at time t, formally defined as the probability of death in an infinitesimal amount of time after t, conditional on the patient being still alive at time t:

λ(t, MELD ) = λ 0 (t) exp( 6 ∑ i=1 β i X i ),
where λ 0 (t) is the baseline instant risk of death at t,

X i = 1 {MELD ∈ category i} , i ∈ 1, 6
are the categorial covariable corresponding to the MELD categories (among [START_REF] Aveklouris | Matching impatient and heterogeneous demand and supply[END_REF][START_REF] Dertouzos | Control robotics: The procedural control of physical processes[END_REF], [START_REF] Doytchinov | Real-time queues in heavy traffic with earliest-deadline-first queue discipline[END_REF][START_REF] Masanet | Perfect sampling of stochastic matching models with reneging[END_REF], [START_REF] Merion | The survival benefit of liver transplantation[END_REF][START_REF] Wiesner | Meld and peld: application of survival models to liver allocation[END_REF], [26, 30], [31, 35] and [36, 40]), and for all i, β i is a weight parameter for the categorial covariable X i .

Then, there are three cases for patients survival laws:

(i) The real and predicted patience times of patients who are not MXP and do not await a MELD exception have the same law, based on that Cox model.

(ii) MXP patients have a different law for their real and predicted patience.

Indeed, for the MXP patients the predicted survival time that we may want to use to decide for a transplantation does not make much sense, since we mainly transplant them based on their life quality. Therefore we calibrated the predictive patience of MXP patients on the transplants observed in the waiting queue over a period of 4 years, see 2.3. This guarantees that transplants for MXP patients that were based on predictive patience would not be too far from what we would expect in reality.

(iii) Patients who awaits a MELD exception are the only patients who do not have a real or predicted patience time (these correspond to the only classes in R ∖ R ′ ). Indeed, in our model we consider that we know from the beginning that these patients will receive a MELD exception, and have to wait for it (while in real life, the decision to give a MELD exception and the receiving of such a component is simultaneous). This difference makes it so that if patients in our model could renege while awaiting a MELD exception, we might not have the right rates of arrival for MXP patients. Therefore, we consider that those patients cannot renege or be transplanted while they await for a MELD exception. Clearly, this is just equivalent to saying that those patients only arrive in the system when they receive their Meld exception, because in the context of organ shortage, under both SCORE and ESDF they would not have access to a transplant before receiving their Meld exception.

The patience times described above are assigned to patients upon their arrival in the system. We will describe in Section 4.3 how we calibrate these patience times after a class transition. Before that, we need to describe how we re-draw the predictive patience times when the latter become negative:

Definition 3. Let i ∈ V ′ and c > 0.
Then the law for re-drawing the predictive patience time of a recipient whose predictive patience has elapsed after having spent c units of time in the system, is given by

(2) γ i,c (p) = µ ′ i|≥c (p) -c, p ≥ c,
where γ i,c = µ ′ i|≥c is the following probability distribution: for all p ≥ c,

µ ′ i,|≥c (p) = µ ′ i (p) µ ′ i ([c, ∞)) = P(P 2 = p | P 2 ≥ c),
for P 2 a generic random variable of law µ ′ i .

4.3.

Class transitions. We model 2 kinds of class transitions:

(1) Transition between 'patient awaiting a MELD exception' to 'MXP patient';

(2) Transitions between MELD classes for patients who are not MXP nor awaiting a MELD exception, and don't have a contra-indication.

The transitions to receive a MELD exception are based on the observed transition over a period of 2 years, and also take the form of a Cox Model. These transitions are the only transitions in E 3 , i.e., we reset the time spent in the system when we give a MELD exception. For those transitions to a class i after having spent c units of time in the system, we draw the new real patience from the distribution

µ i,c = µ i|≥c -c,
associated to µ i as in [START_REF]Handbook of liver allocation in france[END_REF]. Then, the predictive patience is drawn from µ ′ i , which makes sense because the predictive patience distribution was established using the observed transplantation only after a patient received a MELD exception.

The transitions between MELD classes are the transitions for which we had the least amount of data, so we calibrated the rates in the following way: For any i ∈ R, we denote by W up i (resp. W down i ) the set of classes having the same indication, contra-indication status and MELD exception awaiting status than i, and having a higher (resp. lower) MELD.

-If W down i is empty, then for all j ∈ W up i we set

λ i,j = 1 2 ξ j ∑ k∈W up i ξ k ⋅ -If W up i
is empty, then for all j ∈ W down i we let

λ i,j = 1 2 ξ j ∑ k∈W up i ξ k ⋅ -Otherwise, for all j ∈ W up i we set λ i,j = 1 2 1 3 ξ j ∑ k∈W up i ξ k = 1 6 ξ j ∑ k∈W up i ξ k ,
and for all j ∈ W down i ,

λ i,j = 1 2 2 3 ξ j ∑ k∈W up i ξ k = 1 3 ξ j ∑ k∈W up i ξ k ⋅
To better understand this calibration choice, note that setting these rates for MELD transitions is equivalent to applying the following procedure:

1) Draw an exponential of parameter λ i = 1 2 that determines the time until the patient changes MELD class (whatever the MELD class is), setting at 2 years, the average time for changing MELD class.

2) If the patient MELD can decrease (i.e., W down i is not empty) and/or decrease (i.e., W up i is not empty) then with probability 1 3 the patient gets a lower MELD and with probability 2 3 , a higher MELD. This conveys the idea that a patient status is more likely to deteriorate than to improve.

3) Once we have chosen if the patient status improves or deteriorates (say it deteriorates), we pick the class j with probability • Arrivals occur at each time step, and the class of the arriving patient/organ is drawn according to the initial inter-arrival rates ξ i , by uniformization.

• The law of transitions between MELD classes is geometric, with the same mean as the exponential laws of the MELD transitions.

• For practical reasons, instead of considering that a patient awaiting a MELD exception has no patience time, we draw a predicted and real patience times conditioned to be greater than the transition time to receive a MELD exception, thereby ensuring that the corresponding patients will not die before receiving the MELD exception.

Simulation procedure

By conducting this simulations, our aim is to observe how different policy decisions (SCORE, ESDF) and different organ shortage percentages (0%, 15%, 30%, 50%) affect the evolution of a patient/organ waiting queue. To do so, we split the simulation into 2 phases:

5.1. The initiation phase. In this phase, our aim is to create a queue that will be used as an initial state for the study of the impacts of policy decisions and organ shortage in the study phase. To do so, we start with an empty queue, and then simulate the dynamics of the queue during a reasonable amount of time (here, approximately 15 years), by not applying the different organ shortage percentages during this phase. Indeed, if it was not so and if we started to study patients and organs from an empty queue, then it would lead to an unrealistic view of the queue dynamics, as most of the first patients would be transplanted, and there would not be enough competition between patients.

Notice that, in a standard Markovian model, one typically studies the system behavior from any possible starting position, so that it can be asked why the initial queue generated in this initiation phase is not simply viewed as an additional parameter for the study phase. The fact is that the composition of a patient/organ waiting line is an intricate of the positions of patients/organs in the queue, of the time they already spent in the queue, their class, etc., so that viewing the starting queue as an additional parameter would require too many additional simulations.

5.2. The study phase. Starting from the queue generated in the initiation phase, we then simulate the dynamics of the queue, by applying the fixed matching policy and the given organ shortage percentage, during a period of approximately 10 years.

While performing these simulations, we record different characteristics composing the fate of organs and patients during this period:

• The initial class they had when entering the queue (if they received a MELD exception changing their class to a new class, then we consider this new class as their initial class);

• If they were transplanted, deceased or are still alive at the end of the study phase;

• The time they have spent in the system during the study phase.

It is standard in the medical context to only study the fate of patients and organs that arrived during the study phase. However, to have a more complete view, we also recorded the fate of patients/organs from the initiation phase.

Simulations dynamics.

The simulations principle is the same whether we are in the initiation phase or the study phase: We divide the phase in equal amount of times called time steps. At each time step, we randomly draw an incoming patient/organ class according to a probability law P arr (as mentioned in 2.2, P arr is based on the observed incoming rates of patients/organs of different classes during a period of 2 years).

If it is indeed a patient, we also draw if she awaits a MELD exception. We then draw her real survival time using the aforementioned Cox model, as well as the predicted survival time in the case of the ESDF policy. If it is an organ, we simply consider a constant survival time since, from a certain time point, all organs are immediately transplanted. We then actualize the status of every patient/organ in line, as follows:

1) Their elapsed sojourn time in the system increases by one time unit;

2) Their real and predicted survival time, as well as the eventual time they have to wait to receive a MELD exception, decrease by one;

3) We determine if the patient/organ is deceased, in which case it is removed from the queue; 4) We determine if the patient/organ receives a MELD exception, in which case we change its class, set its elapsed sojourn time to 0, and then re-draw a real and predicted survival time conditioned to be larger than the time she already spent in the system.

5)

We determine if the patient/organ state deteriorates or improves, in which case we change its MELD class.

We then check, whether the incoming patient/organ can be matched with an already existing organ/patient in line. If so, we determine its match according to the matching policy, and we then remove the chosen organ/patient from the system. If not, we add the incoming patient/organ to the queue.

We then repeat this operation for every time step. Note that we can separate the phase in steps of time because the inter-arrival times of our model are supposed constant. At the end of the two phases, we return the state of the queue for the initiation phase, and the fate of all arrived elements during the study phase.

Main algorithms.

The simulation function that is represented in Figure 1 is the main algorithm, with N 1 being the number of steps we want to simulate the queue in the initiation phase starting from an empty queue.

The dynamic function represented in Figure 2 describes the dynamics of one simulation step. The secondary algorithms that are used in the simulation are described in section 8.2.

Results

Table 1. Description of the patient population (mean number of patients per 10 simulations) As expected, increasing organ shortage is associated with higher DDTS rates (32% to 52% for ESDF policy and 31% to 53% for SCORE policy) and lower LTx rates (61% to 34% for ESDF policy and 64% to 38% for SCORE policy).

ESDF and SCORE policies have roughly equivalent DDTS rates (no significant differences) regardless of the level of shortage. But the main point of this figure is that the DDTS rates for CIRRH, HCC and OTHER indications remain equitable with increasing organ shortage level With ESDF policy, in contrast to SCORE policy where DDTS rates for HCC increase significantly in case of 30% and 50%

increase in organ shortage.

The same holds true for LTx rates which remain equitable for all indications with the ESDF polcy.

In contrast, the SCORE policy provides inequitable LTx rates with higher LTx rates for MXP as compared to CIRRH, OTHER and HCC, the later having the lowest LTX rate that might explain the inequitable increase of DDTS for this indication. In our study, organ shortage levels were related to decrease in organ procurement.

Nevertheless, our results are likely valid for epidemiological or clinical situations resulting in an increase in LTx indications.

7.2. Limitations and Future works. Despite the good results obtained in this study, there are some limitations.

Of note, (i) the initiation phase provided a higher number of transplant candidates for the study phase, resulting in a higher organ shortage in this study than the actual situation in France ; (ii) we used 10 years DDTS rates whereas 2 or 5 years DDTS rates are usually considered. Anyway, this does not affect the key results related to the resilience of ESDF policy to organ shortage. Last, while we hope that a 30% decrease in organ procurement won't be observed in practice, this corresponds to a Organ/LTx candidate ratio that might occur in some countries.

Outside such a decrease, a MELD based SCORE system might be resilient to mild decreases in organ procurement.

This study uses a macro-population simulation Markov model with classes. Future works is to validate these promising results using our micro-population simulation platform. let E 3 (y) be the set of possible transitions of items of y where the timer is reseted. We then define:

E 4 (y) = {(i, j, k) ∈ E 2 (y)/E 3 (y), j ∈ R ′ }, E 5 (y) = {(i, j, k) ∈ E 3 (y), j ∈ R ′ }, E 6 (y) = {(i, j, k) ∈ E 2 (y)/E 3 (y), j ∈ R/R ′ }, E 7 (y) = {(i, j, k) ∈ E 3 (y), j ∈ R/R ′ }. Let k ∈ 1, |y| and (C, D, P, P ′ ) ∈ V ×R + ×R×R. Then θ 3 (y, k, (C, D, P, P ′ ))
is the state of X composed of the items of y, where the item in k-th position is replaced by (C, D, P, P

′

).

Gathering the arguments of section 3.2, we obtain that Theorem 1. The infinitesimal generator A of the Markov chain X is characterized as follows: for all sufficiently smooth functions F ∶ X ↦ R, for all x ∈ X such that (1) a is the class of i. It belongs to R, as defined in section 3;

O x = {i 1 , ⋯, i l } with i 1 < i 2 < ⋯ < i l , we have that A F (x) = lim h→0 E[F (X k+h ) -F (X k )|X k = x] h = lim h→0 ∑ ℓ∈Ux ξ ℓ ∫ R l + [F (Ψ |I(Φ,θ 2 (τ h (x),p ′ 1 ,⋯,p ′ l ),i) (θ2(τ h (x), p ′ 1 , ⋯, p ′ l )) -F (x)] ⊗ l m=1 dγ C im ,D im (p ′ m ) + ∑ ℓ∈R ′ /Ux ξ ℓ ∫ R l + ∫ R 2 + [F (θ2(τ h (x), p ′ 1 , ⋯, p ′ l )(i, 0, p, p ′ )) -F (x)] ⊗ l m=1 dγ C im ,D im (p ′ m ) dµi(p) dµ ′ i (p ′ ) + ∑ ℓ∈(V /R ′ )/Ux ξ ℓ ∫ R l + [F (θ2(τ h (x), p ′ 1 , ⋯, p ′ l )(i, 0)) -F (x)] ⊗ l m=1 dγ C im ,D im (p ′ m ) + ∑ (i,j,k)∈E 4 (x) λi,j ∑ ℓ∈R ′ /Ux ξ ℓ ∫ R l + ∫ R 2 + [F (θ3(θ2(τ h (x), p ′ 1 , ⋯, p ′ l ), k, (j, D k , p, p ′ )) -F (x)] ⊗ l m=1 dγ C im ,D im (p ′ m ) dµ j,D k (p) dµ ′ j,D k (p ′ ) + ∑ (i,j,k)∈E 5 (x) λi,j ∑ ℓ∈R ′ /Ux ξ ℓ ∫ R l + ∫ R 2 + [F (θ3(θ2(τ h (x), p ′ 1 , ⋯, p ′ l ), k, (j, D k , p, p ′ )) -F (x)] ⊗ l m=1 dγ C im ,D im (p ′ m ) dµ j,D k (p) dµ ′ j,D k (p ′ ) + ∑ (i,j,k)∈E 6 (x) λi,j ∑ ℓ∈R ′ /Ux ξ ℓ ∫ R l + [F (θ3(θ2(τ h (x), p ′
(2) b 0 and b 1 are the real and predicted remaining survival time of i;

(3) c ∈ R + is the time already spent in line by the patient/organ.

Queue actualization

The queue actualization at each step of time is handled by the function actualization that acts as follows.

Step Step 3 : If b 0 (the real survival time) is negative, the patient/organ is deceased, so we remove the patient/organ from the system and go back to step 1. If not go to Step 4.

Step 4: If b 1 (the predicted survival time) is negative, our prediction was wrong, so we re-draw a new predicted survival time according to µ ′ a,c .

Step 5: If -1 < d < 0, the patient must receive a MELD exception, and we do so using the MXP function, which also updates its information.

Step 6: Using the reMELD function, we determine whether the patient changes MELD class and if he does, we update his information accordingly.

We then go back to Step 1.

Step 7: We return the state of the queue, with all patients/organs updated.

Transition between MELD classes.

The algorithm described in Figure 6 determines randomly if a patient changes MELD class, and if it does, it draws the new class according to the new function.

Last, this routine re-draws the predicted and residual survival times.

There, the function resurv(a, c) (resp. resurv 2 (a, c)) redraws a remaining real (resp. predicted) survival time according to µ a,c (resp. µ ′ a,c ), and new(a) draws randomly the new MELD of a patient in the following way:

(1) With probability 1 3 , we draw an improvement of the patient state (lower MELD), and with probability 2 3 , a deterioration of the patient state (higher MELD). (If the MELD is already minimal or maximal, we don't get do anything.)

(2) Then we draw among the possible MELD classes, weighing each class according to the initial arrival probability of each MELD class.

1. 2 .

 2 Rationale for change. During the Covid-19 period, we observed an increase in organ shortage that resulted in an imbalance between Liver Allocation score components [1]. This fact, confirmed by simulation works, prompts us to find organ shortage resilient mathematical models. 1.3. Real-time queueing systems. Queueing systems have become a standard model in operational research, in the performance evaluation of communication and computer networks, and supply chains, among other fields. The typical settings allow for a representation of the system at hand by a markovian stochastic process.

  can await to receive a MELD exception. There are therefore 27 different patient classes with 9 OTHER classes (6 MELD classes + 3 for patients awaiting MELD exceptions), 6 HCC classes (6 MELD classes), 9 CIRRH classes (6 MELD classes + 3 for patients awaiting MELD exceptions), 3 MXP classes (3 MELD classes). We denote by R 1 the patients who are not waiting for a MELD exception and by R 2 the patients awaiting a MELD exception in a way that we

4. 1 .

 1 Arrival rates. The arrival rates of all classes (donors and recipients) except the Meld exceptions recipients, are calibrated by the observed arrival rates of the patients in real life, over a period of 2 years (see 2.2). For Meld exception recipients, the arrival rate is null: patients first arrive into the system, awaiting a MELD exception, and only then, transition to become MXP patients (see 2.3). 4.2. Patience times. In practice, due to organ shortage, organs are only removed from the waiting line whenever there is already a patient awaiting in line upon their arrival into the system. So we make the assumption that organs are immediately matched upon arrival, in other words, organs (class {d}) have no patience clock upon arrival. The patience times of patients of all classes are calibrated by the observed death of patients of such classes in the waiting line, during a period of 4 years (see 2.3).

4 . 4 .

 44 that we consider picking a new MELD class among the set W up i of possible ones, which is equivalent to seeing the arrival of a new patient, conditional on her class belonging to W up i . For those transitions to a class j after a time c spent in the system, we draw the new actual and predicted patience times respectively from the (conditional, and shifted) laws µ j,c and µ ′ j,c , respectively associated to µ j and µ ′ j respectively, as in[START_REF]Handbook of liver allocation in france[END_REF]. Adapting the model to the discrete-time settings. The model introduced so far is formally defined in continuous time. To adapt the present model to discrete simulations, we made the following changes and approximations:

Figure 1 .

 1 Figure 1. simulation function

Figure 2 .

 2 Figure 2. dynamic function

Figure 3 .

 3 Figure 3. DDTS and LTx rates by organ shortage level and matching policy.

Figure 4 .

 4 Figure 4. Variance DDTS rate by indication (without MXP)

7 . Discussion 7 . 1 .

 771 Main findings. Of course, DDTS rates will always increase and LTX rates always decrease with organ shortage, but a major result of our study is to demonstrate that ESDF policy offers prospects for allocation system resilient to organ shortage in terms of equity on both DDTS and LTx rates. Of course, increasing organ shortage in liver transplantation leads to an increase of DDTS rates. Of note, at each level of organ shortage, ESDF policy performs similarly to the Score policy in terms of DDTS rate.Moving from a MELD-based SCORE to a continuous expected lifetime ESDF policy (based on the projected remaining patience into the system) seems like a game changer. This study proposes an extension to the classical model EDF to a more realistic Earliest Simulated Deadline First (ESDF) policy, allowing to emulate the behaviour of the EDF policy, by predicting the value of the remaining patience times of the patients.

7. 3 .

 3 Conclusion/Take home message. Continuous expected lifetime ESDF policy might provide organ shortage resilient allocation systems in terms of equity, without significant impact on the overall DDTS rate.

11

  , ⋯, p ′ l ), k, (j, D k )) -F (x)] ⊗ l m=1 dγ C im ,D im (p θ3(θ2(τ h (x), p ′ 1 , ⋯, p ′ l ), k, (j, D k )) -F (x)] ⊗ l m=1 dγ C im ,D im (p h (∑ i∈V ξi -∑ (i,j,k)∈E 2 (x) λi,j )

8. 2 .

 2 Secondary algorithms. 8.2.1. Notations. Every element (patient or organ) i in the system can be tracked by a sextuple [a, b 0 , b 1 , c, d, e] called the information on i, where:

( 4 )

 4 d determines if the patient awaits to receive a MELD exception, and if so, in how much time. If e ≤ -1 then the patient doesn't await a MELD exception. If -1 < d ≤ 0 the patient must receive a MELD exception. (As we decrease e in a discrete way, we need a margin away from 0 that is higher than the time step.) If d > 0, then d is the time until the patient receives a MELD exception.(5) e only intervenes in the study phase and is a number that identify the patient/organ, negative for prevalent patients, positive otherwise.8.2.2. Algorithms.Organ/patient arrivalThe program shown in Figure5describes the arrival of an organ/patient at one time step. It draws the information of the organ/patients, i.e their class, their eventual temporary contra-indications and MELD exception awaiting, and their real and predicted survival times in the system.

Figure 5 .

 5 Figure 5. incoming function

Step 2 :

 2 1: Pick the first non-actualized patient/organ in the queue and get his informations [a, b 0 , b 1 , c, d, e]. If there is no patient/organ left to actualize in the queue go to Step 8. Increase or decrease the relevant information by one time step. (Namely, b 0 , b 1 , d and e decrease by one and c increases by one).

Figure 6 .

 6 Figure 6. reMELD function

Figure 7 .

 7 Figure 7. XPF function

  2.2. Patients and donors arrivals/flow. 2.2.1. Patients. All newly registered patients on the French national waiting list between January 1, 2018 and December 31, 2019, in the liver transplant centers in

	2.3. Survival times generation.
	2.3.1. Patients. All newly registered patients on the French national waiting list
	between January 1, 2012 and December 31, 2016, in the liver transplant centers
	in France were included. 3758 patients were listed for transplantation during the
	study period.
	2.3.2. Method. A cox proportional hazard statistical was performed to predict DDTS
	dropout. We stratified the model by indication and only used MELD as covariate.
	France were included. 3758 patients were listed for transplantation during the study
	period. Patients' anonymous aggregated data according to blood type, transplant
	indications (hepatocellular carcinoma, cirrhosis, MELD exception and others) and
	MELD classes to feed the mathematical model.
	2.2.2. Donors. All brain dead deceased donors in France between January 1, 2018
	and December 31, 2019, whose liver has been transplanted were included. 2458
	donors were transplanted during the study period. Donors' anonymous aggregated
	data according to blood type were used to feed the mathematical model.

  Patient population. The mean numbers of patients enlisted during the first 2 years of the study period per 10 simulations are presented in Table 1. On columns Ltx and DDTS crude rates. Figure 3 reports on the crude DDTS and LTx rates by organ shortage level and matching policy. SCORE and ESDF are displayed respectively in darkgray and orange bars. Of note, as we stated that an equitable

	we have the 2 matching policies (ESDF and SCORE) and the 4 levels of organ
	shortage (0%, 15%, 30% and 50%) which correspond to all the simulated scenarios.
	On rows we have the 4 indications and the 6 MELD classes.
	For instance, the first column for ESDF policy and 0% of organ shortage show
	that the mean number of patient arrivals for CIRRH indication is 1333.8 and for
	[36-40] MELD class is 378.3.
	Variations in patient arrival flow by matching policies and organ shortage sce-
	narios due to the stochastic modeling are low, and are likely to have a very small
	influence on DDTS and LTx rates between the two policies.
	CIRRH and HCC are the 2 main indications with an average of nearly 1300
	patients in 2 years. OTHER is the smallest one with an average of 321 to 356
	patients and MXP has an average of 747 to 811 patients. As expected, according
	to the actual epidemiology of liver diseases, the number of patients is decreasing
	with increasing MELD class.
	6.2.

6.1.

8. Supplementary materials 8.1. Infinitesimal Generator. The dynamics of the Markov chain {X t } as presented in 3.2 can also be encoded by the following Infinitesimal generator. Hereafter, fix

and let us introduce the following additional piece of notation,

(1) Aging:

To represent the aging of items, for all h > 0 we set

(2) Removing reneged recipients and redrawing predictive patience times: (3) Choosing and removing matched items: Let U y be the subset of V of those classes that can be matched with elements represented by y. Then, for any admissible matching policy Φ and any class i, we let I(Φ, y, i) be the index of the item of y that will be matched with an incoming item of class i, according to Φ.

(4) Transitioning items: Let E 2 (y) be the set of possible transitions of items of y, where any transition for an item I is denoted (i, j, k) where i is the class of I, j is a class available for I to transition, and k is the position of I in y. Similarly, we