{'fraction_non_alphanumeric': 0.04525957314061403, 'fraction_numerical': 0.011256401590974081, 'mean_word_length': 3.733940438099926, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 10, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Kidney exchange and endless paths: On the optimal use of an altruistic donor

We consider a well-studied online random graph model for kidney exchange, where nodes representing patient-donor pairs arrive over time, and the probability of a directed edge is p. We assume existence of a single altruistic donor, who serves as a start node in this graph for a directed path of donations. The algorithmic problem is to select which donations to perform, and when, to minimize the amount of time that patients must wait before receiving a kidney. We advance our understanding of this setting by (1) providing efficient (in fact, linear-time) algorithms with optimal O(1/p) expected waiting time, (2) showing that some of these algorithms in fact provide guarantees to all patients of O(1/p) waiting time {\em with high probability}, (3) simplifying previous analysis of this problem, and (4) extending results to the case of multiple altruistic donors.


Introduction
Altruistic donors have proven to be very powerful in practice in kidney exchange, with a single donor enabling a long sequence of matches. In fact, such sequences have a name: a Never Ending Altruistic Donor (NEAD) chain [17]. 1 The idea is that the altruistic donor donates to a compatible patient A who has already joined the kidney exchange with her willing but incompatible donor B, and in return B agrees to "pay it forward" by serving as a donor to some existing or future compatible patient C who has entered the system with her willing but incompatible donor D, and so on. One reason this can be so powerful is that unlike cyclic exchanges, these donations do not have to be simultaneous. 2 In this work, we consider a well-studied online random graph model [7,2,3,4,5] in which nodes (patient-donor pairs) arrive over time, and between any two nodes u, v there is a directed edge with probability p (with probability p, the donor for u is compatible with the patient for v). This model is of particular interest when p is small, which corresponds to the important case of highlysensitized patients. Our goal is to minimize the average waiting time of patients until they get a kidney, as well as to provide per-patient high-probability bounds on their waiting time.
There are two natural extremes for using an altruistic donor. One is greedy longest-waiting-timefirst: whenever a patient arrives who is compatible with the altruistic donor, immediately donate the kidney, making the patient's associated donor become the new altruistic donor. There now may be multiple patients who this donor can donate to, and in this algorithm we always choose the patient who has been waiting the longest. In a sense, this is the most "fair" and natural algorithm. A second natural extreme is to wait until enough patient-donor pairs have arrived so that there is a Hamiltonian path visiting all nodes in the graph, and then completely clear the queue using this Hamiltonian path. Both algorithms yield an Θ( 1 p log 1 p ) expected waiting time per patient. However, this is not optimal, and [5] give an alternative, computationally-inefficient algorithm that achieves an optimal bound of Θ( 1 p ). In this work, we give two computationally-efficient (in fact, linear time) procedures that achieve the optimal Θ( 1 p ) expected waiting time per patient, one of which also provides each patient a guarantee of waiting time at most O( 1 p ) with high probability. We also give a somewhat simpler correctness argument. For the first algorithm, the idea is to wait a bit before matching (unlike the greedy algorithm) in order to have more options for routing a long path, but not to the extreme of requiring the path cover all the existing nodes in the graph. It then uses Depth First Search (DFS) on the graph to discover a long (though perhaps not the longest) path, and therefore is linear time to implement. We bound not only the expected waiting time but also provide high probability bounds. We then use our analysis of this algorithm to analyze a second algorithm that does not require waiting. This algorithm runs the greedy longest-waitingtime-first algorithm when the number of patients waiting is small, but then switches over to one of the other algorithms (using a DFS-based method to select a path rather than always choosing the patient who has been waiting the longest) in order to more quickly reduce the queue. We show the combined algorithm also enjoys an optimal Θ( 1 p ) expected waiting time for each patient. In addition, we also consider the case of multiple altruistic donors, and show that if there are only O(1/p) altruistic donors then the Ω(1/p) lower bound still applies, while for Ω((1/p) log(1/p)) donors even a naive greedy has an O(1) expected waiting time. (However, the O(1) might be misleading, since conditioned on the patient not being matched immediately, then the expected waiting time is Ω(1/p).) We note that in real-life kidney exchanges, there is some chance donors will back out (or become ill or otherwise be unable to donate). We ignore this effect here because it obscures the distinctions between different algorithms. For instance, if each donor backs out with probability q, then no algorithm can possibly hope to construct a chain of expected length more than 1/q.

Related work
There has been substantial work analyzing kidney exchange in static random graph models. Questions studied include whether it is possible to match most patients in the system, and to what extent long chains in addition to short cycles are needed [9,6]. Additionally, researchers have considered questions such as motivating hospitals to join and fully participate in the exchange under such models [8,18] and how to match in the presence of failures [12]. [19] was the first to consider kidney exchange in dynamic random graph models in which nodes arrive one at a time. This work considers the dense-graph case, focusing on blood-type incompatibility rather than highly-sensitized patients as we do here.
The work of [7] considers dynamic kidney exchange in the model we consider here, namely highlysensitized patients (small p) and assuming all pairs are blood-type compatible (so for every pair u, v there is an edge from u to v with probability p). One of their main results is that allowing for a chain in addition to cycles of size 2 or 3 increases the total number of matches linearly in the number of arriving nodes. [1] consider a dynamic model in which nodes both arrive and depart over time, and examine different pairwise matching algorithms in this model.
The question of queue size (expected waiting time for patients to receive a kidney) in the setting of highly sensitized patients is considered in [2,3,4,5]. [2] examine queue size for cycles rather than paths. Their conclusion is that for cycles, greedy matching is optimal: they show that the greedy algorithm has an average waiting time of O(1/p 2 ) for cycles of size 2 and O(1/p 3/2 ) for cycles of size 2 or 3, which is best possible. In a follow-up work, [3] show that for a chain (which starts with an altruistic donor) the greedy algorithm, if it selects the longest path in the graph, can guarantee an expected waiting time of O(1/p). A clear caveat of such an approach is that computing the longest path is NP-complete. In contrast, our efficient algorithms run in linear time. Finally, [4,5] consider a dynamic model with both easy-to-match and hard-to-match patients, and consider both cycles and paths, analyzing expected waiting time. A particularly relevant result shown in [5] for our setting is that the greedy algorithm for paths has average waiting time of Θ((1/p) log(1/p)) when all patients are hard to match.
There is of course a substantial body of work in general on analysis of random graphs; see, e.g., [11,14]. We use the ideas from [16] to compute long paths in random graphs using DFS algorithms.

Model
In our model, the basic unit is a pair consisting of a patient and a willing but incompatible donor, which we model as a node in a directed graph G(V, E). The set of nodes of V are these patientdonor pairs except for one special node which represents the single altruistic donor, which we call the start node. A directed edge between two nodes indicates that the donor of the first pair (node) is compatible with the patient of the second pair (node).
The process of matching donors with patients reduces to finding a directed path starting at the altruistic donor (start node). Again, the interpretation is that each directed edge u → v represents a donation from the donor at u to the patient at v. The number of edges in the path represents the number of donations. Essentially, our goal is to maximize the length of the path, maximizing the number of patients that receive a donation.
We consider an online (dynamic) model, where there is a stream of nodes (patient and donor pairs) that arrive one per time step and our goal is to minimize the expected time a patient waits until she is matched to a compatible donor.
We assume that we start at time t = 0 with the start node v 0 (altruistic donor). At each integer time t > 0 one node v t arrives. For each existing node v τ , for τ < t, we select with probability p an incoming edge and with probability p an outgoing edge, independently. I.e., with probability p we have v τ → v t , and also with probability p we have v t → v τ , where all the events are independent.
In time t, the algorithm may extend the directed path (which began originally at the start node v 0 , the altruistic donor) by one or more edges if such an extension exists in the graph. This is viewed as servicing or matching those nodes on the directed path.
At each time t we have a node v e t which is the end of the current path, and we call it the end of the path, and any future extension has to start with it. The nodes which are still not on the directed path are called waiting nodes. We refer to the queue size, q t , at time t, as the number of waiting nodes at time t. The waiting time w t of a node v t is the time between its arrival, t, and the time it is added to the path a t (namely, the time until the patient in the patient-donor pair is serviced). Formally, w t = a t − t.
We assume that extending the path, by any extension, is done instantaneously, and we ignore that time. We also assume that a node exists until it is added to the path (i.e., serviced). Namely, patients do not depart until they receive a kidney.
Our main discussion is on when and how to extend the path. Unlike some online models, an arriving node does not have to be serviced immediately, even if it can be.
We assume that the process continues for T time steps, but most of our results will be independent of this parameter. For nodes v t that are not serviced by time T we assume that a t = T , just for simplicity of the presentation.

Evaluation criteria
Our main evaluation criteria is the expected waiting time of a node, or alternatively, the expected queue size. Note that the sum of the waiting times of nodes (i.e., patients) over time is the same as the sum of the queue sizes over time. 3 Definition 2.1. The average waiting time (queue size) is 1 where the expectation is with respect to the random edges and any randomization of the path selection algorithm.
We will be also interested in deriving high probability guarantees on the waiting time of a node. Definition 2.2. We say that node v t has with probability 1 − δ a waiting time of at most ω if Pr[w t > ω] ≤ δ.
We are also interested in giving node specific guarantees, starting at an arbitrary time, conditioned on the history. The goal is to show that the system does not discriminate against any patient, and that history has a limited effect on the waiting time.

Multiple altruistic donors
We also consider the case that there are multiple altruistic donors, denoted by R. In this case each of the R altruistic donors has a separate directed path. (Clearly, the paths are node disjoint.) At each time t, the algorithm decides which of the paths to extend and how to extend them. (The algorithm may decide to extend multiple paths at the same time.)

Preliminaries: Random walks
In many places in our analysis we will need to analyze sequences of random variables which are generated through a random walk. At a high level, the sequence of non-negative random variables will have the property that if their value is above a certain threshold, we are guaranteed that in expectation their value will decrease. Intuitively, this implies that their expected value cannot be much larger then the threshold. While this holds, under some assumptions that do hold in our setting, it does require some analysis that we perform in the Appendix.
Two remarks are in order. First, we believe that our derivation is most likely implicitly known, but unfortunately we were not able to locate any reference. For this reason we added the derivation in the Appendix. Second, we remark that one cannot use the Azuma inequality in our setting, since the decrease is "unbounded", while the Azuma inequality requires that the maximum change is bounded.
We now do the precise formalization and derivation. Let Q t be a sequence of non-negative random variables where initially The main property that we assume about the sequence is that when Q t ≥ M + 1 then with probability at least ρ we have Z t ≥ K. In addition, ρK = 1 + β where β > 0, which means that for |Q t | ≥ M + 1, the expected change in Q t , which is at most 1 − ρK, is negative. We call such a random walk a (M, K, ρ, β) random walk. (Actually, since ρK = 1 + β one parameter is redundant, but it will be more convenient to have all four parameters.) Intuitively we like to claim that this implies that E[Q t ] ≤ M + O(K), however, this requires some care.
In Appendix B we show the following theorem.

Lower bound for any algorithm
We start by showing that for any algorithm the expected waiting time has to be Ω(1/p). Proof. Fix any time t and consider v t the node arriving at time t. We need v t to have at least one incoming edge to have it served. The expected number of coin flips until we have an incoming edge is 1/p. Therefore, we have E[w t |q t ] ≥ 1/p − q t , since we immediately do q t coin flips, for the q t waiting nodes, and the right-hand-side corresponds to a lower bound in which we consider an edge to the ith waiting node as giving w t = i − q t rather than giving w t = 0.
Taking the expectation with respect to the history up to time t, we have E[ Averaging over all time steps we have 1 Since the expected average waiting time and queue size are identical, we have that the expected average waiting time is at least 1/2 p .

Greedy algorithm
We now concentrate on the simple greedy longest-waiting-time-first algorithm (Greedy). Greedy extends v e t , the end of the path at time t, the first opportunity it has, and in the event of multiple options always chooses the patient who has been waiting the longest. Note that after it completes an extension, the new end of the path, v e t+1 , does not have any directed edges to waiting nodes. We begin with matching upper and lower bounds on the expected waiting time of the greedy algorithm. These bounds are shown also in [5] but we prove them here through a different argument that helps to set up our general methodology. Proof. We start by showing that the waiting time of Greedy is at least Ω( 1 p log 1 p ). At time t, with probability 1 − p, node v t does not have an incoming edge from the end of the directed path v e t . In this case, the queue size grows by 1. Otherwise, with probability p, node v t has an incoming edge from v e t , and v t and a path of length path(v t ) extends the current path from v e t . The change in the queue size q t is, We need to upper bound path(v t ). Note that while generating the path, we have a probability of at least (1 − p) qt of terminating the path since we reached a node with zero outgoing degree. 4 This implies that We can now partition the time into intervals, where q t < λ ǫ , or singletons where q t ≥ λ ǫ . In the intervals, we have an increase of q t bounded by 1 (deterministically) and at least ǫ (in expectation). Assume we start an interval with a value q t = 0 (this will be the worst case). The expected length of the interval would be at most λ ǫ /ǫ and the sum of the queue lengths would be at least λ 2 ǫ /2.
With probability at least 1/2 the length of the interval is at most 2λ ǫ /ǫ. This implies that the average queue size in the interval is at least For ǫ = 1/2 we get an expected lower bound of (1/16)λ 0.5 = (1/(16p)) ln((0.5 − p)/p).
We now analyze the upper bound using (M, K, ρ, β) random walk and Theorem 3.1. Notice that given that v e t , the end of the path, has an outgoing edge (probability p at each time t), the probability of extending by a path of length at least 4/p is at least (1 − (1 − p) qt ) 4/p . For q t > (1/p) log(4/p) this is at least 1/e. This implies that we have a (M, K, ρ, β) random walk for M = (1/p) log(4/p), K = 4/p, ρ = p/e and β = 4/e − 1 < 0.5. From Theorem 3.1 we have the desired upper bound.

The CLEAR-ALL algorithm
The CLEAR-ALL algorithm waits until it can extend the current path and serve all the existing nodes, i.e., using a Hamiltonian path. This implies that we partition the time to phases, where the algorithm CLEAR-ALL serves all the waiting nodes. This implies that each phase starts with an empty queue! Theorem 6.1. The CLEAR-ALL algorithm has an expected waiting time of Θ( 1 p log 1 p ), for p < 1/2.
Proof. The algorithm CLEAR-ALL waits until the waiting nodes have a Hamiltonian path connecting all of them. From graph theory we know that for an Erdos-Renyi graph G(n, p) if p = log(n)+log log(n)+O(log(1/δ)) n then with probability 1 − δ we have a Hamiltonian path (see, [15,10,13]).
This implies that when we have n δ = O(log(1/p)+log(1/δ)) p nodes waiting, with probability 1 − δ we have a Hamiltonian path. This implies that the expected number of arrivals before we have a Hamiltonian path is Θ( 1 p log( 1 p )). Each time we have a Hamiltonian path in the graph of the waiting nodes, we extend the current path from the end of the path v e t , using the Hamiltonian path and completely empty the queue of waiting nodes.

Batch algorithm
We now present the Batch algorithm, which we show achieves waiting time only Θ( 1 p ). The idea behind the algorithm is to wait for some time and aggregate arrivals, and then in one time step to compute and add a long path. The benefit, compared to Greedy, is that we can plan better to find a longer path. The challenge is that now the graph on the nodes left over is no longer random, because the path is determined algorithmically based on structural properties of the nodes. In contrast, one of the key features of Greedy is that because it selects which outgoing edge to take based solely on the arrival time of the incident node, the graph on unvisited nodes remains uniform random. In fact, we will use this property later to show that if desired, we can replace the waiting step in Batch with runs of a greedy algorithm, producing a hybrid algorithm that always makes a match when one is available and yet still achieves expected waiting time Θ( 1 p ).
The Batch algorithm has a parameter c > 0 and works in phases. At the start of each phase we wait c/p time, for c/p incoming nodes to arrive. We then run a procedure PATH that extends the current path. Then we start a new phase. Different implementation use different procedures PATH.
The following is a description of an implementation of PATH which we call FAIR-PATH. The procedure FAIR-PATH works as follows. Let Q be the set of waiting nodes at the start of the phase and let V f p be the set of c/p nodes that arrived since the start of the phase. We build a graph G f p (V f p , E f p ) where V f p are the c/p new arriving nodes. For each old node v ∈ Q, if there are new nodes u 1 , u 2 ∈ V f p , such that there are edges u 1 → v and v → u 2 , then we pick a random ingoing edge to v, say from u 1 , and a random outgoing edge from v, say to u 2 , and add an edge from u 1 → u 2 to E f p and label it by v. Namely, and a random u 2 ∈ OU T (v) and add the edge u 1 → u 2 to E f p and label it v. This defines the edges E f p , and if there are multiple parallel edges, we select one such edge at random.
Let v e be the end of the path at the end of the previous phase. We add v e to V f p and add its is empty, FAIR-PATH returns an empty extension.
We run the algorithm DFS-LP 5 from v e , and let path(v e ) be the path that it returns. We extend the current directed path using path(v e ) by adding for each edge the vertex which is its label, i.e., the nodes that caused the insertion of that edge.
Note that the extension path, path(v e ), alternates between nodes that arrive during the last phase, i.e., nodes from V f p , and nodes that arrive in previous phases, i.e., nodes in Q. If path(v e ) has ℓ edges in G f p then we are extending by 2ℓ − 1 nodes, where ℓ are from the recent phase, and ℓ − 1 are from previous phases.
Let |Q| be the number of nodes that remain from previous phases. We would like to consider nodes from Q that have at least one incoming and one outgoing degree from V f p . The expected number of such nodes is at least |Q|(1 − 2(1 − p) c/p ) ≈ |Q|(1 − 2e −c ) and for c ≥ 10 with high probability it is at least 0.9Q m.
We now show a simple property of a random graph where the number of edges is fixed, but the actual edges are selected uniformly at random. Specifically, we consider now a random graph with n = c/p nodes and m edges, where the edges are selected at random with replacements, so there might be multiplicities. We show that if the number of edges is large enough, any two disjoint subsets of size k will share an edge.
Lemma 7.1. A random graph with n nodes and m ≥ (n 2 /k log(n/(kδ)) random edges, with probability 1 − δ, for any two disjoint sets for size k there is an edge joining them.
Proof. For the proof, we do a union bound over all pairs of disjoint subsets of size k. For a fixed disjoint sets S 1 and S 2 of size k, the probability that a given edge will select to connect them is k 2 /n 2 . Therefore, the probability that there are two such sets which do not share an edge is bounded by, where the last inequality uses the assumption that m ≥ (n 2 /k) log(n/(kδ).
Theorem 7.2. For p < 0.04 and c > 10, the expected waiting time in the Batch algorithm with parameter c is O(c/p) and with probability 1 − δ it is at most O((c/p) log(1/δ)).
Proof. Let Q t be the number of waiting nodes at the end of phase t. We would like to show that the Q t forms a (M, K, ρ, β) random walk. However, the increase of Q t can be c/p (rather than 1 in the (M, K, ρ, β) random walk). For this reason we scale each c/p nodes as a "one unit", and show the bound for the (M, K, ρ, β) random walk. At the end we multiply by c/p to get the correct bound.
Let n = c/p, k = n/10, and M = (n 2 /k) log(n/(kδ) = (10c/p) log(10/δ). Once we scale down by c/p and set δ = 0.1 we have M = 10 log(100). We like to compute the probability of decrease and its magnitude. We need the magnitude to be at least c/p to have a net decrease (which is 1 after the scaling).
First we show that if there are many waiting nodes, then with high probability we have many edges in G f p . Assume that |Q t | ≥ M + 1 and m = 0.9|Q t |. For any v ∈ Q t , the probability that This implies that with probability at least 1−2e −c there is an edge labeled by v. The probability that we have a duplicate edge is 2|Q t |/(c/p) 2 , so the expected number of edges is at least |Q t |(1 − p 2 /c 2 − 2e −c ). For p < 0.04 and c ≥ 10 we have that |E f p | < m with probability at most 2e −10 .
By Theorem 3.1, for such a (M, K, ρ, β) random walk, we have that the expected value is at most 100 log(100) + 10 = O(1) and with probability 1 − δ it is at most O(log(1/δ)). Scaling back by c/p derives the theorem.

Not a short path
A clear drawback of the greedy algorithm is that in many cases it generates rather short paths to be added. The Not A Short Path (NASP) algorithm will overcome this weakness by requiring that the length of the path that we add is "not short". Specifically, the algorithm will have a parameter c > 0 and it will add only paths of length at least θ = c/p. This will clearly overcome the issue of adding short paths. The challenge is that now the duration of a phase (the time between two consecutive extensions of the path) is a random variable. It is worthwhile to compare the NASP algorithm to the batch algorithm. While in the batch algorithm the duration of a phase is fixed and the length of the extension is a random variable, in NASP the duration of a phase is a random variable and the length of the extension has a fixed lower bound (we allow to add longer paths).
The algorithm NASP works in phases. In each phase, as in the batch algorithm, the goal is to build an extension to the path built from both new and old nodes. The main difference is that a phase does not have a pre-specified number of new nodes (unlike the batch algorithm which had exactly c/p new node arrivals). The phase ends when we find an extension path of length at least θ = c/p nodes. Therefore in NASP the duration of a phase is a random variable while the length of the path is always at least θ = c/p. In contrast, in the batch algorithm, the size of the phase is fixed to be c/p while the length of the extension path is a random variable.
The analysis bounds the expected duration of a phase, i.e., the expected time it takes until we have such a path. Let Q t be the set of waiting nodes at the start of the phase t. Our analysis will have two cases depending on the number of waiting nodes nodes |Q t | at the start of the phase t. If the number of waiting nodes at the start of the phase is small, we show that the expected duration of the phase is not too large. We will not claim much about the outcome of such a phase, just that it ends in expected O(c/p) time. If the number of waiting nodes at the start of the phase is large, we show that with reasonable probability the number of waiting nodes will decrease (compared to the start of the phase). We start by considering the duration of a phase when the number of waiting nodes is arbitrary (actually, the worse case would be no waiting nodes). Proof. Note that we make no assumption about |Q t |, the number of waiting nodes at the start of the phase. For the proof we consider only the new arriving nodes in the phase (implicitly assuming that |Q t | = 0). After n = 1.2c/p we have a G(n, p) random graph. The probability that there exists two subsets of size k = 0.1c/p nodes that do not share an edge is Therefore, with probability 1 − e −30 , we have that every two subsets of size k = 0.1c/p share an edge. By Lemma A.1 This implies that the graph has a path of length at least c/p.

Corollary 8.2.
For θ = c/p, the expected duration of a phase is at most 1.21c/p.
Proof. By Lemma 8.1 we have that after 1.2c/p new nodes we have a path of length c/p with probability 1 − e −30 > 0.999. This implies that the expected time is at most 1.21c/p.
In the above case we consider only the new nodes (implicitly assumed Q t = ∅). Not surprisingly, the number of waiting nodes is likely to increase in such a case. The main benefit of NASP is that in the case that there are many waiting nodes at the start of the phase (|Q t | is large) then we expect that the number of waiting nodes will decrease. Similar to the batch algorithm ,we can show, Claim 8.3. If |Q t | ≥ (10c/p) log(10/δ) then after n = 0.625c/p new nodes, with probability 1 − δ the expected length of the path is at least c/p.
The main concern in the analysis has two folds. The first and the easier case, is how long a phase would last, in expectation, since the number of waiting nodes is the sum of the original waiting nodes and the new arriving nodes. By Corollary 8.2 this would be at most O(c/p). The second, and more involve, is bounding the expected number of waiting nodes at the end of the phase. Proof. In case that at the start of the phase we have |Q t | ≤ 10(c/p) log(10/δ), at the end of the phase we have an expected increase in the number of waiting nodes, which is the expected duration of the phase minus the length of the path, which is at most 1.21c/p − c/p = 0.21c/p, using Corollary 8.2.
The proof is similar to the proof of Theorem 7.2. Let Q t be the number of waiting nodes at the end of phase t. We would like to show that the Q t forms a (M, K, ρ, β) random walk. Again, we scale each 0.625c/p nodes as a "one unit", and show the bound for the (M, K, ρ, β) random walk. At the end we multiply by 0.625c/p to get the true bound.

Combined Greedy-Batch Algorithm
In this section we present an algorithm that combines Greedy and Batch in a simple way, and achieves O(1/p) expected waiting time. While the guarantee is not better than Batch, the combined algorithm has the appealing property that it always makes a match whenever a match from the current end-of-path exists.
The idea of the combined algorithm is to run Batch, maintaining a set Q of "old" nodes and a set V f p of "new" nodes that have arrived since the start of the current phase. However, instead of simply waiting for V f p to reach size c/p, if a node arrives with an in-edge from the current end-of-path v e , then we run Greedy. That is, if V f p has size less than c/p and a node arrives that can be matched, we run Greedy; if V f p has size greater than or equal to c/p and a node arrives that can be matched, we run FAIR-PATH.
To analyze this algorithm, we use one of the key properties of Greedy, which is that given multiple out-edges to choose from, it always chooses the edge to the node that has been waiting longest, regardless of any structural properties of the nodes. Therefore, after each run of Greedy, the nodes still in V f p (i.e., not yet matched) remain uniform random, except for the new end of path v e . Thus, except for an additional expected 1/p nodes needed to produce the first out-edge from v e after V f p has reached size c/p, the analysis of each phase of Batch is just as before.
The one change to the overall analysis of Batch is that the length of each phase is no longer exactly c/p but is rather a random variable. In particular, in addition to the expected 1/p nodes needed to produce the first out-edge from v e after V f p reaches size c/p, there is also the number of new nodes ∆ matched in runs of Greedy during the phase. This is potentially a concern because in the (rare) event that the set Q of old nodes is large, if ∆ is also large in this phase then this increases the average overall queue size. However, note that by definition of Greedy, if the current node has any edge to an old node, then such an edge will be taken since the old nodes by definition have been waiting longer than the new nodes. Moreover if Q has size greater than c ′ /p for sufficiently large c ′ , a new node will have probability at least 0.9 of having an edge to an old node. Therefore, if Q is large, then the expected number of old nodes matched by Greedy in this phase is at least 0.9∆ large , where ∆ large is the number of new nodes matched by Greedy in the current phase while Q has size greater than c ′ /p. Therefore, we can charge matches of new nodes by Greedy in intervals where Q is large to progress in decreasing the size of Q. In particular, if Q is large then for every c/p new nodes matched by Greedy we make at least as much progress in reducing Q as in a phase of Batch.
Similar to Theorem 7.2 we have,

Multiple altruistic donors
Recall that we extend our model as follows. Assume we have R multiple donors. Each donor will create a path, so we have R disjoint paths.
It is very surprising that having a small number (less than 1/p) of multiple donors does not significantly reduce the expected waiting time. On the other hand, if we have a large number of multiple donors (more than (1/p) log(1/p)) then the greedy algorithm have a constant expected waiting time. We remark, that conditioned on the fact that a node is not matched immediately, the waiting time of the mode is Ω(1/p). Proof. Consider the case that R ≤ 1/p. Assume that the number of waiting nodes q t is at most 1/p (otherwise we are done). When a new node arrives, with probability at least 1/e it does not have any incoming edge, and therefore it clearly cannot be immediately added to any of the current R paths. Conditioned on the fact that the new incoming node does not have any incoming edges, the expected time until the new node will have some incoming edge is 1/p, so the expected waiting time is at least 1/(ep). Since either q t ≥ 1/p or if q t ≤ 1/p then with probability at least 1/e we have w t ≥ 1/p, which implies that E[q t ] + E[w t ] ≥ 1/(ep). Similar to Theorem 4.1, we have that the expected waiting time is at least Ω(1/p).
For R ≥ (1/p) log(1/p) we have that the probability that a new node v t is not matched immediately at time t is (1 − p) R ≤ p. At any future time τ > t, the probability that v t is added to some path is at least the probability that v τ is immediately add and there is an edge v τ → v t , i.e., This implies that the waiting time of v t , until it is matched is at most 1/((1 − p)p). Therefore the expected waiting time is O(1). Equivalently, the expected queue size is O(1).
We remark that the expected additional waiting for a node which is not matched immediately, is Ω(1/p). Therefore, the O(1) waiting time is mainly due to nodes which are matched immediately as they arrive.

Future Directions
In this paper we have focused on a clean sparse random graph model in which each edge (u, v) is present with some small probability p. This model can be viewed as a setting in which patients are all highly sensitized (so p is low) and all bring an O-donor (so we do not need to consider blood-type incompatibility), and was studied in the static case in [6].
A more complex model would incorporate blood-type incompatibility, as done in the static densegraph case in [8,9]. One challenge here from the online perspective is that if the probability of an O-donor is the same as the probability of an O-patient, then no method can produce bounded queue sizes. In particular, if we define the random variable X to be the number of O-patients seen minus the number of O-donors seen, or zero if that difference is negative, then the queue size must be at least X, and after t time-steps E[X] = Ω( √ t). So, no matter what algorithm is used for extending the altruistic donor path, queue sizes will grow with t.
However, an interesting model to consider for future work would be one where patients are "encouraged" to bring O-donors, though not 100% of them do. An interesting question there would be how large a fraction of O-donors would be needed to achieve the bounded queue sizes we get in the model studied here.

A Long paths in random graphs
In this Appendix we include the results regarding long paths in random graphs. The following lemma from [16] has the essence of the methodology of generating long paths using DFS.
Lemma A.1 ([16]). Given a graph G(V, E) such that for any two disjoint subsets S 1 , S 2 ⊂ V of size at least k there is an edge, then the DFS will return a path of length at least |V | − 2k.
Lemma A.2. Given a graph G(V, E) such that between any two disjoint subsets S 1 , S 2 ⊂ V of size at least k there is an edge, assuming that |V | ≥ 3k, then G has a connected component of size at least |V | − k + 1 Proof. Assume for contradiction that all the connected components of G are of size at most |V | − k. Let C 1 , . . . , C m be the connected components of G. Clearly m ≥ 2, otherwise we have a single connected component of size |V |. If m = 2 then |C 1 | + |C 2 | = |V |, therefore for one connected component, say This implies that we have two subsets, C 1 and C 2 , each of size at least k, which do not share an edge. contradiction.
For m ≥ 3, assume that |C 1 | ≥ · · · ≥ |C m |. Clearly, if |C 1 | ≥ |V | − k + 1 we are done. If |C 1 | ≥ k but |C 1 | ≤ |V | − k, then we have a contradiction by considering S 1 = C 1 and S 2 = V − C 1 , since Note that this implies that since all the connected components are of size at Corollary A.3. Given a graph G(V, E) such that between any two disjoint subsets S 1 , S 2 ⊂ V of size at least k there is an edge, assuming that |V | ≥ 3k, any set of S 3 of at least k nodes has some v ∈ S 3 which belongs to a connected component of size at least |V | − k + 1.
Corollary A.4. Given a graph G(V, E) such that between any two disjoint subsets S 1 , S 2 ⊂ V of size at least k there is an edge, assuming that |V | ≥ 3k, for any set of S 3 of at least k nodes has some v ∈ S 3 which has a path of length |V | − 2k.
Proof. By Corollary A.3 there is a node v ∈ S 3 which belongs to a connected component of size at least |V |− k + 1. Consider the DFS from node v. At any time while the number of nodes not visited is at least k, the number of nodes from which the DFS backtracked is at most k − 1. Otherwise the set of nodes backtracked and the set of nodes not visited are both at least size k and they are disjoint, which is a contradiction to the hypothesis in the corollary.

B Random walks
In this section we outline the proof of Theorem 3.1.
We define a new random walk Y t that stochastically dominates Q t . Similar to Q t we have Y 1 = 0, and Y t+1 = Y t +1 or Y t+1 = max{Y t −Z t , M }. However, if Y t ≥ M +1 then Z t = K with probability ρ and otherwise Z t = 0. As before, ρK = 1 + β where β > 0.
We consider the steady state distribution of the random walk Y t , where s ℓ is the probability that Y t = ℓ for ℓ ≥ M . The steady state probability need to satisfy the following identities.
∀ℓ ≥ M + 1 s ℓ+1 = (1 − ρ)s ℓ + ρs ℓ+K+1 (1) The first identity implies that to reach a value of Y t+1 = ℓ + 1 either Y t = ℓ and Y t+1 = Y t + 1 or Y t = ℓ + K + 1 and Z t = K. The second identity states that to reach Y t+1 = M then Y t ∈ [M + 1, M + K] and Z t = K. The last two identities simply state that s ℓ is a distribution.
Claim B.1. the expected value of Y t is at most M + k x < M + k(1+β ′ ) 2β ′ .
Proof. The claim follows by considering the steady state distribution: For the high probability we have the following.
A . Using the value of A we have that α A ≤ ck(1+β ′ ) 2β ′ δ , and therefore, the probability is bounded by δ.