Analysis of an optimal policy in dynamic bipartite matching models

Performance Evaluation 154 (2022) 102286 Contents lists available at ScienceDirect Performance Evaluation journal homepage: www.elsevier.com/locate/peva Analysis of an optimal policy in dynamic bipartite matching models Arnaud Cadas a,b, Josu Doncel c,∗, Ana Bušić a,b aInria, Paris, France bDépartement d’informatique de l’ENS, ENS, CNRS, PSL University, Paris, France cUniversity of the Basque Country, UPV/EHU, Leioa, Spain article info Article history: Received 16 June 2021 Received in revised form 1 December 2021 Accepted 15 February 2022 Available online 22 February 2022 Keywords: Dynamic matching models Optimal control Markov decision process abstract A dynamic bipartite matching model is given by a bipartite matching graph which determines the possible matchings between the various types of supply and demand items. Both supply and demand items arrive to the system according to a stochastic process. Matched pairs leave the system and the others wait in the queues, which induces a holding cost. We model this problem as a Markov Decision Process and study the discounted cost and the average cost problem. We assume that the cost function is linear on the queue sizes. We show that for the N-shaped matching graph, an optimal matching control prioritizes the matchings in the pendant edges and is of threshold type for the diagonal edge. In addition, for the average cost problem, we compute the optimal threshold value. We then show how the obtained results can be used to characterize the structure of an optimal matching control for a quasi-complete graph with an arbitrary number of nodes. For arbitrary bipartite graphs, we show that, when the cost of the pendant edges is larger than in the neighbors, an optimal matching policy prioritizes the items in the pendant edges. We also study the W-shaped matching graph and, when the cost of the pendant edges is larger than the cost of the middle edge, we conjecture that an optimal matching policy is also of threshold type with priority to the pendant edges; however, when the cost of the middle edge is larger, we present simulations that show that it is not optimal to prioritize items in the pendant edges. ©2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/). 1. Introduction We study matching models with a bipartite compatibility graph. In this model, one supply and one demand item arrive to the system in each time slot according to a given stochastic process. Compatible supply and demand items can be matched, in which case they leave the system, and items that are not matched stay in the system. We assume that supply and demand items are divided in classes. Thus, each class of supply items is compatible with a different subset of demand item classes and, likewise, each class of demand items is compatible with a different subset of supply item classes. In Fig. 1 we represent an example of a compatibility graph with three demand nodes and three supply nodes. In this case, when the system is empty and there is an arrival of the demand class 2 and the supply class 2, the arriving items can be matched and leave the system. However, in case of an arrival of the demand class 1 and the supply class 3 when the system is empty, both items stay in the system since they cannot be matched. ∗Corresponding author. E-mail address: [email protected] (J. Doncel). https://doi.org/10.1016/j.peva.2022.102286 0166-5316/©2022 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons. org/licenses/by-nc-nd/4.0/). A. Cadas, J. Doncel and A. Bušić Performance Evaluation 154 (2022) 102286 Fig. 1. A matching graph with three supply classes and three demand classes. Once the compatibility graph and the probability distribution of arrivals of supply and demand classes are fixed, the stochastic process of the number of items present in the system depends clearly on how compatible items are matched, i.e., on the matching policy. For instance, the First Come First Matched policy is a popular matching policy that consists of matching the incoming items with the oldest compatible items, if any. Another example is the Matching the Longest policy, which matches each incoming item with its compatible item with the largest number of items (or the largest queue). Unmatched supply and demand items incur a cost (for instance, when the available kidneys are not compatible with the patient that requires the donation). An optimal matching policy can be hence defined as how items are matched so as to minimize the cost of the system. In this work, we consider bipartite matching graphs and we aim to characterize the optimal matching policy for this case. When the compatibility graph is complete, since supply and demand items arrive in pairs, any newly arriving pair can be matched, so there is never any queue. This shows that an optimal matching control consists of matching all the items for this matching graph. For the rest of the compatibility graphs, the characterization of an optimal matching policy is not that easy. Indeed, we model this problem as a Markov Decision Process and use arguments of structured policies in this article. We consider the discounted cost problem as well as the average cost problem. We assume that the instantaneous cost is a linear function on the queue sizes (i.e., on the number of items of each class). The main contributions of this article are summarized as follows: •We first consider the N-shaped matching graph, which is formed by two supply and two demand classes. For this system, we show that an optimal matching policy matches all the items of the pendant edges and is of threshold type in the diagonal edge. Furthermore, for the average cost problem, we provide an analytical expression of the optimal threshold. •We then focus on quasi-complete matching graphs with an arbitrary number of supply and demand nodes. We provide conditions on the holding costs under which a threshold type policy has the same cost as a threshold type policy of the N-shaped graph. As a result, using that an optimal matching policy for the N-shaped graph is of threshold type, we show that an optimal policy of a quasi-complete graph with an arbitrary number of supply and demand nodes is also of threshold type. •We study optimal matching policies of an arbitrary bipartite graph in which the holding cost of each pendant edge is larger than the holding cost of its neighbors. For this case, we show that an optimal matching policy consists of matching all the items of the pendant edges. •Finally, we consider the W-shaped graph, which is formed by two supply and three demand classes. We differentiate two cases. First, we consider that the cost of the pendant demand nodes is larger than of the middle demand node. We present the properties that the value function must satisfy to prove that an optimal matching policy is of threshold type with priority to the pendant edges. Unfortunately, given the difficulty of these properties, we did not succeed in showing that these properties are preserved by the Dynamic Programming operator. However, we show that, if there is a set of properties (containing those required to show the optimality of the threshold type policy) that are preserved under the Dynamic Programming operator, an optimal matching policy is of threshold type with priority to the pendant edges for this case. Furthermore, we consider the case when the cost of the pendant nodes is smaller than of the middile demand node. For this case, we present our numerical work that shows that the matching policy that prioritizes the pendant edges is not optimal. A conference version of this article appeared in [1]. The remainder of the article is organized as follows. In Section 2, we put our work in the context of the existing literature. In Section 3, we describe the optimal control problem we investigate in this paper. We characterize an optimal matching policy for the N-shaped graph in Section 4. Then, in Section 5we study the optimal policy of a quasicomplete matching graph and in Section 6of arbitrary bipartite matching graphs. We also consider in Section 7the W-shaped matching graph. Finally, we provide the main conclusions of our work in Section 8. 2. Related work The study of how to optimally match compatible items has been widely studied. This problem was introduced by with Petersen and König and it was analyzed first considering that the population is fixed. For this case, its known that the 2 A. Cadas, J. Doncel and A. Bušić Performance Evaluation 154 (2022) 102286 Hopcroft–Karp algorithm [2] solves this problem in a bipartite graph with a time complexity of O(m√n) where mis the number of edges and nis the number of nodes. We refer to [3, Table I] for a historical review of algorithms that compute maximum matchings. Then, this problem was extended to the dynamic setting in which one population is static and the other arrives according to a stochastic process [4–7]. Our work differs from this large literature since we explore fully dynamic matching models, i.e., all the items arrive to the system according to a random process. In 1984, Kaplan studied the tenant assignment process of public housing in Boston [8] in which, when a public housing unit becomes available, it is assigned to the longest waiting family that listed the corresponding housing project. Kaplan was interested in the matching rate, i.e., the fraction of families having the same preferences that are assigned to a specific housing project. The authors in [9] modeled this problem as the First Come First Served (FCFS) infinite bipartite matching model. This problem is defined by a connected bipartite graph, where nodes represent the class of items and the edges their compatibilities. Several articles followed the aforementioned work. The authors in [10] provided necessary and sufficient conditions for the ergodicity of the Markov chain associated to this model. They also proved the product form of its stationary distribution. Furthermore, the authors in [11] considered a more detailed Markov chain and proved its reversibility. The authors in [12] showed that the stationary distribution of the FCFS infinite bipartite matching model coincides with that of the following queueing systems: the redundant model of [13] and the skill-based parallel server system of [14]. In [15] the authors considered the bipartite matching model with other matching policies such as Last Come First Served, Random, Match the Longest and Priority and established necessary and sufficient conditions for the stability of these models. They also showed that the Match the Longest policy has the maximum stability region and introduced the Extended Bipartite Matching Model, which extends the FCFS infinite matching policy by considering any joint distribution for the classes of arrival pairs. We would like to remark that some authors also investigated matching models where the compatibility graph is not bipartite. This alternative model was introduced by [16] and the main particularity is that items arrive to the system one by one. The authors in [17] showed that the stationary distribution of items for this model with the FCFS matching policy satisfies a product-form expression. In this work, we aim to find study an optimal matching policy with holding costs on the size of the queues. The authors in [18] also considered holding costs on the size of the queues in a non-bipartite matching model and for the finite horizon case. In our work, we consider a bipartite matching model and the discounted and average problems. Indeed, to the best of our knowledge, optimality results for bipartite matching models have been obtained only in asymptotic regimes. The authors in [19] analyze the heavy-traffic regime in which the difference between the arrivals of one item class and its compatible items tends to zero for the average cost problem and derive a new matching policy that is asymptotically optimal with bounded regret. A related optimization problem of maximizing rewards on edges has been considered in [20]. In that paper, the authors consider compatibilities given by a hypergraph and develop a matching policy based on an extension of the Greedy Primal–Dual algorithm and, using fluid limits, they show asymptotic optimality of their algorithm. One of the main contributions of this work is to show the optimality of threshold-type matching policies in dynamic bipartite matching graphs. Similar policies have been also studied in a different context in which the goal is to optimally assign jobs to servers. For instance, the authors in [21,22] consider that N-shaped model and show that there is a threshold policy that is asymptotically optimal. The authors in [23] extended this result to a parallel server system with an arbitrary topology. 3. Model description We consider a bipartite matching graph (D∪S,E) where D= {d1,d2,...,dnD}and S= {s1,s2,...,snS}are, respectively, the set of demand nodes (or queues) and the set of supply nodes. E⊂D×Sis the set of allowed matching pairs. In each time slot n, a demand item and a supply item arrive to the system according to the i.i.d. arrival process A(n). We assume independence between demand and supply arrivals. The demand item arrives to the queue diwith probability αiand the supply item arrives to the queue sjwith probability βj, i.e: ∀(i,j)∈AP(A(n)=e(i,j))=αiβj>0 with ∑nD i=1αi=1, ∑nS j=1βj=1 and where A=D×Sis the set of allowed arrival pairs, e(i,j)=edi+esjand ek∈NnD+nS is the vector of all zeros except in the kth coordinate where it is equal to one, k∈D∪S. We assume that the αiand βj are chosen such that the arrival distribution satisfies the necessary and sufficient conditions for stabilizability of the MDP model: Ncond given in [24], i.e. ∀D⊊D,∀S⊊S: ∑ di∈D αi<∑ sj∈S(D) βjand ∑ sj∈S βj<∑ di∈D(S) αi(1) where D(j)= {i∈D:(i,j)∈E}is the set of demand classes that can be matched with a class jsupply and S(i)= {j∈S:(i,j)∈E}is the set of supply classes that can be matched with a class idemand. The extension to subsets S⊂Sand D⊂Dis D(S)=⋃j∈SD(j) and S(D)=⋃i∈DS(i). The main notation of this article is presented in Table 1. 3 A. Cadas, J. Doncel and A. Bušić Performance Evaluation 154 (2022) 102286 Table 1 Summary of the main notation of this article. D= {d1,d2,...,dnD}Set of demand nodes S= {s1,s2,...,snS}Set of supply nodes αiProbability that a demand item arrives to node di βiProbability that a supply item arrives to node si (i,j) Edge that connects diand sj ediThe dith vector of the canonical basis of RnD+nS esjThe nD+sjth vector of the canonical basis of RnD+nS e(i,j)The sum of ediand esj(i.e., e(i,j)=edi+esj) D(j) The set of demand classes that can be matched with sj S(i) The set of supply classes that can be matched with di Q(n)=(qk(n))k∈D∪SVector of queue lengths at time slot n X(n)=(xk(n))k∈D∪SVector of queue lengths at time slot nafter arrivals UxSet of admissible matchings when the vector of lengths after arrivals is x ckHolding cost of node k∈D∪S We denote by qk(n) the queue length of node kat time slot n, where k∈D∪S. Let Q(n)=(qk(n))k∈D∪Sbe the vector of the queue length of all the nodes and Q= {q∈NnD+nS:∑k∈Dqk=∑k∈Sqk}be the set of all the possible queues length. We must have q(n)∈Qfor all n. Matchings at time nare carried out after the arrivals at time n. Hence, Q(n) evolves over time according to the following expression: Q(n+1) =Q(n)+A(n)−u(Q(n),A(n)),(2) where uis a deterministic Markovian decision rule which maps the current state Y(n)=(Q(n),A(n))to the vector of the items that are matched at time n. Thus, Yis a Markov Decision Process where the control is denoted by u. It is sufficient to consider only deterministic Markovian decision rules and not all history-dependent randomized decision rules as proved in [25, Theorem 5.5.3] and [25, Proposition 6.2.1]. Let us define X(n)=Q(n)+A(n) as the vector of the queue length of all the nodes just after the arrivals. In order to ease the notations and because the matchings only depend on the queues length after the arrivals, we use the following notation in the remainder of the paper: u(Q(n),A(n)) =u(X(n)). When the state of the system is Y(n)=(q,a), x=q+a,u(x) must belong to the set of admissible matchings which is defined as: Ux=⎧ ⎨ ⎩ u=∑ (i,j)∈E u(i,j)e(i,j)∈NnD+nS:(a)∀i∈D,∑ k∈S(i) u(i,k)≤xdi,(b)∀j∈S,∑ k∈D(j) u(k,j)≤xsj⎫ ⎬ ⎭ (3) where u(i,j)is the number of matchings in the edge (i,j). Uxis defined for all x∈Q. We consider a linear cost function on the buffer size of the nodes: c(Q(n),A(n)) =c(X(n)) =∑k∈D∪Sckxk(n). A matching policy πis a sequence of deterministic Markovian decision rules, i.e. π=(u(X(n)))n≥1. The goal is to obtain an optimal matching policy for two optimization problems: •The average cost problem: g∗=inf πgπwith gπ(y)=lim N→∞ 1 N N−1 ∑ n=0 Eπ y[c(Y(n))] •The discounted cost problem: v∗ θ=inf πvπ θwith vπ θ(y)=lim N→∞ N−1 ∑ n=0 θtEπ y[c(Y(n))] where θ∈ [0,1) is the discount factor and y∈Y=Q×Ais the starting state. Both problems admit an optimal stationary policy, i.e. the decision rule depends only on the state of the system and not on the time [25]. The notation Eπ yindicates that the expectation is over the arrival process, given that Y(0) =yand using the matching policy πto determine the matched items u(X(n)) for all n. As A(n) are i.i.d., to ease the notation from now on, we denote by Aa random variable with the same distribution as A(1). For a given function v,Y(n)=(q,a), x=q+a,u∈Ux, we define for all 0 ≤θ≤1: Lθ uv(q,a)=c(q,a)+θE[v(q+a−u,A)] = c(x)+θE[v(x−u,A)] Lθv(q,a)=c(q,a)+min u∈Ux θE[v(q+a−u,A)] = c(x)+min u∈Ux θE[v(x−u,A)] and in particular, we define Tu=L1 uand T=L1. A solution of the discounted cost problem can be obtained as a solution of the Bellman fixed point equation v=Lθv. In the average cost problem, the Bellman equation is given by g∗+v=Tv. We say that a value function vor a decision rule uis structured if it satisfies a special property, such as being increasing, decreasing or convex. Throughout the article, by increasing we mean nondecreasing and we will use strictly increasing 4 A. Cadas, J. Doncel and A. Bušić Performance Evaluation 154 (2022) 102286 Fig. 2. The N-shaped matching graph. for increasing. For a collection of properties σ, we denote by Vσthe set of structured value functions that satisfy those properties. Similarly, we define Dσas the set of structured decision rules induced by those structured value functions. A policy is called structured when it only uses structured decision rules and the set of structured stationary matching policies is denoted by Πσ= {π=(u(X(n)))n≥1:u∈Dσ}. The framework of this work is that of property preservation when we apply the Dynamic Programming operator. For the average cost problem, we use an adapted version of [23,Theorem 6.11.3] and we proceed to characterize the structure of an optimal matching policy as follows: first, we identify a set of structured value functions Vσand a set of structured deterministic Markovian decision rules Dσsuch that if the value function belongs to Vσan optimal decision rule belongs to Dσ. Then, we show that the properties of Vσare preserved by the Dynamic Programming operator, i,e. that Lv∈Vσif v∈Vσ. Finally, we show that these properties hold in the limit as well. In the case of the average cost problem, our proofs are based on [23,Theorem 8.11.1], which uses the results of the discounted cost problem. In fact, the average cost problem is considered as a limit when θtends to one and, therefore, it is enough to show that the properties still hold for this limit. The statement of the theorems we use for the discounted cost problem and the average cost problem are provided in Appendix A. These theorems present some technical requiments due to the unboundness of the costs. In Appendix A we show that the technical requirements of the theorems we use are satisfied and, therefore, when we study an optimal matching policy in the discounted cost problem, we only need to check that conditions (a), (b) and (c) of Theorem 6 are verified, i.e,. (a) v∈Vσimplies that Lθv∈Vσ; (b) v∈Vσimplies that there exists a decision u′∈Dσsuch that u′∈arg minuLθ uv; (c) Vσis a closed subset of the set of value functions under pointwise convergence. whereas when we study an optimal matching policy in the average cost problem, we only need to check that conditions (a) and (b) of Theorem 7 are verified, i.e., (a) for any sequence (θn)n≥0, 0 ≤θn<1, for which lim n→+∞θn=1, lim n→+∞[v∗ θn−v∗ θn(0)e] ∈ Vσ Hwith e(y)=1 for all y∈Y (b) v∈Vσ Himplies that there exists a decision u′∈Dσsuch that u′∈arg minuTuv; 4. N-Shaped graph We now focus on the N-shaped matching graph, which is formed by two supply nodes and two demand nodes as well as a N-shaped set of edges (see Fig. 2). Specifically, we have D= {d1,d2},S= {s1,s2}and E= {(1,1),(1,2),(2,2)}. We also define (2,1) as the imaginary edge between d2and s1(imaginary because (2,1) /∈E) that we introduce to ease the notations. To ensure stability, we assume that α > β. In this section, we show that an optimal policy for the N-shaped matching graph has a specific structure. For this purpose, we first present the properties of the value function. Then, we show how these properties characterize the optimal decision rule and how they are preserved by the Dynamic Programming operator. Finally, we prove the desired results in Theorems 1 and 2. 4.1. Value function properties We now present the properties of the value function. We first define the increasing property as follows: Definition 1 (Increasing Property).Let (i,j)∈E. We say that a function vis increasing in (i,j) or v∈I(i,j)if ∀a∈A,∀q∈Q, v(q+e(i,j),a)≥v(q,a). 5 A. Cadas, J. Doncel and A. Bušić Performance Evaluation 154 (2022) 102286 Remark 1. The increasing property in (2,1) can be interpreted as the preference to match items of (1,1) and of (2,2) than of (1,2). Indeed, v(q+e(1,1) +e(2,2) −e(1,2),a)=v(q+e(2,1),a)≥v(q,a). We now define the convexity property as follows: Definition 2 (Convexity Property).A function vis convex in (1,2) or v∈C(1,2) if ∀a∈A,∀q∈Qsuch that qd1≥qs1, we have v(q+2e(1,2),a)−v(q+e(1,2),a)≥v(q+e(1,2),a)−v(q,a). Likewise, vis convex in (2,1) or v∈C(2,1) if ∀a∈A,∀q∈Qsuch that qs1≥qd1, we have v(q+2e(2,1),a)−v(q+e(2,1),a)≥v(q+e(2,1),a)−v(q,a). We also define the boundary property next: Definition 3 (Boundary Property).A function v∈Bif ∀a∈A, v(0,a)−v(e(2,1),a)≤v(e(1,2),a)−v(0,a). We remark that, the properties I(1,1),I(2,2),I(2,1) and C(1,2) are used to characterize the optimal decision rule, whereas C(2,1) and Bare required to show that C(1,2) is preserved by the operator Lθ. In the remainder of the section, we consider the following set of structured value functions Vσ=I(1,1) ∩I(2,2) ∩I(2,1) ∩C(1,2) ∩C(2,1) ∩B,(4) which means that we consider that the value function satisfies the following properties: it is increasing with (1,1), (2,2) and (2,1), convex in (1,2) and (2,1) and satisfies the boundary property. 4.2. Optimal decision rule A decision rule is of threshold type in (1,2) with priority to (1,1) and (2,2) if it matches all the items of (1,1) and (2,2) and it matches the items of (1,2) only if the remaining items (in d1and s2) exceed a specific threshold t∈N∪∞. The decision rule of threshold type in (1,2) with priority to (1,1) and (2,2) is defined formally now. Definition 4 (Threshold-type Decision Rule).A decision rule uxis of threshold type in (1,2) with priority to (1,1) and (2,2) when ux=min(xd1,xs1)e(1,1) +min(xd2,xs2)e(2,2) +kt(x)e(1,2) where kt(x)={0,if xd1−xs1≤t, xd1−xs1−t,otherwise. Let us note that if t= ∞, the above decision rule consists of never matching (1,2). However, if t<∞, the decision rule matches the items of (1,2) until the remaining items in d1and s2after matching all the possible items in (1,1) and (2,2) do not exceed the threshold t. In fact, the state of the system after a decision rule of threshold type in (1,2) with priority to (1,1) and (2,2) is of the form (0,l,l,0) if xd1≤xs1, of the form (l,0,0,l) if xd1>xs1and l<tand the form (t,0,0,t) otherwise. In the rest of this section, we consider that Dσis the set of decision rules that are of threshold type in (1,2) with priority to (1,1) and (2,2) for any t∈N∪∞. We now show that there exists an optimal decision rule that matches all the items in (1,1) and (2,2). Proposition 1. Let v∈I(1,1) ∩I(2,2) ∩I(2,1) and 0≤θ≤1. For any q ∈Qand a ∈A, let x =q+a. Thus, there exists u∗∈Uxsuch that u∗∈arg minu∈UxLθ uv(q,a), u∗ (1,1) =min(xd1,xs1)and u∗ (2,2) =min(xd2,xs2). In particular, this result holds for the average operator: Tu. Proof. See Appendix B.□ From this result, it follows that there exists an optimal decision rule that matches all possible items of (1,1) and (2,2). We denote by Kxthe set of possible matching in (1,2) after matching all the items of (1,1) and (2,2). Definition 5. Let 0 ≤θ≤1, x∈Q. Then, Kx={{0},if xd1≤xs1, {0,...,min(xd1−xs1,xs2−xd2)},otherwise. We now prove that a decision rule of threshold type in (1,2) with priority to (1,1) and (2,2) is optimal. Proposition 2. Let v∈I(1,1) ∩I(2,2) ∩I(2,1) ∩C(1,2). Let 0≤θ≤1. For any q ∈Qand for any a ∈A, x =q+a, there exists u∗∈Dσsuch that u∗∈arg minu∈UxLθ uv(q,a). In particular, this result holds for the average operator: Tu. 6 A. Cadas, J. Doncel and A. Bušić Performance Evaluation 154 (2022) 102286 Proof. The idea of the proof is to show that for any admissible matching u, the matching u∗that prioritizes the pendant edges satisfies that Lθ u∗v(q,a)≤Lθ uv(q,a) for all qand a. Detailed proof is provided in Appendix C.□ 4.3. Value function property preservation In this section, we show that the properties of the value function defined in Section 4.1 are preserved by the Dynamic Programming operator. In other words, we show that if vis increasing with (1,1), (2,2) and (2,1), convex in (1,2) and (2,1) and satisfies the boundary property, so does Lθv. We first focus on the increasing property in (1,1), (2,2) and (2,1) and we show that they are preserved by the Dynamic Programming operator. Lemma 1. If a function v∈I(1,1) ∩I(2,2) ∩I(2,1), then Lθv∈I(1,1) ∩I(2,2) ∩I(2,1). Proof. The idea of the proof is to consider any qand aand define ¯ qas qwith two additional items for each edge we consider. Then, since v(q,a)≤v(¯ q,a) by assumption, it is enough to show that Lθv(q,a)≤Lθv(¯ q,a). Detailed proof is provided in Appendix D.1.□ We now aim to show that the convexity in (1,2) is preserved by the Dynamic Programming operator. It is important to note that Lθv∈C(1,2) when the value function is not only increasing in (1,1),(2,2) and (2,1) and convex in (1,2), but also satisfies the boundary condition. Lemma 2. If v∈I(1,1) ∩I(2,2) ∩I(2,1) ∩C(1,2) ∩B, then Lθv∈C(1,2). Proof. The idea of the proof is to consider any qand aand define ¯ qas qwith two additional items for each that we consider as well as ¯ ¯ qas ¯ qwith two more additional items in the same edge. Then, since v∈C(1,2), we know that v(¯ q,a)−v(q,a)≤v(¯ ¯ q,a)−v(¯ q,a) by assumption, it is enough to show that Lθv(¯ q,a)−Lθv(q,a)≤Lθv(¯ ¯ q,a)−Lθv(¯ q,a). Detailed proof is provided in Appendix D.2.□ Finally, to show that the Dynamic Programming operator preserves the boundary property, we need to use the convexity property in (2,1). The preservation of the boundary and the convexity properties are proven in the following lemma. Lemma 3. If v∈I(1,1) ∩I(2,2) ∩I(2,1) ∩C(1,2) ∩C(2,1) ∩B, then Lθv∈C(2,1) ∩B. Proof. For the Boundary condition, the idea is to show that Lθv(0,a)−Lθv(e(2,1),a)≤Lθv(e(1,2),a)−Lθv(0,a) for any a∈A, whereas for the convexity property we proceed similarly than in the proof of Lemma 2. Detailed proof is provided in Appendix D.3.□ 4.4. Structure of an optimal policy Now, using the result of Theorem 6, we show that there exists an optimal matching policy which is formed of a sequence of decision rules that belongs to Dσ(with a fixed threshold). Theorem 1. The optimal control for the discounted cost problem is of threshold type in (1,2) with priority to (1,1) and (2,2). Proof. We apply Theorem 6 where Vσis the set of functions defined in (4) and Dσthe set defined in Definition 4. We focus on the structural conditions of the theorem. From Lemmas 1–3 of Section 4.3, it follows (a) since they show that if v∈Vσ, then Lθv∈Vσ. The result of Proposition 2 shows (b) because the policy that belongs to Dσminimizes Lθ uvif v∈Vσ. Finally, since limits preserve inequalities, the point-wise convergence of functions of Vσbelong to this set, which shows (c). □ The following theorem shows that the previous result also holds for the average cost problem. Theorem 2. The optimal control for the average cost problem is of threshold type in (1,2) with priority to (1,1) and (2,2). Proof. We want to apply Theorem 7 using the same value function set Vσand the same decision rule set Dσas in the proof of the previous theorem. Assumptions (A1) to (A4) hold because of Lemma 9. Let (θn)n∈Nbe a sequence such that 0≤θn<1 for all n∈Nand lim n→+∞θn=1. Let n∈N. We know that v∗ θn∈Vσ(see the proof of Theorem 1). The inequalities in the definitions of the properties used in Vσstill hold if we add a constant to v, thus v∗ θn−v∗ θn(0)e∈Vσ. Using Assumption (A3) and Assumption (A4), we have H≤v∗ θn−v∗ θn(0)e≤M, so v∗ θn−v∗ θn(0)e∈Vσ H. This last result holds for each n∈Nand since limits preserve inequalities Vσ His a closed set, lim n→+∞[v∗ θn−v∗ θn(0)e] ∈ Vσ Hwhich shows (a). The result of Proposition 2 shows (b) because the policy that belongs to Dσminimizes L1 uv=Tuvif v∈Vσ H⊂Vσ.□ 7 A. Cadas, J. Doncel and A. Bušić Performance Evaluation 154 (2022) 102286 Fig. 3. A complete matching graph minus the edge (3,1). 4.5. Computing the optimal threshold We consider the matching policy of threshold type in (1,2) with priority to (1,1) and (2,2) in the average cost case. In this result, we provide an analytical expression of the threshold at which items of (2,1) are matched. Proposition 3. Let ρ=β(1−α) α(1−β)∈(0,1), R =cs1+cd2 cd1+cs2 and ΠT(1,2) be the set of matching policy of threshold type in (1,2) with priority to (1,1) and (2,2). The optimal threshold t∗, which minimizes the average cost on ΠT(1,2) , is t∗={⌈k⌉if f (⌈k⌉)≤f(⌊k⌋) ⌊k⌋otherwise where k =log ρ−1 (R+1) log ρ log ρ−1and f (x)=(cd1+cs2)x+(cd1+cd2+cs1+cs2)ρx+1 1−ρ−(cd1+cs2)ρ 1−ρ+((cd1+cs1)αβ +(cd2+ cs2)(1 −α)(1 −β)+(cd2+cs1)(1 −α)β+(cd1+cs2)α(1 −β)). The threshold t∗is positive. Proof. The idea of the proof is to look at the Markov chain derived from the policy u∞ t∈ΠT(1,2) . We show that the Markov chain is positive recurrent and we compute the stationary distribution. Using the strong law of large numbers for Markov chains, we show that the average cost gu∞ tis equal to the expected cost of the system under the stationary distribution. Then, we find an analytical form for the expected cost which depends on the threshold on (1,2), i.e, t. Finally, we minimize the function over t. Detailed proof is provided in Appendix E.□ From this result, it is important to note that the value of k(and therefore, the value of t∗) is increasing with ρand it tends to 0 when ρ→0 whereas it tends to infinity when ρ→1. This means that, when β≪α, the threshold is zero, i.e., an optimal matching policy always matches the items of the diagonal edge. On the other hand, when β→α(recall that α > β to ensure stability), we have that the threshold tends to infinity. This means that an optimal matching policy never matches items of the diagonal edge. 5. Optimal policy of quasi-complete graphs We aim to generalize the results of the N-shaped graph to a quasi-complete matching graph with an arbitrary number of supply and demand nodes. A quasi-complete matching graph is a matching graph where all the supply and demand nodes are connected, except for one supply node which is connected to all but one demand node. Let us denote a quasicomplete matching graph as G=(D∪S,E) with E=(D×S)\{(i∗,j∗)}, where (i∗,j∗) (i∗∈Dand j∗∈S) is the missing edge (see Fig. 3 for an example). We show that, under certain assumptions on the holding costs, this matching graph is related to the N-shaped matching graph. Hence, throughout this section, when we refer to the N-shaped matching graph we use the superscript N. First, we define the transformations to move from Y(the Markov Decision Process defined on G) to YN(the Markov Decision Process defined on GN). Definition 6. Let Qand Abe the sets of possible states and arrivals of G. Let QNand ANbe the sets of possible states and arrivals of GN. We define the projection from Qto QNand the projection from Ato ANas pN Q(q)=⎛ ⎝∑ i∈D(j∗) qdi,qdi∗,qsj∗,∑ j∈S(i∗) qsj⎞ ⎠and 8 A. Cadas, J. Doncel and A. Bušić Performance Evaluation 154 (2022) 102286 pN A(a)=⎧ ⎪ ⎨ ⎪ ⎩ e(1,1) if a =e(i,j∗),i∈D(j∗) e(2,2) if a =e(i∗,j),j∈S(i∗) e(2,1) if a =e(i∗,j∗) e(1,2) otherwise . We can easily show that pN Q(x)=pN Q(q)+pN A(a) where x=q+a. Let aN∈AN, we also define (pN A)−1(aN)= {a∈A: pN A(a)=aN}. Let Abe the arrival process associated to G, we construct an arrival process ANfor GNin the following way: ∀aN∈AN,P(AN=aN)=∑ a∈(pN A)−1(aN) P(A=a) We assume that the quasi-complete graphs we consider in this section satisfy the following property: the holding cost is the same for all the demand nodes that are compatible with all the supply nodes and the holding cost is the same for all the supply nodes that are compatible with all the demand nodes. In other words, there exist c1and c2such that cdi=c1 for all i∈D(j∗) and csj=c2for all j∈S(i∗). In the example of Fig. 3, this means that cd1=cd2as well as cs2=cs3. From this assumption on the holding costs, we can construct the N-shaped matching graph such that cN d1=cdi, for all i∈D(j∗), cN d2=cdi∗,cN s1=csj∗and cN s2=csjfor all j∈S(i∗). Therefore, using Definition 6, it follows that c(x)=cN(pN Q(x)) for all x∈Q.(5) We now define the decision rule of threshold-type that we study in this section. Definition 7 (Threshold-type decision rule).A decision rule uxis said to be of threshold type with priority to i∗and j∗if: 1. it matches all the items of (i,j∗) for all i∈D(j∗) and all the items of (i∗,j) for all j∈S(i∗). 2. it matches the items of (i,j) (i∈D(j∗) and j∈S(i∗)) only if the remaining items (in the sum of difor i∈D(j∗)) are above a specific threshold, denoted by t(with t∈N∪∞). i.e, uxis such that ∑i∈D(j∗)(ux)(i,j∗)=min(∑i∈D(j∗)xdi,xsj∗), ∑j∈S(i∗)(ux)(i∗,j)=min(xdi∗,∑j∈S(i∗)xsj) and ∑i∈D(j∗)∑j∈S(i∗) (ux)(i,j)=kt(x) where kt(x)={0if ∑i∈D(j∗)xdi−xsj∗≤t ∑i∈D(j∗)xdi−xsj∗−t otherwise . We define D∗as the set of decision rules that are of threshold type with priority to i∗and j∗for any t∈N∪∞. We aim to show that the stationary policy based on the above decision rules is optimal for a quasi-complete matching graph with an arbitrary number of supply and demand nodes. For this purpose, we first need to show the following properties. Lemma 4. Let 0≤θ < 1, let π∗=(u(X(n)))n≥0(with u ∈D∗as defined in Definition 7) be a threshold-type policy with priority in i∗and j∗and let (πN)∗=(uN(XN(n)))n≥0(with uN∈Dσas defined in Definition 4) be a threshold-type policy with priority in (1,1) and (2,2). Thus, we have vπ∗ θ(y)=v(πN)∗ θ(yN)for all y =(q,a)∈Q×A, with yN=(pN Q(q),pN A(a)). The result remains true for the average cost problem with gπ∗and g(πN)∗. Proof. The idea of the proof is to first show that for π∗, we have that pN Q(xn)=xN nand then that the expected cost in both matching models coincides. Detailed proof is provided in Appendix F.□ Lemma 5. Let 0≤θ < 1, let πbe a stationary policy on Y, y =(q,a)∈Q×Aand yN=(pN Q(q),pN A(a)). Thus, there exists a policy πNon YNsuch that vπ θ(y)=vπN θ(yN). The result remains true for the average cost problem with gπand gπN. Proof. The idea of the proof is that, for any π, we define πNsuch that we have that pN Q(xn)=xN nand also that the expected cost in both cases coincides. Detailed proof is provided in Appendix G □ We now prove that an optimal matching policy for a quasi-complete graph with an arbitrary number of supply and demand nodes is formed by decision rules which are as defined in Definition 7. Theorem 3. The optimal control for the discounted cost problem and the average cost problem is of threshold type with priority to i∗and j∗. Proof. Let 0 ≤θ < 1, let πbe a stationary policy on Yand π∗=(u(X(n)))n≥0(with u∈D∗as defined in Definition 7) be a threshold-type policy with priority in i∗and j∗. Let y0=(q0,a0)∈Q×Aand yN 0=(pN Q(q0),pN A(a0)). Using Lemma 5, 9 A. Cadas, J. Doncel and A. Bušić Performance Evaluation 154 (2022) 102286 Proof. First, we note that the cost function is nonnegative and therefore Assumption (A1) holds using C=0. Let πML be the policy Match the Longest as defined in [24, Definition 2.6]. This policy is stable for any bipartite matching graph as proved in [24, Theorem 7.1], which means that the derived Markov chain is positive recurrent and gπML <∞. Moreover, the set {y∈Y:c(y)<gπML }is nonempty because gπML >min(i,j)∈Acdi+csjalmost surely and c(0,a)=cdi+csj(for any a=e(i,j)∈A). It is also finite because gπML <∞and cis increasing in y(because cis linear). Therefore, we can use [25, Theorem 8.10.9] and Assumptions (A2) to (A4) hold. □ Appendix B. Proof of Proposition 1 Let v∈I(1,1) ∩I(2,2) ∩I(2,1), 0 ≤θ≤1, q∈Q,a∈A,x=q+aand u∈Ux. The maximum number of items that can be matched in (1,1) is denoted by m(1,1) =min(xd1,xs1) and in (2,2) by m(2,2) =min(xd2,xs2). Let p(1,2) =min(u(1,2),xs1−u(1,1),xd2−u(2,2)) be the number of items that are matched in (1,2) under the control u that can be transformed from matching items in (1,1) and (2,2) at the same time. We define a policy up(1,2) that removes the p(1,2) items in (1,2) and matches p(1,2) items in (1,1) and (2,2), that is, up(1,2) =u+p(1,2)(e(1,1) +e(2,2) −e(1,2)). Using (3), we verify that this policy is admissible, i.e. up(1,2) ∈Ux:up(1,2) ∈N4is true because u∈Ux.(a) is true because up(1,2) (2,2) =u(2,2) +p(1,2) ≤xd2.(b) is true because up(1,2) (1,1) =u(1,1) +p(1,2) ≤xs1. Then, since v∈I(2,1), it follows that Lθ up(1,2) v(q,a)≤Lθ uv(q,a). We now define u∗as the decision rule that matches all the items (1,1) and (2,2) of x−up(1,2) , that is, of the remaining items when we apply up(1,2) . Hence, we have that u∗=up(1,2) +e(1,1)(m(1,1) −up(1,2) (1,1) )+e(2,2)(m(2,2) −up(1,2) (2,2) ). Using (3), we also verify that u∗∈Ux:u∗∈N4is true because up(1,2) ∈Ux,m(1,1) ≥0 and m(2,2) ≥0. We immediately get that u∗ (2,2) =m(2,2) ≤xd2and u∗ (1,1) =m(1,1) ≤xs1. For xd1and xs2, we distinguish the following cases: 1. If p(1,2) =u(1,2). Then we have u∗ (1,2) =up(1,2) (1,2) =0. Thus, u∗ (1,1) +u∗ (1,2) =m(1,1) ≤xd1 u∗ (2,2) +u∗ (1,2) =m(2,2) ≤xs2 2. If p(1,2) =xs1−u(1,1). Then, u∗ (1,1) +u∗ (1,2) =m(1,1) +u(1,2) −xs1+u(1,1) ≤u(1,2) +u(1,1) ≤xd1 u∗ (2,2) +u∗ (1,2) =m(2,2) +u(1,2) −xs1+u(1,1) ≤xd2+u(1,2) −xs1+u(1,1) =xs2+u(1,2) −xd1+u(1,1) ≤xs2 3. If p(1,2) =xd2−u(2,2). Then, u∗ (1,1) +u∗ (1,2) =m(1,1) +u(1,2) −xd2+u(2,2) ≤xs1+u(1,2) −xd2+u(2,2) =xd1+u(1,2) −xs2+u(2,2) ≤xd1 u∗ (2,2) +u∗ (1,2) =m(2,2) +u(1,2) −xd2+u(2,2) ≤u(1,2) +u(2,2) ≤xs2 In all the cases, (a) and (b) are true. Hence, since v∈I(1,1) ∩I(2,2), it results that Lθ u∗v(q,a)≤Lθ up(1,2) v(q,a) and, as a consequence, Lθ u∗v(q,a)≤Lθ uv(q,a) for any u∈Ux. Appendix C. Proof of Proposition 2 Let q∈Q,a∈A,x=q+aand u∈Ux. We define m(1,1) =min(xs1,xd1) and m(2,2) =min(xs2,xd2). Since v∈I(1,1) ∩I(2,2) ∩I(2,1), it follows from Proposition 1 that there exists u′∈Uxthat matches all the items of the pendant edges and Lθ u′v(q,a)≤Lθ uv(q,a). Therefore, u′is of the following form: u′=m(1,1)e(1,1) +m(2,2)e(2,2) +ke(1,2) with k∈Kx. We now prove that there exists t∈N∪∞ such that Lθ u∗v(q,a)≤Lθ u′v(q,a),∀k∈Kx(10) where u∗is a decision rule of threshold type in the diagonal edge with priority to the pendant edges (see Definition 4). If xs1≥xd1, then Kx=0 and, as a result, we have that u∗=u′. We now consider that xs1<xd1, in which case Kx= {0}. For this case, the state of the system after applying a threshold type decision rule (u∗or u′) is of the form (l,0,0,l). Therefore, to compare Lθ u∗v(q,a) with Lθ u′v(q,a), we only need to compare E[v(j∗e(1,2),A)]with E[v(j′e(1,2),A)], where j∗,j′∈Kx. Since vis convex in (1,2), we distinguish the following cases: •First, we consider that ∀j∈N,E[v((j+1)e(1,2),A)] − E[v(je(1,2),A)] ≤ 0. For this case, we define u∗as follows: u∗=m(1,1)e(1,1) +m(2,2)e(2,2) (note that this is the same as choosing t= ∞ and therefore kt(x)=0). Since E[v((j+1)e(1,2),A)]−E[v(je(1,2),A)] ≤ 0, it follows that Lθ u∗v(q,a)≤Lθ u∗+e(1,2) v(q,a)≤ ··· ≤ Lθ u∗+ke(1,2) v(q,a) for all k∈Kx. Therefore, it follows (10). 16 A. Cadas, J. Doncel and A. Bušić Performance Evaluation 154 (2022) 102286 •We now consider that E[v(e(1,2),A)] − E[v(0,A)] ≥ 0. For this case, we define u∗as follows: u∗=m(1,1)e(1,1) + m(2,2)e(2,2) +(xd1−xs1)e(1,2) (note that this is the same as choosing t=0 and kt(x)=xd1−xs1). Using that E[v(e(1,2),A)]−E[v(0,A)] ≥ 0 and also that vis convex in (1,2), it results that Lθ u∗v(q,a)≤Lθ u∗−e(1,2) v(q,a)≤ ··· ≤ Lθ u∗−ke(1,2) v(q,a) for all k∈Kxand since u∗−(xd1−xs1−k)e(1,2) =u′(with xd1−xs1−k∈Kx,∀k∈Kx), it follows (10). •Finally, we consider that ∃j∈N∗,E[v((j+1)e(1,2),A)]−E[v(je(1,2),A)] ≥ 0. Let j=min{j∈N∗:E[v((j+1)e(1,2),A)]− E[v(je(1,2),A)] ≥ 0}. By definition of jand by convexity of vin (1,2), we have E[v((j−l)e(1,2),A)]−E[v((j−l−1)e(1,2),A)] ≤ 0∀l∈ [[0;j−1]] (11) and E[v((j+1+l)e(1,2),A)]−E[v((j+l)e(1,2),A)] ≥ 0∀l∈N(12) We define u∗as the decision rule of Definition 4 with t=j. We first consider that xd1−xs1≤j, then we have kt(x)=0 and Lθ u∗v(q,a)≤Lθ u′v(q,a) for all k∈Kxby (11) (note that 0 ≤k≤xd1−xs1≤j), which shows (10). We now consider that xd1−xs1>j, then kt(x)=xd1−xs1−jand Lθ u∗v(q,a)=c(x)+θE[v(je(1,2),A)]. Therefore, for all k∈Kx,Lθ u∗v(q,a)≤Lθ u′v(q,a) by (11) if k≥jor by (12) if k≤j, which proves (10). Appendix D. Proofs of Section 4.3 D.1. Proof of Lemma 1 We first show that if v∈I(1,1), then Lθv∈I(1,1). Let q∈Qand a∈A,x=q+a. We define q=q+e(1,1),x=q+a. Since vis increasing with (1,1), we have that v(q,a)≥v(q,a). We aim to show that Lθv(q,a)≥Lθv(q,a). Let ux∈arg minu∈UxLθ uv(q,a). Since (x)s1≥1 and (x)d1≥1, from Proposition 1, it follows that (ux)(1,1) =min(xd1,xs1)≥ 1. Therefore, we define ux=ux−e(1,1). Thus, it is easy to see that ux∈Uxbecause ux∈Ux. Moreover, we observe that x−ux=x−uxand, since cis a linear function, c(x)>c(x). Hence, Lθ uxv(q,a)=c(x)+θE[v(x−ux,A)] =c(x)−c(x)+c(x)+θE[v(x−ux,A)] =c(x)−c(x)+Lθv(q,a) <Lθv(q,a). And, since ux∈Ux, then by definition Lθv(q,a)≤Lθ uxv(q,a) and, as a result, the desired result follows. To prove that if v∈I(2,2), then Lθv∈I(2,2), one can use the same arguments as above with q=q+e(2,2). We omit it for clarity of the presentation. The proof of the preservation of the increasing property in I(2,1) is also similar but requires to handle the case when no items can be matched in (1,2). Let q∈Qand a∈A,x=q+a. Let q=q+e(1,1) +e(2,2) −e(1,2),x=q+a. Since v∈I(2,1), we know that v(q,a)≤v(q,a). Besides, c(x)<c(x) holds because cis a linear function of x. We aim to show that Lθv(q,a)≤Lθv(q,a). Let ux∈arg minu∈UxLθ vv(q,a). From Proposition 1, we know that (ux)(2,2) =min(xd2,xs2) and (ux)(1,1) =min(xd1,xs1). We first consider that xd1≥1 and xs2≥1. We define ux=ux−e(1,1) −e(2,2) +e(1,2). Thus, we have that x−ux=x−ux and ux∈Uxbecause ux∈Uxas well as xs1=xs1−1≥(ux)(1,1) −1=min(xd1,xs1)−1=min(xd1,xs1+1) −1≥0, xd2=xd2−1≥(ux)(2,2) −1=min(xd2,xs2)−1=min(xd2+1,xs2)−1≥0. Thus, Lθ uxv(q,a)=c(x)+θE[v(x−ux,A)] =c(x)−c(x)+c(x)+θE[v(x−ux,A)] =c(x)−c(x)+Lθv(q,a) <Lθv(q,a). And since ux∈Ux, then Lθv(q,a)≤Lθ uxv(q,a) and from the above inequality, the desired result follows. 17 A. Cadas, J. Doncel and A. Bušić Performance Evaluation 154 (2022) 102286 We now consider that xd1=0 or xs2=0. In that case, we cannot match more items in state xthan in state x, which implies that ux∈Ux. As a result, Lθ uxv(q,a)=c(x)+θE[v(x−ux,A)] ≤c(x)+θE[v(x−ux,A)]since v∈I(2,1) =c(x)−c(x)+c(x)+θE[v(x−ux,A)] =c(x)−c(x)+Lθv(q,a) <Lθv(q,a). And since ux∈Ux, then Lθv(q,a)≤Lθ uxv(q,a) and from the above inequality, the desired result follows. D.2. Proof of Lemma 2 Let q∈Q,qd1≥qs1,a∈A,x=q+a,q=q+e(1,2),x=q+a,q=q+e(1,2) and x=q+a. Since vis convex in (1,2), we have v(q,a)−v(q,a)≤v(q,a)−v(q,a). We aim to show that Lθv(q,a)−Lθv(q,a)≤Lθv(q,a)−Lθv(q,a). For y∈{x,x,x}, let uy∈arg minuLθ uv(y). From Proposition 2, we can choose uysuch that uy=min(yd1,ys1)e(1,1) +min(yd2,ys2)e(2,2) +kt(y) e(1,2). Let us also define m=x−ux. Suppose that qd1≥qs1+1 or a∈A\{e(2,1)}, we can distinguish 3 cases: (a) kt(x)>0, (b) kt(x)=0 and kt(x)>0 and (c) kt(x)=0 and kt(x)=0: (a) If kt(x)>0. Then, Lθv(q,a)−Lθv(q,a)=c(x)−c(x)+θE[v(m,A)−v(m,A)] =c(x)−c(x)+θE[v(m,A)−v(m,A)] =Lθv(q,a)−Lθv(q,a). (b) If kt(x)=0 and kt(x)>0. Then, Lθv(q,a)−Lθv(q,a)=c(x)−c(x)+θE[v(m+e(1,2),A)−v(m,A)] =c(x)−c(x)+Lθv(q,a)−Lθ ux+e(1,2) v(q,a) =c(x)−c(x)+Lθv(q,a)−Lθ ux+e(1,2) v(q,a) ≤c(x)−c(x) =c(x)−c(x)+θE[v(m+e(1,2),A)−v(m+e(1,2),A)] =Lθv(q,a)−Lθv(q,a) where the inequality is given because kt(x)=kt(x)=0 and 1 ∈Kx. (c) If kt(x)=0 and kt(x)=0. Then, Lθv(q,a)−Lθv(q,a)=c(x)−c(x)+θE[v(m+e(1,2),A)−v(m,A)] =c(x)−c(x)+θE[v(m+e(1,2),A)−v(m,A)] ≤c(x)−c(x)+θE[v(m+2e(1,2),A)−v(m+e(1,2),A)] =Lθv(q,a)−Lθv(q,a) where the inequality is true since v∈C(1,2). Suppose now that qd1=qs1and a=e(2,1), we can distinguish 2 cases: kt(x)>0 and kt(x)=0: •If kt(x)>0. Then, Lθv(q,a)−Lθv(q,a)=c(x)−c(x)+θE[v(m−e(2,1),A)−v(m,A)] ≤c(x)−c(x)+θE[v(m,A)−v(m,A)] =c(x)−c(x)+θE[v(m,A)−v(m,A)] =c(x)−c(x)+θE[v(m−e(2,1),A)−v(m−e(2,1),A)] =Lθv(q,a)−Lθv(q,a) where the inequality is given because v∈I(2,1). 18 A. Cadas, J. Doncel and A. Bušić Performance Evaluation 154 (2022) 102286 •If kt(x)=0. Then, Lθv(q,a)−Lθv(q,a)=c(x)−c(x)+θE[v(m−e(2,1),A)−v(m,A)] =c(x)−c(x)+θE[v(m−e(2,1),A)−v(m,A)] ≤c(x)−c(x)+θE[v(m−e(2,1) +e(1,2),A)−v(m−e(2,1),A)] =Lθv(q,a)−Lθv(q,a) where the inequality is given because v∈B. D.3. Proof of Lemma 3 D.3.1. Preservation of B Proof. Let a∈A. Since v∈B, we have v(0,a)−v(e(2,1),a)≤v(e(1,2),a)−v(0,a). We aim to show that Lθv(0,a)− Lθv(e(2,1),a)≤Lθv(e(1,2),a)−Lθv(0,a). For any x∈Q, we know from Proposition 2 that there exists ux∈arg minuLθ uv(x) such that ux=min(xd1,xs1)e(1,1) +min(xd2,xs2)e(2,2) +kt(x)e(1,2). We show the desired result for each possible value of a: •If a=e(1,1) or a=e(2,2). Suppose that kt(e(1,2))=0. Then, Lθv(0,a)−Lθv(e(2,1),a)=c(a)−c(a+e(2,1))+θE[v(0,A)−v(e(2,1),A)] <c(a+e(1,2))−c(a)+θE[v(0,A)−v(e(2,1),A)] ≤c(a+e(1,2))−c(a)+θE[v(e(1,2),A)−v(0,A)] =Lθv(e(1,2),a)−Lθv(0,a) where the second inequality is given since v∈B. Suppose now that kt(e(1,2))>0. Then, Lθv(0,a)−Lθv(e(2,1),a)=c(a)−c(a+e(2,1))+θE[v(0,A)−v(e(2,1),A)] ≤c(a)−c(a+e(2,1)) <c(a+e(1,2))−c(a) =c(a+e(1,2))−c(a)+θE[v(0,A)−v(0,A)] =Lθv(e(1,2),a)−Lθv(0,a) where the first inequality is given because v∈I(2,1). •If a=e(1,2). Suppose that kt(2e(1,2))=0. Then, Lθv(0,a)−Lθv(e(2,1),a)=c(a)−c(a+e(2,1))+θE[v(e(1,2),A)−v(0,A)] <c(a+e(1,2))−c(a)+θE[v(e(1,2),A)−v(0,A)] ≤c(a+e(1,2))−c(a)+θE[v(2e(1,2),A)−v(e(1,2),A)] =Lθv(e(1,2),a)−Lθv(0,a) where the second inequality follows since v∈C(1,2). Suppose now that kt(2e(1,2))>0 and kt(e(1,2))=0. Then, Lθv(0,a)−Lθv(e(2,1),a)=c(a)−c(a+e(2,1))+θE[v(e(1,2),A)−v(0,A)] =c(a)−c(a+e(2,1))+Lθv(0,a)−Lθ ua+e(1,2) v(0,a) ≤c(a)−c(a+e(2,1)) <c(a+e(1,2))−c(a) =c(a+e(1,2))−c(a)+θE[v(e(1,2),A)−v(e(1,2),A)] =Lθv(e(1,2),a)−Lθv(0,a), where the first inequality follows since 1 ∈UxFinally, suppose that kt(2e(1,2))>0 and kt(e(1,2))>0. Then, Lθv(0,a)−Lθv(e(2,1),a)=c(a)−c(a+e(2,1))+θE[v(0,A)−v(0,A)] <c(a+e(1,2))−c(a)+θE[v(0,A)−v(0,A)] =Lθv(e(1,2),a)−Lθv(0,a). 19 A. Cadas, J. Doncel and A. Bušić Performance Evaluation 154 (2022) 102286 •If a=e(2,1). Then, Lθv(0,a)−Lθv(e(2,1),a)=c(a)−c(a+e(2,1))+θE[v(e(2,1),A)−v(2e(2,1),A)] ≤c(a)−c(a+e(2,1))+θE[v(0,A)−v(e(2,1),A)] <c(a+e(1,2))−c(a)+θE[v(0,A)−v(e(2,1),A)] =Lθv(e(1,2),a)−Lθv(0,a) where the first inequality follows since v∈C(2,1).□ D.3.2. Preservation of C(2,1) Proof. Let a∈Aand q∈Qsuch that qs1≥qd1,x=q+a. We define q=q+e(2,1),x=q+a,q=q+e(2,1) and x=q+a. Since vis convex in (2,1), we have v(q,a)−v(q,a)≤v(q,a)−v(q,a). We aim to show that Lθv(q,a)−Lθv(q,a)≤Lθv(q,a)−Lθv(q,a). For y∈{x,x,x}, let uy∈arg minuLθ uv(y). From Proposition 2, we can choose uysuch that uy=min(yd1,ys1)e(1,1) +min(yd2,ys2)e(2,2) +kt(y)e(1,2). Let us also define m=x−ux. We can distinguish 2 cases: (a) qs1≥qd1+1 or a∈A\{e(1,2)}and (b) qs1=qd1and a=e(1,2): (a) If qs1≥qd1+1 or a∈A\{e(1,2)}. Then, Lθv(q,a)−Lθv(q,a)=c(x)−c(x)+θE[v(m+e(2,1),A)−v(m,A)] ≤c(x)−c(x)+θE[v(m+2e(2,1),A)−v(m+e(2,1),A)] <c(x)−c(x)+θE[v(m+2e(2,1),A)−v(m+e(2,1),A)] =Lθv(q,a)−Lθv(q,a) where the first inequality is given because v∈C(2,1). (b) If qs1=qd1and a=e(1,2). Suppose that kt(x)=0. Then, Lθv(q,a)−Lθv(q,a)=c(x)−c(x)+θE[v(m−e(1,2),A)−v(m,A)] ≤c(x)−c(x)+θE[v(m−e(1,2) +e(2,1),A)−v(m−e(1,2),A)] =Lθv(q,a)−Lθv(q,a) because cis a linear function and v∈B. Suppose now that kt(x)>0. Then, Lθv(q,a)−Lθv(q,a)=c(x)−c(x)+θE[v(m+e(2,1),A)−v(m,A)] ≤c(x)−c(x)+θE[v(m+2e(2,1),A)−v(m+e(2,1),A)] <c(x)−c(x)+θE[v(m+2e(2,1),A)−v(m+e(2,1),A)] =Lθv(q,a)−Lθv(q,a) where the first equality follows since v∈C(2,1).□ Appendix E. Proof of Proposition 3 Proof. Let u∞ t∈ΠT(1,2) . Let us look at the Markov chain derived from this policy. The set of possible states (except for Y0) is SA= {(si,a):i∈N,a∈A}with si=(t−i,0,0,t−i) if i≤tand si=(0,i−t,i−t,0) otherwise. The si are all possible states after matching the items using u∞ t. In order to see more clearly the behavior of the Markov chain, we group together some states. Let us define S= {Si:i∈N}with S0= {(s0,e(1,2)),(s0,e(1,1)),(s0,e(2,2)),(s1,e(1,2))}and Si= {(si−1,e(2,1)),(si,e(1,1)),(si,e(2,2)),(si+1,e(1,2))}for all i∈N∗.Fig. 6 shows that this Markov chain defined on Sis clearly irreducible. The balance equations are the following: β(1 −α)πSi=α(1 −β)πSi+1i=0,1, . . . Solving these equations under the constraint that ∑∞ i=0πSi=1 give: πSi=ρi(1 −ρ)i=0,1, . . . (13) with ρ=β(1−α) α(1−β)∈(0,1). So (13) is the stationary distribution of the Markov chain on S, which thus is positive recurrent. Using these results, we can easily conclude that the Markov chain on SAis also irreducible. Then, since the arrival process 20 A. Cadas, J. Doncel and A. Bušić Performance Evaluation 154 (2022) 102286 Fig. 6. The graph associated to the Markov chain derived from u∞ tand defined on the state space S.pe(1,1) =αβ,pe(2,2) =(1 −α)(1 −β), pe(1,2) =α(1 −β) and pe(2,1) =β(1 −α). does not depend on the state and because the following condition must be satisfied πSi=π(si−1,e(2,1))+π(si,e(1,1))+π(si,e(2,2))+ π(si+1,e(1,2)), we can think of the following as the stationary distribution: π(si,a)=ρi(1 −ρ)pa(14) with paas defined in Fig. 6 (i.e. pe(1,1) =αβ,pe(2,2) =(1 −α)(1 −β), pe(1,2) =α(1 −β) and pe(2,1) =β(1 −α)), for all i∈N and a∈A. Let us verify that (14) is indeed a stationary distribution: ∑ k∈N∑ a∈A π(sk,a)p((sk,a),(si,a′)) =pa′(π(si−1,e(2,1))+π(si,e(1,1))+π(si,e(2,2))+π(si+1,e(1,2))) =pa′(ρi−1(1 −ρ)pe(2,1) +ρi(1 −ρ)pe(1,1) +ρi(1 −ρ)pe(2,2) +ρi+1(1 −ρ)pe(1,2) ) =pa′ρi(1 −ρ)(β(1 −α) ρ+αβ +(1 −α)(1 −β)+ρα(1 −β)) =pa′ρi(1 −ρ) =π(si,a′) Hence, ∑i∈N∑a∈Aπ(si,a)=∑i∈Nρi(1 −ρ)∑a∈Apa=∑i∈Nρi(1 −ρ)=1 and, therefore, (14) is the stationary distribution of the Markov chain derived from the policy u∞ tand this Markov chain is positive recurrent. Using the monotone convergence theorem and the strong law of large number for Markov chains, we can compute the average cost gu∞ t: gu∞ t(y)=lim N→∞ 1 N N−1 ∑ n=0 Eu∞ t y[c(Y(n))] = Eπ[c(Y)] where Eπmeans the expectation over the stationary distribution πdefined as (14). Finally, we compute this value: Eπ[c(Y)] = t ∑ i=1∑ a∈A c(st−i+a)π(st−i,a)+∑ i∈N∑ a∈A c(st+i+a)π(st+i,a) = t ∑ i=1 ((cd1+cs2)i+cd1+cs1)ρt−i(1 −ρ)αβ +((cd1+cs2)i+cd2+cs1)ρt−i(1 −ρ)(1 −α)β +((cd1+cs2)i+cd1+cs2)ρt−i(1 −ρ)α(1 −β)+((cd1+cs2)i+cd2+cs2)ρt−i(1 −ρ)(1 −α)(1 −β) +∑ i∈N ((cd2+cs1)i+cd1+cs1)ρt+i(1 −ρ)αβ +((cd2+cs1)i+cd2+cs1)ρt+i(1 −ρ)(1 −α)β +((cd2+cs1)i+cd1+cs2)ρt+i(1 −ρ)α(1 −β)+((cd2+cs1)i+cd2+cs2)ρt+i(1 −ρ)(1 −α)(1 −β) = t ∑ i=1 (cd1+cs2)iρt−i(1 −ρ)+(cd1+cs1)ρt−i(1 −ρ)αβ +(cd2+cs1)ρt−i(1 −ρ)(1 −α)β +(cd1+cs2)ρt−i(1 −ρ)α(1 −β)+(cd2+cs2)ρt−i(1 −ρ)(1 −α)(1 −β) +∑ i∈N (cd2+cs1)iρt+i(1 −ρ)+(cd2+cs1)ρt+i(1 −ρ)αβ +(cd2+cs1)ρt+i(1 −ρ)(1 −α)β +(cd2+cs1)ρt+i(1 −ρ)α(1 −β)+(cd2+cs2)ρt+i(1 −ρ)(1 −α) (15) Using basic algebra, one can show that, for any c, the following properties hold: t ∑ i=1 c·i·ρt−i=c(t−ρ1−ρt 1−ρ)and ∑ i∈N c·i·ρt−i=cρt+1 1−ρ. 21 A. Cadas, J. Doncel and A. Bušić Performance Evaluation 154 (2022) 102286 Moreover, for any cand q, we have that q·c·(1 −ρ) t ∑ i=1 ρt−i=q·c·(1 −ρt) and q·c·(1 −ρ)∑ i∈N ρt+i=q·c·ρt. Using these properties in (15), we obtain that Eπ[c(Y)] = (cd1+cs2)(t−ρ1−ρt 1−ρ)+(1 −ρt)((cd1+cs1)αβ +(cd1+cs2)α(1 −β) +(cd2+cs1)α(1 −β)+(cd2+cs2)(1 −α)(1 −β)) +(cd2+cs1)ρt+1 1−ρ+ρt((cd1+cs1)αβ +(cd1+cs2)α(1 −β)+(cd2+cs1)α(1 −β)+(cd2+cs2)(1 −α)(1 −β)) =(cd1+cs2)t+(cd1+cd2+cs1+cs2)ρt+1 1−ρ−(cd1+cd2)ρ 1−ρ+((cd1+cs1)αβ +(cd1+cs2)α(1 −β)+(cd2+cs1)α(1 −β)+(cd2+cs2)(1 −α)(1 −β)).(16) We aim to obtain the value of tthat minimizes (16). To this end, we compute the second derivative of (16) with respect to tand it results in (cd1+cd2+cs1+cs2)ρt+1 1−ρ(log ρ)2, which is positive for ρ∈(0,1), i.e., (16) is convex. As a consequence, the minimum of (16) is achieved when its derivative with respect to tis equal to zero: cd1+cs2+(cd1+cd2+cs1+cs2)ρt+1 1−ρ(log ρ)=0⇐⇒ 1+(1 +R)ρt+1 1−ρ(log ρ)=0, where R=cs1+cd2 cd1+cs2 . The root of the previous equation is t0=1 log ρlog (ρ−1 (R+1) log ρ)−1. Since t0is not necessarily integer, the optimal threshold t∗is obtained by computing the value of (16) for the ceil of t0and the floor of t0and choosing the minimum of these values. □ We now show that t∗is always positive. Lemma 10. t∗is always positive. Proof. From Taylor’s Theorem, it follows that for all ρ∈(0,1) 1−ρ (1 +R)log(ρ)∈(0,1 R+1). Since R>0, we have that for all ρ∈(0,1) log (1−ρ (1 +R)log(ρ))<0. Hence, log (1−ρ (1+R)) log(ρ)>0. As a result, t∗is positive since t0is positive. Appendix F. Proof of Lemma 4 Let 0 ≤θ < 1, let π∗=(u(X(n)))n≥0(with u∈D∗as defined in Definition 7) be a threshold-type policy with priority in i∗and j∗and let (πN)∗=(uN(XN(n)))n≥0(with uN∈Dσas defined in Definition 4) be a threshold-type policy with priority in (1,1) and (2,2). Let y0=(q0,a0)∈Q×A, with yN 0=(pN Q(q0),pN A(a0)). First, let us note that (πN)∗is the ‘‘projection’’ of π∗on GNin the following sense. Let x∈Q,u(x)∈D∗the matching of state x(u(x)∈Ux) under the policy π∗and uN(pN Q(x)) ∈Dσthe matching of state pN Q(x) (uN(pN Q(x)) ∈UN pN Q(x)) under the policy (πN)∗. We can easily see that uN (1,1)(pN Q(x)) =∑i∈D(j∗)u(i,j∗)(x), uN (2,2)(pN Q(x)) =∑j∈S(i∗)u(i∗,j)(x) and uN (1,2)(pN Q(x)) =∑i∈D(j∗)∑j∈S(i∗)u(i,j)(x). 22 A. Cadas, J. Doncel and A. Bušić Performance Evaluation 154 (2022) 102286 Then, we are going to prove by induction that for any aN 1∈AN,...,aN n∈ANand any a1∈(pN A)−1(aN 1),...,an∈ (pN A)−1(aN n), we have pN Q(xn)=xN n. We already specifically chose xN 0to verify this property: pN Q(x0)=pN Q(q0)+pN A(a0)=qN 0+aN 0=xN 0. Now, assume that pN Q(xn−1)=xN n−1. Then, pN Q(qn)=⎛ ⎝∑ i∈D(j∗) (qn)di,(qn)di∗,(qn)sj∗,∑ j∈S(i∗) (qn)sj⎞ ⎠ =⎛ ⎝∑ i∈D(j∗) (xn−1−u(xn−1))di,(xn−1−u(xn−1))di∗, (xn−1−u(xn−1))sj∗,∑ j∈S(i∗) (xn−1−u(xn−1))sj⎞ ⎠ =⎛ ⎝∑ i∈D(j∗) (xn−1)di−∑ j∈S(i) u(xn−1)(i,j), (xn−1)di∗−∑ j∈S(i∗) u(xn−1)(i∗,j),(xn−1)sj∗−∑ i∈D(j∗) u(xn−1)(i,j∗), ∑ j∈S(i∗) (xn−1)sj−∑ i∈D(j) u(xn−1)(i,j)⎞ ⎠ =pN Q(xn−1)−∑ i∈D(j∗) u(xn−1)(i,j∗)e(1,1) −∑ j∈S(i∗) u(xn−1)(i∗,j)e(2,2) −∑ i∈D(j∗)∑ j∈S(i∗) u(xn−1)(i,j)e(1,2) =pN Q(xn−1)−uN(pN Q(xn−1))(1,1)e(1,1) −uN(pN Q(xn−1))(2,2)e(2,2) −uN(pN Q(xn−1))(1,2)e(1,2) =pN Q(xn−1)−uN(pN Q(xn−1)) =xN n−1−uN(xN n−1) =qN n and pN A(an)=aN n(because pN A((pN A)−1(aN)) =aNfor all aN∈AN). Thus, pN Q(xn)=pN Q(qn)+pN A(an)=qN n+aN n=xN n. Finally, using this property and (5), we have Eπ∗ y0[c(Y(n))] = ∑ a1∈A,...,an∈A c(xn) n ∏ k=1 P(A=ak) =∑ aN 1∈AN,...,aN n∈AN∑ a1∈(pN A)−1(aN 1)··· ∑ an∈(pN A)−1(aN n) c(xn) n ∏ k=1 P(A=ak) =∑ aN 1∈AN,...,aN n∈AN∑ a1∈(pN A)−1(aN 1)··· ∑ an∈(pN A)−1(aN n) cN(pN Q(xn)) n ∏ k=1 P(A=ak) =∑ aN 1∈AN,...,aN n∈AN∑ a1∈(pN A)−1(aN 1)··· ∑ an∈(pN A)−1(aN n) cN(xN n) n ∏ k=1 P(A=ak) =∑ aN 1∈AN,...,aN n∈AN cN(xN n) n ∏ k=1∑ ak∈(pN A)−1(aN k) P(A=ak) 23 A. Cadas, J. Doncel and A. Bušić Performance Evaluation 154 (2022) 102286 =∑ aN 1∈AN,...,aN n∈AN cN(xN n) n ∏ k=1 P(AN=aN k) =E(πN)∗ yN 0[cN(YN(n))]. This equality is true for any n∈N. Therefore, vπ∗ θ(y0)=v(πN)∗ θ(yN 0) and gπ∗(y0)=g(πN)∗(yN 0). This was done for any y0=(q0,a0)∈Q×Awith yN 0=(pN Q(q0),pN A(a0)), giving the final result. Appendix G. Proof of Lemma 5 Proof. Let 0 ≤θ < 1, let πbe a stationary policy on Y,y0=(q0,a0)∈Q×Aand yN 0=(pN Q(q0),pN A(a0)). We start by constructing a history dependent policy πN=(uN n)n≥0on YNthat will make YN‘‘follow’’ (in some sense) the projection of Yon GN. First, let us introduce new independent random variables ˆ A(n) that we sample just after the arrivals on GN. ˆ A(n) is defined on Awith the following distribution: ∀n∈N∗,∀a∈A,∀aN∈AN, P(ˆ A(n)=a|AN(n)=aN)={P(A(n)=a) P(AN(n)=aN)if a ∈(pN A)−1(aN) 0Otherwise . Then, we define uN nthe decision rule of πNat time nbased on the history of the trajectory, i.e. (AN(1),ˆ A(1),...,AN(n),ˆ A(n)) =(aN 1,ˆ aN 1,...,aN n,ˆ aN n), the initial state y0=(q0,a0) and the stationary policy π. Let ˆ xn∈Qbe the state we end up by starting in x0=q0+a0 and following the dynamics (2) with the sequence of arrivals ˆ aN 1,...,ˆ aN nand under the policy π. Let u∈Uˆ xnbe the decision rule applied for the state ˆ xnunder the policy π. We construct uN n∈UpN Q(ˆ xn)such that (uN n)(1,1) =∑i∈D(j∗)u(i,j∗), (uN n)(2,2) =∑j∈S(i∗)u(i∗,j)and (uN n)(1,2) =∑i∈D(j∗)∑j∈S(i∗)u(i,j). Now, let us show by induction that, under πN, we have pN Q(xn)=xN nfor any aN 1∈AN,...,aN n∈ANand any ˆ a1∈(pN A)−1(aN 1),...,ˆ an∈(pN A)−1(aN n) such that ˆ a1=a1,...,ˆ an=an. We already specifically chose yN 0to verify this property: pN Q(x0)=pN Q(q0)+pN A(a0)=qN 0+aN 0=xN 0. Now, assume that pN Q(xn−1)=xN n−1. First, let us note that xn−1=ˆ xn−1because ˆ a1=a1,...,ˆ an−1=an−1and they both follow the same dynamics under the same policy π. Then, pN Q(qn)=⎛ ⎝∑ i∈D(j∗) (qn)di,(qn)di∗,(qn)sj∗,∑ j∈S(i∗) (qn)sj⎞ ⎠ =⎛ ⎝∑ i∈D(j∗) (xn−1−u(xn−1))di,(xn−1−u(xn−1))di∗ ,(xn−1−u(xn−1))sj∗,∑ j∈S(i∗) (xn−1−u(xn−1))sj⎞ ⎠ =⎛ ⎝∑ i∈D(j∗) (xn−1)di−∑ j∈S(i) u(xn−1)(i,j), (xn−1)di∗−∑ j∈S(i∗) u(xn−1)(i∗,j),(xn−1)sj∗−∑ i∈D(j∗) u(xn−1)(i,j∗), ∑ j∈S(i∗) (xn−1)sj−∑ i∈D(j) u(xn−1)(i,j)⎞ ⎠ =pN Q(xn−1)−∑ i∈D(j∗) u(xn−1)(i,j∗)e(1,1) −∑ j∈S(i∗) u(xn−1)(i∗,j)e(2,2) −∑ i∈D(j∗)∑ j∈S(i∗) u(xn−1)(i,j)e(1,2) 24 A. Cadas, J. Doncel and A. Bušić Performance Evaluation 154 (2022) 102286 =pN Q(xn−1)−∑ i∈D(j∗) u(ˆ xn−1)(i,j∗)e(1,1) −∑ j∈S(i∗) u(ˆ xn−1)(i∗,j)e(2,2) −∑ i∈D(j∗)∑ j∈S(i∗) u(ˆ xn−1)(i,j)e(1,2) =pN Q(xn−1)−(uN n)(1,1)e(1,1) −(uN n)(2,2)e(2,2) −(uN n)(1,2)e(1,2) =xN n−1−uN n =qN n and pN A(an)=aN n(because pN A((pN A)−1(aN)) =aNfor all aN∈AN). Thus, pN Q(xn)=pN Q(qn)+pN A(an)=qN n+aN n=xN n. Then, using this property and (5), we have Eπ y0[c(Y(n))] = ∑ a1∈A,...,an∈A c(xn) n ∏ k=1 P(A(k)=ak) =∑ aN 1∈AN,...,aN n∈AN∑ a1∈(pN A)−1(aN 1)··· ∑ an∈(pN A)−1(aN n) c(xn) n ∏ k=1 P(A(k)=ak) =∑ aN 1∈AN,...,aN n∈AN∑ a1∈(pN A)−1(aN 1)··· ∑ an∈(pN A)−1(aN n) cN(pN Q(xn)) n ∏ k=1 P(A(k)=ak) =∑ aN 1∈AN,...,aN n∈AN∑ ˆ a1∈(pN A)−1(aN 1)··· ∑ ˆ an∈(pN A)−1(aN n) cN(xN n) n ∏ k=1 P(A(k)=ˆ ak) =∑ aN 1∈AN,...,aN n∈AN∑ ˆ a1∈(pN A)−1(aN 1)··· ∑ ˆ an∈(pN A)−1(aN n) cN(xN n) n ∏ k=1 P(ˆ A(k)=ˆ ak|AN(k)=aN k)P(AN(k)=aN k) =∑ aN 1∈AN,...,aN n∈AN∑ ˆ a1∈(pN A)−1(aN 1)··· ∑ ˆ an∈(pN A)−1(aN n) cN(xN n) n ∏ k=1 P(AN(k)=aN k,ˆ A(k)=ˆ ak) =EπN yN 0[cN(YN(n))]. This equality is true for any n∈N. Therefore, vπ θ(y0)=vπN θ(yN 0) and gπ(y0)=gπN(yN 0). □ Appendix H. Proof of Proposition 4 Let q∈Q,a∈A,x=q+aand u∈Ux. We define x(i,j)=min(xdi,xsj) for all (i,j)∈Eto ease the notations. We assume that the matching graph has mpendant edges, i.e., E∗= {(i1,j1),(i2,j2),...,(im,jm)}. For k=1,...,m, we define pk=min(x(ik,jk)−u(ik,jk),∑ (i,j)∈N((ik,jk)) u(i,j)). We now observe that, for all (i,j)∈N((ik,jk)), we define 0 ≤pi,j≤u(i,j)such that pk=∑(i,j)∈N((ik,jk)) pi,j. Hence, we define u′=u+ m ∑ k=1 ⎛ ⎝pke(ik,jk)−∑ (i,j)∈N((ik,jk)) pi,je(i,j)⎞ ⎠. We assume that u′∈Ux. Since v∈Vσ, it follows that Lθ u′v(q,a)≤Lθ uv(q,a).(17) We now define mk=x(ik,jk)−u′ (ik,jk)for all k=1,...,mand u∗=u′+∑m k=1mke(ik,jk).We assume that u∗∈Ux. Using that v∈Vσ, we have that Lθ u∗v(q,a)≤Lθ u′v(q,a),and, taking into account (17), it follows that Lθ u∗v(q,a)≤Lθ uv(q,a), which holds for any u∈Uxand therefore also for u∈arg min Lθv(q,a). As a result, u∗∈arg min Lθv(q,a). Besides, for any pendant edge (ik,jk), we have that u∗ (ik,jk)=u′ (ik,jk)+x(ik,jk)−u′ (ik,jk)=x(ik,jk), and the desired result follows if we show that u′∈Uxand u∗∈Ux. 25