Ergodic Control of Bipartite Matching Queues with Class Change and Matching Failure

1. Introduction

1.1. Motivation and Problem Statement

Although matching supply and demand has been a long-lasting problem (Roth and Sotomayor 1992), the advent and diffusion of online platform applications have spurred notable research in the operations community (Chen et al. 2020). Demand and supply are usually heterogeneous belonging to different classes/types. In many applications such as organ transplant matching systems and ridesharing systems, demand is from impatient customers and those customers may abandon the system if they wait too long, and supply should be allocated to waiting demand quickly. In addition, customers may change classes while waiting in the system. For example, in organ transplant and other healthcare applications, patients’ classes can change because of their health deterioration or improvement, and in service systems, customers can switch between regular and VIP classes. Motivated by these applications, we study a multiclass bipartite matching queue with class change, and focus on instantaneous matching policies that assign each supply unit upon arrival to waiting customers.

In the queueing system we consider, customers belonging to different classes arrive to one side of the system according to Poisson processes, join their class-dependent queues, and wait in queue to be matched with resources. On the other side, resources with different types arrive according to Poisson processes and are allocated to the waiting customers on arrival. The value of a match may depend on the resource type and customer class. While waiting, the customers can join another queue or abandon the system after an exponentially distributed amount of time. Furthermore, we incorporate the matching disruption feature into the system, that is, the customers may refuse the offered resources with some class-dependent probabilities. In this case, the resources will be wasted, and the customers remain in queue, that is, the matching fails. Figure 1 shows a schematic view of the matching system with the existence of customer class change and matching failure.

One motivation for the current setting stems from the organ transplant application, where both the class change and matching failure features have been observed and studied. Fluid models that capture patients’ health change were proposed in Akan et al. (2012) to study the organ allocation control problems over a finite time horizon. The optimal policy is of priority type, where the priority indices dynamically depend on the shadow price process of the optimal control problem. The stochastic version of this problem was investigated in Khademi and Liu (2021), where the asymptotic optimality of the dynamic priority rule is established under a strictly overloaded condition in fluid scaling. In another related work, motivated by patient health deterioration in hospitals, Hu et al. (2021) developed a multiclass many-server queueing system, where customers of class i can move to adjacent classes i − 1 and i + 1. Focusing on the fluid dynamics of the setting with two customer classes, they developed a modified $c\mu /\theta$ rule to optimize a long-run average cost function and investigated the stability of the state process under the proposed policy. They further studied an associated transient control problem (see Section 2 for a more complete literature review of related works). Considering a general multiclass bipartite matching system in a Markovian setting, our current work exploits the class change feature to develop a stability condition under which the system is stable for any arrival rates of customers and resources and any admissible control, and propose asymptotically optimal policies by studying a simple linear program (LP).

We consider a decision maker (DM) who is interested in maximizing the long-run average expected matching values and minimizing the long-run average expected cost. To this end, a bicriteria objective is formulated as a single objective via a linear combination of the two objectives with flexible weights. By this transformation, we study the bicriteria objective as a minimization problem, where the bicriteria objective is referred to as the weighted cost function. Both the class change and matching failure play important roles in designing efficient control policies. To showcase the complexity, we consider a simple system with two customer classes and one resource type. Customer class 1 has high matching value and low cost, whereas customer class 2 has low matching value and high cost. This assumption is motivated from a healthcare application, where class 1 customers correspond to patients in better conditions comparing with class 2 customers in more urgent conditions. The matching value may represent the treatment effect and the cost may include the waiting and abandonment costs. We observe that without the class change or matching failure features, if the objective is to maximize matching values, customer class 1 should be prioritized, whereas if the objective is to minimize the cost, a $c\mu /\theta$ rule developed in Atar et al. (2010) should be applied (noting that the service rates for both classes are the same in this setting and equal to the arrival rate of the resource). Clearly, designing an efficient policy for our bicriteria objective depends on the weighted cost and should properly balance the matching values and costs. Now, if we include the customer class change feature, the outflow from each queue before matching consists of the abandonment and transitions to other queues, and similarly the inflow into each queue includes the transitions from other queues in addition to the external arrivals. When considering minimizing the cost, a modified $c\mu /\theta$ rule was developed in Hu et al. (2021) for which the class change rates appear in the indices of the rule. As shown in our Section 4.2, these modified indices can be characterized in terms of the inverse of a matrix that collects the class change and abandonment rates, see the matrix P defined in (12). Finally, the introduction of matching failure will reduce the priority of the corresponding queue. The larger the matching failure probability, the less chance we allocate the resource to this queue. For a general multiclass bipartite system with multitype resources, the interplay of different features becomes more complex. Our work provides a unified approach to develop efficient policies in the presence of all these features.

1.2. Main Contributions and Results

Our main contributions and results are summarized as follows.

We provide a suitable stability condition (Assumption 1) on the class change and abandonment rates, under which the matching system is stable for any arrival rates of customers and resources and under any admissible control. The stability condition does not require all the abandonment rates to be positive. Instead, it exploits the class change structure and requires the existence of a class transition path from the customer queue without abandonment to a queue with abandonment. This condition can be applied for general parallel queues with class change.

We create a deterministic fluid control problem (FCP) that serves as a lower bound for the original queueing control problem (QCP) under any admissible control as the planning horizon T approaches infinity (Proposition 1). We introduce a class transition rate matrix P (see (12)) that can capture the class change and abandonment feature, show that P satisfies some regularity conditions (see Section 4.2.1 for details) under the established stability condition and characterize important properties of $P^{-1}$ (Lemma 1). These results on P play a crucial role in establishing the lower bound in Proposition 1. Moreover, using $P^{-1}$, the FCP can be reformulated as a simpler LP that can be solved efficiently.

We solve the FCP analytically for two low dimensional matching systems with two classes of customers and two types of resources (known as X models), which may be of independent interest for applications, to illustrate how the class change and matching failure impact the optimal policy. The first system models a transplant queueing system with two patient classes (“Sick” and “Healthy”) and two organ types (“Low-quality” and “High-quality”). By Healthy, we mean a patient whose health condition is not severely deteriorated. We observe that the optimal policy is of assortative or priority type depending on a threshold, which is characterized in terms of the class change and abandonment rates, and the probability that Healthy patients decline Low-quality organs (Lemma 2). For the second matching system, we assume that there is no matching failure. The optimal policy is a simple index policy with indices given as the products of the linear cost (row) vector c and the columns of the matrix $P^{-1}$. The policy is thus referred to as the $c{P}^{-1}$ rule. It generalizes the well-known $c\mu /\theta$ rule developed in Atar et al. (2010) and the modified $c\mu /\theta$ rule developed in Hu et al. (2021) to an X matching model (Lemma 3).

We develop a large-scale asymptotic framework under which we propose a randomized matching policy for the QCP based on the optimal solution of the FCP and show that the proposed policy is asymptotically optimal under both the long-run average cost criterion and the ergodic cost criterion. Under the asymptotic framework, the volumes of both demand and supply are assumed to be high and of order $\mathcal{O}(n)$ (the factor n measures the size of the system, e.g., the total demand rate). We show that for sufficiently long planning horizon T, the FCP lower bound is attained under the proposed policy as the system size $n\to \infty$, and furthermore, for sufficiently large system with size n, the same FCP lower bound is attained under the proposed policy as the planning horizon $T\to \infty$ (Theorem 1). The former result is the asymptotic optimality under the long-run average cost criterion and the latter gives the asymptotic optimality for the ergodic cost. These two results yield the interchange limit theorem for the state process and the matching process as T and n both approach infinity (Theorem 2). An important tool to prove these results is a Lyapunov function (see (44) and (50)) that is constructed using the M-matrix property of the class change rate matrix P. In particular, we show that the fluid limit (derived as $n\to \infty$) of the state process under the proposed policy is a reflected ordinary differential equation (ODE) that is also known as a projected dynamical system. Using the associated variational problem and constructing a Lyapunov function, we show that the reflected ODE admits a unique equilibrium point that is exponentially stable (Proposition 5). Next, with a similar Lyapunov function, we make evident that the matching system under the proposed policy is ergodic (derived as $T\to \infty$) and the fluid limit of the stationary distribution turns out to be the unique equilibrium point of the reflected ODE (Proposition 7). We believe that the constructed Lyapunov function can be potentially used to analyze the stability of parallel queues with class change under different types of policies.

1.3. Organization of the Paper

The rest of the paper is organized as follows. Section 2 reviews some related literature on matching queues, queues with class change, and scheduling control of multiclass queues. In Section 3, we develop the queueing model and the QCP. In Section 4, we formally introduce the FCP and the stability condition under which the FCP is reformulated as a simple LP, and prove that the FCP provides a lower bound for the QCP under any admissible control policy. In Section 4.4, we propose the randomized matching policy based on an optimal solution of the FCP. Section 5 studies two X matching systems and solves the corresponding FCPs to provide insights on how the class change and matching failure impact the optimal policies. Section 6 is devoted to constructing the asymptotic large-scale framework. In Section 6.1, we show that the proposed policy is asymptotically optimal under both the long-run average cost and the ergodic cost criteria. The detailed asymptotic analysis is provided in Sections 6.2 and 6.3. Section 7 conducts some numerical experiments using simulation. Section 8 discusses some of the assumptions that we make in the model and their implications and potential relaxations. All the proofs are presented in the appendix.

2. Literature Review

There are several streams of literature related to our study.

2.1. Allocation Control in Bipartite Matching Systems

The bipartite matching models have been widely used in organ transplant applications. For example, Hasankhani and Khademi (2021) extended the fluid model of Akan et al. (2012) to incorporate fairness constraints and showed that the optimal policy is still of a dynamic priority rule type. Ata et al. (2021) advanced the fluid transplant model to incorporate patient choice in accepting/declining the offered organ and showed that under some natural assumptions there exists a unique Nash equilibrium. The current literature on organ transplant applications mainly uses deterministic fluid models to address a variety of decision-making problems. In the current work, we consider a stochastic bipartite matching system and develop asymptotically optimal policies construced by the corresponding fluid model. The fluid model was also considered in Arnosti and Shi (2020) for the public housing application. They studied a matching queue with strategic waiting agents, where the DM has to strike a balance between targeting individuals with the highest need (fairness) and matching individuals with the resources that produce high value (efficiency). The recent work by Ding et al. (2021) studied a matching queue where the DM allocates the resource to the customer with the highest score, which is the sum of customer’s waiting time and matching score. The system is formulated as a stochastic model, the authors studied a fluid sample path of the system and developed an efficient algorithm to analyze the steady state of the fluid sample path. In the study of a ridesharing system, Özkan and Ward (2020) studied a stochastic matching system of drivers and customers with time-varying arrival rates. They developed asymptotically optimal matching policies based on a continuous linear program for a finite horizon control problem. Compared with this work, we consider a Markovian system which allows class change for a long-run average control problem and prove the asymptotic optimality under both long-run average and ergodic cost criteria.

All the aforementioned works including the current work focus on optimizing the demand side of the system and the supply is either matched or wasted, and thus can be viewed as one-sided controlled matching systems. If resources can also be queued in addition to customers, the system becomes a two-sided controlled system. For example, Aveklouris et al. (2021) proposed a two-sided matching queue with generally distributed patience times and studied the tradeoff between making quick valuable matches and waiting to make better decisions with the risk of losing impatient demand and supply. Afeche et al. (2021) studied the design of matching topology in a multiclass multiserver queueing system under a first come first served - assign longest idle server (FCFS-ALIS) service discipline. Beyond bipartite matching queues, Gurvich and Ward (2015) modeled a matching queue in which items arrive to their dedicated queue and wait to be matched with items of other queues based on match feasibility to minimize a finite-horizon cumulative holding cost function.

2.2. Queueing Systems with Class Change Feature

In addition to the aforementioned transplant queueing models and the work by Hu et al. (2021), Down and Lewis (2010) studied the effect of class change on the stability and optimal policies for a Markovian N model with two customer classes and two service stations (with multiple servers), where station 1 is flexible in serving both customer classes and station 2 is dedicated to customer class 2, and class 1 customers are allowed to be upgraded to class 2. In Cao and Xie (2016), a two-class single-server queue was studied, where class 1 customers can change to class 2. The queueing control problem is formulated as a continuous-time Markov decision process and the main results establish the existence of optimal nonidling stationary policies and the conditions under which a modified $c\mu$ rule remains optimal. Xie et al. (2017) computed the stationary distribution of a two-class single-server priority queue that allows priority upgrade for nonpriority customers. These three works focus on the low-dimensional systems and do not consider abandonment or large-scale asymptotic setting. In Pang and Yao (2013), a collection of Markovian many-server queues, each queue with its own service pool, were considered, where a job waiting in a queue can switch over to another queue or abandon the system after an exponentially distributed time. The work is concerned with system performance analysis and establishes the fluid and diffusion limits under different large-scale regimes (quality-and-efficiency-driven and efficiency-driven regimes).

2.3. Scheduling Control of Multiclass Queueing Systems in Heavy Traffic

There is a significant literature on scheduling control of queues, where there is a fixed number of service stations/server pools in the system that serve randomly arriving heterogeneous customers. We review some related works in the many-server setting, focusing on the long-run average type objectives, or related to the X model. None of these works consider the class change feature studied in the current work. The works by Atar et al. (2010, 2011) developed the well-known $c\mu /\theta$ rule for the Markovian multiclass many-server (in a single pool) queueing system with abandonments to minimize the long-run average cost, and showed that $c\mu /\theta$ rule is asymptotically optimal under both the long-run average cost and ergodic cost criteria in the fluid scaling. For an overloaded (i.e., in the efficiency driven regime) multiclass many-server queue with multiple server pools, Stolyar and Tezcan (2011) proposed the shadow routing algorithm for reward maximization (SHADOW-RM) policy, and proved its asymptotic optimality for maximizing the long-run reward rate. For other works in scheduling overloaded multiclass many-server (in a single pool) queues, we refer the readers to the tutorial paper (Puha and Ward 2019) and the references therein. The literature on the ergodic control of many-server queues seems scarce. Armony and Ward (2010) designed a threshold policy for a single-class multipool many-server queue (known as the inverted V model) and showed that it is asymptotically optimal for minimizing the steady-state customer waiting time subject to a “fairness” constraint on the workload division in quality-and-efficiency driven regime. The ergodic control problem of the Markovian multiclass many-server (in a single pool) queues was studied in Arapostathis et al. (2015), and the study was extended to multipool setting in Arapostathis and Pang (2016). Both works are considered in the quality-and-efficiency driven regime. Comparing with these studies, our system assumes heterogeneity on both sides and class change feature for the customer side. We do not assume specific regimes and prove that the proposed policy is asymptotically optimal under both the long-run average cost and ergodic cost criteria.

As the simplest multiclass multipool queueing system, the X model has been studied in a series of work by Perry and Whitt (2009, 2011, 2013, 2015). Perry and Whitt (2009) studied two service systems (modeled as single-class single-pool many-server queues with abandonment) that can help each other when one encounters overload, and proposes an efficient fixed-queue-ratio-with-thresholds (FQR-T) control. In the sequels, Perry and Whitt (2011, 2013, 2015) developed fluid approximations and new algorithms for the overloaded X model under the FQR-T control. Our study of the X matching models focuses on exploring the impact of the class change rates and acceptance probabilities on fluid control problems.

3. Model Formulation

We study a bipartite matching queue where customers arrive to one side of the system and resources arrive to the other side. Customers and resources are differentiated by their classes and types. The customer class is indexed by $i\in \mathbb{I}≔\{1,2,\dots ,I\}$ so that there are totally I different customer classes. Customers of class i arrive to the system according to a Poisson process with rate λ_i and will join queue i on arrival. Customers in queue may abandon the system or join another queue while waiting. More precisely, the transition mechanism works as follows: Each customer in queue i is associated with I + 1 independent transition clocks, and for $j=0,1,\dots ,I$, the jth clock rings after an exponentially distributed time with rate ρ_ij. If the jth clock rings first, the customer will join queue j, where queue j = 0 is interpreted as the outside of the system, that is, the customer will abandon the system. We assume that ${\rho }_{ii}=0$, which indicates that the customers in queue i will not leave their current position to join queue i again. There will be H types of resources, and the units of resource of type $h\in \mathbb{H}≔\{1,2,\dots ,H\}$ arrive to the system according to a Poisson process with rate μ_h. We assume each customer is matched with one resource unit and the matching is instantaneous, that is, each resource unit should be allocated to a customer immediately on arrival.

For each resource type h, let $\mathbb{I}(h)$ denote the index set of customer classes for which the resource type h is a feasible match. For each customer class i, let $\mathbb{H}(i)$ denote the set of resource types that are feasible for class i customers. Without loss of generality, we assume that $\mathbb{I}(h)\ne \varnothing$ for all h, and $\mathbb{H}(i)\ne \varnothing$ for all i, that is, for each resource type (respectively, customer class) there is at least one customer class (respectively, resource type) such that their matching is feasible because otherwise we can exclude that resource type (respectively, customer class) from analysis upfront without affecting the system. The matching topology is characterized by $\mathbb{I}(h)$ and $\mathbb{H}(i)$ for $i\in \mathbb{I}$ and $h\in \mathbb{H}$ and is assumed to be fixed.

On arrival of each resource unit, the DM will allocate it to the head-of-line of a feasible customer queue, and if all feasible customer queues are empty, the unit will be wasted and removed from the system. A match may fail and we let a_hi denote the probability that a match of the customer class $i\in \mathbb{I}$ with the resource type $h\in \mathbb{H}$ is successful. If the match is successful, the customer leaves the system instantaneously with the offered resource unit; otherwise, the customer will stay in the system and the resource unit is wasted and removed from the system. Figure 1 provides a schematic view of the system. One application for a matching failure is that customers may have a preference over resource types and a customer who is offered a resource unit may decline it for a hope that the future offer is of the type that the customer has a higher preference for. For this application our approach assumes that customer decisions in accepting/declining the resource are exogenous; that is, we model those decisions by considering acceptance probabilities a_hi. For example, for the application of the proposed matching system for transplant systems, all the simulation models for organ allocation purposes developed by the United Network for Organ Sharing (LSAM for liver, TSAM for lung and heart, and KPSAM for kidney and pancreas) consider the acceptance probabilities for patients based on past observations (UNOS 2021). Another example is in ride sharing applications, where a customer may decline the offered driver with a probability that may depend on different factors (Özkan and Ward 2020). Another application for a matching failure is that the matching process is disrupted. For example, in a communication channel, packages sent from a supply node to a demand node may get lost or corrupted.

We now mathematically formulate the problem. Let $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$ be a complete probability space. All the random variables and stochastic processes in this section are assumed to be defined on this space. The expectation under the probability measure $\mathbb{P}$ will be denoted by $\mathbb{E}$. For $t\ge 0$, denote by $X_i(t)$ the number of customers of class i in the system at time t, $U_{hi}(t)$ the number of successful matches of resource type h to customer class i up to time t, and $V_{hi}(t)$ the number of resource units of type h assigned to customer class i up to time t. Let $A_i(t)$ and $E_h(t)$, respectively, represent the Poisson arrival processes of customers of class i and resource units of type h. Because the transition clocks associated with each customer are independent and exponentially distributed, the transition processes between customer queues can be formulated using independent Poisson processes. Let $N_{ij},i\in \mathbb{I},j\in \mathbb{I}\cup \{0\}$ be independent unit rate Poisson processes, which are independent of the arrival processes $A_i,E_h,i\in \mathbb{I},h\in \mathbb{H}$. Then, the number of customers in queue i that join the customer queue j by time t can be formulated as $N_{ij}({\rho }_{ij}{\int }_0^t{X}_i(s)ds).$ Consequently, the state process can be described as follows: For $t\ge 0$ and $i\in \mathbb{I}$,

where $X_i(0)$ is the initial number of customers in queue i, and the nondecreasing process $U_{hi}(t)$ satisfies

Furthermore, the random variables $X_i(0),i\in \mathbb{I}$ are assumed to be independent of the arrival processes $A_i,E_h,i\in \mathbb{I},h\in \mathbb{H}$ and the Poisson processes $N_{ij},i\in \mathbb{I},j\in \mathbb{I}\cup \{0\}.$

The allocation policy is represented by a matrix-valued stochastic process $\{\pi (t);t\ge 0\}$: At time t, $\pi (t)={({\pi }_{hi}(t))}_{H\times I}$, where each ${\pi }_{hi}(t)$ equals zero or one and there is at most one element equal to one in each row, that is, ${\sum }_{i\in \mathbb{I}(h)}{\pi }_{hi}(t)\le 1$ for each $h\in \mathbb{H}$ and ${\pi }_{hi}(t)=0$ for $i\notin \mathbb{I}(h)$. Suppose that a unit of type h resource arrives at time t. If ${\pi }_{hi}(t)=1$ for some $i\in \mathbb{I}(h)$, the unit is assigned to the customer queue i. Otherwise, if ${\pi }_{hi}(t)=0$ for all $i\in \mathbb{I}(h)$, the unit will be wasted. We study nonanticipative allocation policies. To this end, define the following filtration: For $t\ge 0,$

which represents all relevant information available to the DM at time t and σ denotes sigma field. An allocation policy $\{\pi (t);t\ge 0\}$ is nonanticipative if $\pi (t)\in {\mathcal{F}}_t$ for all $t\ge 0$, and it is called admissible if it satisfies the previously mentioned constraints as well.

Given an admissible control policy $\{\pi (t);t\ge 0\}$, the allocation process $\{V_{hi}(t);t\ge 0\}$ and the successful matching process $\{U_{hi}(t);t\ge 0\}$ can be formulated as follows. Let ${\nu }_h^k$ denote the arrival time of the kth unit of resource type h (that is, the kth arrival time of the Poisson process $E_h(t)$). We have for $t\ge 0$,

Note that ${\pi }_{hi}(t)$ can also be completely characterized by the jump times of $V_{hi}(t)$.

An assigned unit may result in a successful match or a waste. Let ${\{w_{hi}^k\}}_{k\in \mathbb{N}}$ be an independently identically distributed (i.i.d.) sequence of Bernoulli random variables with successful probability a_hi, which represents the probability of a successful match between customer class i and resource type h. Thus, for $t\ge 0$,

We assume that for each $h\in \mathbb{H}$ the vector $w_h^k≔(w_{h1}^k,w_{h2}^k,\dots ,w_{hI}^k)\prime$ is independent of ${\mathcal{F}}_{{\nu }_h^k}$ and all the external arrival processes $\{E_h(t);t\ge 0\}$ and $\{A_i(t);t\ge 0\}$ for $i\in \mathbb{I}$ and $h\in \mathbb{H}$ (noting that $\prime$ denotes matrix transpose). That is, the success of a match only depends on the class and type of the pair and is independent of the aforementioned system information.

Next, we provide the elements of the objective function. The DM considers the following factors in the matching system: (1) the value of successful matches, (2) the waiting cost of customers, and (3) the abandonment cost of customers. (One can also consider the wastage cost of a resource, see Section 8.) Specifically, the DM seeks to maximize the average value of the successful matches and minimize the average waiting and abandonment costs over a finite planning horizon $[0,T]$ (to establish asymptotic optimality, we will eventually consider a long horizon by letting $T\to \infty$). Let ${\vartheta }_{hi}$ denote the value of a successful match between a customer in class i and a resource unit of type h. Let $c_i^w$ denote the linear holding cost that a class i customer imposes to the system per unit time, and $c_i^a$ denote the cost that is imposed to the system if a customer of class i abandons the system. Let $c_i=c_i^w+{\rho }_{i0}{c}_i^a$ denote the total expected cost of holding and abandonment per customer of class i per unit time. Given an admissible allocation policy $\pi =\{\pi (t);t\ge 0\}$, the expected average holding and abandonment cost over the time interval $[0,T]$ is given by

In addition, the expected average value of successful matches is given by

Because the DM seeks to choose admissible policies to minimize the objective function (5), and to maximize the objective function (6), we combine the two objectives into one and consider a weighted average of the two objective functions by assigning a weight of ${\omega }_1\ge 0$ to the minimization objective (5) and ${\omega }_2\ge 0$ to the maximization objective (6), where ${\omega }_1+{\omega }_2>0$. Without loss of generality, we present the objective in the minimization sense; that is, we consider the following expected “weighted cost” of an admissible allocation policy $\pi =\{\pi (t):t\ge 0\}$:

where $\mathcal{M}$ collects all the known system parameters. More precisely, for our analysis, it is assumed that all the arrival rates $\lambda \equiv ({\lambda }_1,\dots ,{\lambda }_I)\prime ,\mu \equiv ({\mu }_1,\dots ,{\mu }_H)\prime$, the class change rates $\rho \equiv {({\rho }_{ij})}_{I\times (I+1)}$, the acceptance probabilities $a\equiv {(a_{hi})}_{H\times I}$, the total costs $c\equiv (c_1,\dots ,c_I)\prime$, and the matching values $\vartheta \equiv {({\vartheta }_{hi})}_{H\times I}$ are given. These parameters are collected in $\mathcal{M}$, that is, $\mathcal{M}=(\lambda ,\mu ,\rho ,a,c,\vartheta ).$ Therefore, the DM solves the following control problem to calculate the value functionwhere the infimum is taken over all admissible allocation policies.

The direct analysis of the control problem (8) is rather complex, and the standard numerical methods do not apply because of the curse of dimensionality. Our goal is to (i) develop a stability condition under which a simple LP, referred to as the fluid control problem (FCP), provides a lower bound for the queue control problem (QCP) (8) when $T\to \infty$, (ii) construct asymptotically optimal allocation policies for the QCP (8) in a suitable large-scale setting by using the optimal solution of the LP, and (iii) show that under the proposed policy, the matching system in the large-scale setting is ergodic with a unique stationary distribution. The next section develops the FCP of interest.

4. FCP

In this section, we construct the FCP by considering the expectation of the stochastic processes constructed previously. We develop a suitable stability condition (Assumption 1) under which the FCP attains a simple reformulation, and its optimal value provides a lower bound for the QCP (Proposition 1).

4.1. Construction of the FCP

We first establish a lemma that will be used in the construction of the FCP. Recall the allocation process $\{V(t);t\ge 0\}$ and the successful matching process $\{U(t);t\ge 0\}$ from (3) and (4). It can be shown that $\mathbb{E}(U_{hi}(t)|V_{hi}(t))=a_{hi}{V}_{hi}(t)$ for all $t,i,h$. Taking expectation in (1) yields that for $t\ge 0$ and $i\in \mathbb{I},$

Next, taking expectation in (2), we have

Now define $x_i(t)\equiv \mathbb{E}(X_i(t))$ and $v_{hi}(t)\equiv \mathbb{E}(V_{hi}(t))$ for $t\ge 0$. We introduce the following deterministic control problem associated with the state process $x_i(t)$ and the control process $v_{hi}(t)$. This control problem serves as a transitional step to introduce the FCP of interest.

Definition 1.

Given $x(0)=(x_1(0),\dots ,x_I(0))\prime \in {\mathbb{R}}_{+}^I$ and $\mathcal{M}$, the transitional control problem selects $v\equiv \{{(v_{hi}(t))}_{H\times I};t\in [0,T]\}$ to minimize

$${\mathcal{C}}_T(v;x(0),\mathcal{M})\equiv \frac{{\omega }_1}{T}{\displaystyle {\int }_0^T{\displaystyle \sum _{i\in \mathbb{I}}{c}_i}}{x}_i(t)dt-\frac{{\omega }_2}{T}{\displaystyle \sum _{i\in \mathbb{I}}{\displaystyle \sum _{h\in \mathbb{H}(i)}{\vartheta }_{hi}}}{a}_{hi}{v}_{hi}(T)$$(10a)

$$\text{subject}\hspace{0.17em}\text{to}\hspace{0.17em}\text{the}\hspace{0.17em}\text{following}\hspace{0.17em}\text{constraints}:\hspace{0.17em}\text{For}\hspace{0.17em}\hspace{0.17em}t\ge 0\hspace{0.17em}\text{and}\hspace{0.17em}i\in \mathbb{I},h\in \mathbb{H},$$

$$x_i(t)=x_i(0)+{\lambda }_{i}t-{\displaystyle {\int }_0^t\left[{\displaystyle \sum _{k\in \mathbb{I}\cup \left\{0\right\}}{\rho }_{ik}}{x}_i(\tau )-{\displaystyle \sum _{l\in \mathbb{I}}{\rho }_{li}}{x}_l(\tau )\right]}d\tau -{\displaystyle \sum _{h\in \mathbb{H}(i)}{a}_{hi}}{v}_{hi}(t)\ge 0,$$(10b)

$${\displaystyle \sum _{i\in \mathbb{I}(h)}{v}_{hi}}(t)\le {\mu }_{h}t,$$(10c)

$$v_{hi}(0)=0,\hspace{0.17em}\hspace{0.17em}\text{and} v_{hi}(t)\hspace{0.17em}\hspace{0.17em}\text{is}\hspace{0.17em}\text{non}\hspace{0.17em}\hspace{0.17em}\text{decreasing}\hspace{0.17em}\text{in}\hspace{0.17em}\hspace{0.17em}t.$$(10d)

We are interested in analyzing the system for a long time horizon. Letting $T\to \infty$ enables us to establish a deterministic control problem in equilibrium, which will be the focused FCP. Roughly speaking, we will think of $\{x_i(t);t\ge 0\}$ admitting an equilibrium point $x_i^e$ such that $x_i(t)\to x_i^e$ as $t\to \infty$, and then the long-run average $t^{-1}{\int }_0^t{x}_i(s)ds$ will converge to $x_i^e$ as well when $t\to \infty .$ Instead of considering $v_{hi}(t)$ directly, we study the proportion $v_{hi}(t)/({\mu }_{h}t)$ and denote by $r_{hi}^e$ its formal equilibrium, that is, $v_{hi}(t)/({\mu }_{h}t)\to r_{hi}^e$ as $t\to \infty$. In other words, $r_{hi}^e$ represents the proportion of type h resource assigned to class i customers.

Definition 2

(FCP). The FCP is to select an H × I matrix $r^e={(r_{hi}^e)}_{H\times I}$ to solve

$$\mathcal{C}(\mathcal{M})=\underset{x^e,r^e}{\min }\hspace{0.17em}\hspace{0.17em}{\omega }_1{\displaystyle \sum _{i\in \mathbb{I}}{c}_i}{x}_i^e-{\omega }_2{\displaystyle \sum _{i\in \mathbb{I}}{\displaystyle \sum _{h\in \mathbb{H}(i)}{\vartheta }_{hi}}}{\mu }_h{a}_{hi}{r}_{hi}^e$$(11a)

$$\text{subject}\hspace{0.17em}\text{to}$$

$$\hspace{1em}{\lambda }_i-{\displaystyle \sum _{k\in \mathbb{I}\cup \left\{0\right\}}{\rho }_{ik}}{x}_i^e+{\displaystyle \sum _{l\in \mathbb{I}}{\rho }_{li}}{x}_l^e-{\displaystyle \sum _{h\in \mathbb{H}(i)}{\mu }_h}{a}_{hi}{r}_{hi}^e=0,\hspace{0.17em}\hspace{0.17em}\forall i\in \mathbb{I},$$(11b)

$$\hspace{1em}{x}_i^e\ge 0,\hspace{0.17em}\forall i\in \mathbb{I},$$(11c)

$$\hspace{1em}{\displaystyle \sum _{i\in \mathbb{I}(h)}{r}_{hi}^e}\le 1,\hspace{0.17em}\forall h\in \mathbb{H},$$(11d)

$$\hspace{1em}{r}_{hi}^e\ge 0,\hspace{0.17em}\forall h\in \mathbb{H},i\in \mathbb{I}.$$(11e)

The relationship between the original QCP (8), the transitional control problem (10), and the FCP (11) is characterized in Proposition 1. Before stating the result, we present the following stability condition. Let ${\mathcal{I}}_1\equiv \{i\in \mathbb{I}:{\rho }_{i0}>0\}$ and ${\mathcal{I}}_2\equiv \{i\in \mathbb{I}:{\rho }_{i0}=0\}$. The set ${\mathcal{I}}_1$ (respectively, ${\mathcal{I}}_2$) collects the indices of customer queues for which the abandonment rate is positive (respectively, zero).

Assumption 1

(Stability Condition). The index set ${\mathcal{I}}_1\ne \varnothing$. Furthermore, for any $j\in {\mathcal{I}}_2$, there exist $k\ge 1,\hspace{0.17em}{j}_1,j_2,\dots ,j_k\in {\mathcal{I}}_2$ and $i\in {\mathcal{I}}_1$ such that ${\rho }_{j{j}_1}{\rho }_{j_1{j}_2}\cdots {\rho }_{j_{k}i}>0.$

Assumption 1 says there exists at least one customer queue with a positive abandonment rate, and for any customer queue without abandonment, there exists a transition path from this queue to a customer queue with abandonment through class changes.

4.2. FCP Reformulation

We study some structural properties embedded in the FCP that will be crucial in further analysis. To that end, considering the matrix form of (11b), we let ${\mathit{x}}^{\mathit{e}}=(x_1^e,\dots ,x_I^e)\prime$, and introduce the following matrices:

and

Now, equations in (11b) can be represented as $P{x}^e=b$.

The matrix $\mathit{P}$ plays a crucial role in the analysis throughout the paper. In Section 4.2.1, we present some important structural properties of $P$. Next, in Section 4.2.2, we propose a reformulation to the LP (11), which facilitates the interpretation of the optimal solution.

4.2.1. Structure of Matrix $P$ and Its Inverse.

We develop some important properties of $P$ in Lemma 1. A square matrix is called a nonsingular M-matrix if it can be expressed as $s\text{I}-B$, where $\text{I}$ is the identity matrix, B is a matrix with nonnegative entries, and the scalar s is greater than the spectral radius of B. Nonsingular M-matrices appear in many applications and have rich properties (see Plemmons (1977) for a collection of equivalent definitions for M-matrices.

Lemma 1.

Under Assumption 1, (i) $P$ is a nonsingular M-matrix, (ii) its inverse $P^{-1}$ has positive diagonal entries and nonnegative off-diagonal entries, and (iii) for $i\in {\mathcal{I}}_1$ and $j\in {\mathcal{I}}_2$, the (i, j)th entry of $P^{-1}$ is positive.

The proof of Lemma 1 is provided in Appendix B.1, and the key is to observe that the matrix P is a weakly chained diagonally dominant matrix.

For convenience, let $A=P^{-1}$. The entries of the matrix A could be rather complicated. In Appendix A, we investigate a special case when P is upper triangular to shed some light on its structure.

4.2.2. FCP Reformulation Presentation.

In this section, we provide a reformulation to the FCP (11) that will pave the way to provide insights on its optimal solutions. From Lemma 1, we have that $x^e=P^{-1}b=Ab$, that is, Equation (11b) can be written as $x_i^e={\sum }_{k\in \mathbb{I}}{A}_{ik}{\lambda }_k-{\sum }_{k\in \mathbb{I}}{A}_{ik}{\sum }_{h\in \mathbb{H}(k)}{\mu }_h{a}_{hk}{r}_{hk}^e$, and its substitution in Equation (11c) results in the following Equation (14b). Therefore, Formulation (11) can now be reformulated as follows:

where ${\tilde{c}}_{hi}={\mu }_h{a}_{hi}({\sum }_{k\in \mathbb{I}}{\omega }_1{c}_k{A}_{ki}+{\omega }_2{\vartheta }_{hi})\ge 0$. We observe that the coefficient ${\tilde{c}}_{hi}$ for the allocation rate $r_{hi}^e$ depends both on matching values and costs. Specifically, because of class change, ${\tilde{c}}_{hi}$ for class i includes the cost c_k from all other classes weighted by A_ki.

The optimization problem (14) is an LP with a bounded convex nonempty solution space and thus admits an optimal solution at the boundary.

Lemma 2.

Under Assumption 1, the FCP admits an optimal solution.

Denote by $r^{e,*}={(r_{hi}^{e,*})}_{H\times I}$ an optimal solution and $x^{e,*}=(x_1^{e,*},\dots ,x_I^{e,*})\prime$ the corresponding optimal state. One may interpret $r_{hi}^{e,*}$ as the optimal proportion of type h resource assigned to customers of class i. For an optimal solution, if the ith constraint in (14b) becomes active, then $x_i^{e,*}=0$; otherwise, $x_i^{e,*}>0$ because $x_i^e={\sum }_{k\in \mathbb{I}}{A}_{ik}{\lambda }_k-{\sum }_{k\in \mathbb{I}}{A}_{ik}{\sum }_{h\in \mathbb{H}(k)}{\mu }_h{a}_{hk}{r}_{hk}^e$. If the hth constraint in (14c) becomes active, all the resource units of type h are used; otherwise, the optimal solution wastes some of it. Furthermore, if the optimal solution constraints in (14b) are all inactive, that is, $x_i^{e,*}>0$ for all $i\in \mathbb{I}$, the system is “strictly overloaded.” Consequently, the optimization problem (14) becomes a knapsack problem whose solution is a priority policy by sorting ${\tilde{c}}_{hi}$’s. In this case, for resource type h, customers’ priority will be based on $a_{hi}({\sum }_{k\in \mathbb{I}}{\omega }_1{c}_k{A}_{ki}+{\omega }_2{\vartheta }_{hi})$. The exact optimal solution of the LP depends on the matching topology (i.e., the index sets $\mathbb{I}(h)$ and $\mathbb{H}(i)$ for each i and h) and the system parameters $\mathcal{M}$. To provide insight on the structure of the optimal solution, we study two low-dimensional matching systems in Section 5.

4.3. Lower Bound on QCP

We now present Proposition 1 that shows that the FCP serves as a lower bound for the QCP as the time horizon tends to infinity. This enables us to construct asymptotic (in a sense that will be clear later in Section 6) optimal policies for the QCP by using the optimal solution of the FCP. First, we show the following Lemma 3 that says under Assumption 1 the matching system is stable under any admissible control, and will be used in the proof of Proposition 1.

Lemma 3.

Under Assumption 1, there exist positive constants C₁ and C₂ that are independent of t such that for any $t\ge 0$,

$$\mathbb{E}\left({\displaystyle \sum _{i\in \mathbb{I}}{X}_i}(t)\right)\le C_1\mathbb{E}\left({\displaystyle \sum _{i\in \mathbb{I}}{X}_i}(0)\right)+C_2.$$

Proposition 1.

Under any admissible policy π for the QCP (8) and for any $T\ge 0$,

$$C_T(\pi ;X(0),\mathcal{M})\ge {\mathcal{C}}_T(\mathbb{E}(V);\mathbb{E}(X(0)),\mathcal{M}),$$(15)

where V is the allocation process under the policy π. Furthermore, under Assumption 1,

$$\underset{T\to \infty }{\text{lim inf}} {\mathcal{C}}_T(\mathbb{E}(V);\mathbb{E}(X(0)),\mathcal{M})\ge \mathcal{C}(\mathcal{M}).$$(16)

The complete proofs of Lemma 3 and Proposition 1 are provided in Appendix B.1. Roughly speaking, the first part of Proposition 1 is true because the constraints in the FCP are created from those of the original stochastic control problem, as well as having the same objective. The second part holds because by Lemma 3, ${\lim }_{T\to \infty }{x}_i(T)/T=0$, which makes the constraints in (10) converge to those in (11).

4.4. Proposed Policy for QCP

We construct a simple randomized allocation policy for QCP using an optimal solution of the FCP. Under Assumption 1, denote by $r^{e,*}={(r_{hi}^{e,*})}_{H\times I}$ an optimal solution and $x^{e,*}=(x_1^{e,*},\dots ,x_I^{e,*})\prime$ the corresponding state of the FCP with parameter $\mathcal{M}$. For each $h\in \mathbb{H}$, let $r_{h0}^{e,*}=1-{\sum }_{i\in \mathbb{I}}{r}_{hi}^{e,*}$ representing the probability of wasting a resource unit of type h. We consider a generalized Bernoulli random vector $Z_h=(Z_{h0},Z_{h1},\dots ,Z_{hI})\prime$ according to the probability distribution $(r_{h0}^{e,*},r_{h1}^{e,*},\dots ,r_{hI}^{e,*})\prime .$ More precisely, we consider a random vector $Z_h=(Z_{h0},Z_{h1},\dots ,Z_{hI})\prime$ such that each component Z_hi is Bernoulli distributed with success probability $r_{hi}^{e,*}$ and ${\sum }_{i=0}^I{Z}_{hi}=1$. The distribution of Z_h is then given by

for $z_i\in \{0,1\},i=0,1,\dots ,I$ and ${\sum }_{i=0}^I{z}_i=1$. For each arriving resource unit of type h, we sample the random vector Z_h, independently of the past, and assign the unit to the customer queue i if Z_hi = 1 and queue i is nonempty; otherwise, if queue i is empty, we simply assign it to queue 0 and waste the unit.

Denote by ${\pi }^{*}(\mathcal{M})$ the previously described allocation policy. Clearly, it is admissible. The policy is not work-conserving; a resource unit is wasted when it is assigned to a customer queue that is empty, no matter other customer queues that can accept the resource be empty or not. Nevertheless, in Section 6.1, we will show that this policy is asymptotically optimal when the system scale is large, and the resource units wasted in the previous situation are asymptotically negligible.

5. FCPs for Two X Models

We analytically solve the FCP for two X matching models and investigate how their solutions depend on the class change rates and the success probability of matching. In the first model, we study a transplant system with two patient classes and two organ types and establish an optimal policy that is of assortative or priority type depending on a threshold. The threshold parameter is given in terms of the class change and abandonment rates, and the success probability of matching (Proposition 2). For the second model, an X model with no matching failure is considered where the FCP only minimizes the linear cost. We show that a simple index policy, referred to as the $c{P}^{-1}$ rule, is optimal and generalizes the well-known $c\mu /\theta$ rule developed in Atar et al. (2010) and the modified $c\mu /\theta$ rule developed in Hu et al. (2021) to an X matching model (Proposition 3).

5.1. An X Model for a Transplant System

We consider a transplant queueing system with two patient classes (Sick and Healthy) and two organ types (Low-quality and High-quality). The arrival rates for Sick and Healthy patients are λ₁ and λ₂, and the arrival rates for Low-quality and High-quality organs are μ₁ and μ₂. Sick patients die with rate ${\rho }_{10}\equiv d_1>0$ and Healthy patients become Sick with rate ${\rho }_{21}\equiv \rho >0$. We assume that Healthy patients do not die while waiting (i.e., ${\rho }_{20}=0$) and Sick patients do not become Healthy (i.e., ${\rho }_{12}=0$). We also assume that Sick patients accept both organs with probability one (i.e., $a_{11}=a_{21}=1$), Healthy patients accept High-quality organs with probability one (i.e., $a_{22}=1$), but accept Low-quality organs with probability $a_{12}\equiv a\in (0,1]$. Figure 2 shows a schematic view of the system. In transplant queueing systems, it is natural to assume that ${\lambda }_1+{\lambda }_2>{\mu }_1+{\mu }_2$, that is, the system is overloaded in the sense that the demand for organs exceeds the supply. Under this assumption, summing up (11b) over i = 1, 2 results in $d_1{x}_1^e={\lambda }_1+{\lambda }_2-{\mu }_1(r_{11}^e+a{r}_{12}^e)-{\mu }_2>0$ under any feasible allocation policy. Thus, no organ will be wasted (because of no available patients), which yields that the allocation rates must satisfy $r_{11}^e+r_{12}^e=r_{21}^e+r_{22}^e=1$. The matrix $P$ and its inverse A are given by

In the FCP, the cost c_i represents the pretransplant mortality, as well as the social costs corresponding to waiting on the list, and the matching values ${\vartheta }_{hi}$ denote the posttransplant survival of a patient in class i on transplanting an organ of type h. It is natural to assume that ${\vartheta }_{11}\le {\vartheta }_{12}$ and ${\vartheta }_{21}\le {\vartheta }_{22}$. That is, the posttransplant survival of Sick patients is less than or equal to that of Healthy patients. The FCP in (14) will be given by

Constraint (17b) is redundant because from the overloaded condition that ${\lambda }_1+{\lambda }_2>{\mu }_1+{\mu }_2$, we have

Introduce

We note that $C_2>0$, but C₁ can be positive or negative or zero. For this system, we interpret the optimal allocation policy as being (i) assortative or (ii) of priority type. Assortative policies are those that assign high-quality organs to patients with lower risk (moderately healthy) and vice versa. We collect the optimal solutions of the FCP in the following Proposition 2; the proof is standard and provided in Appendix B.2.

Proposition 2.

When ${\lambda }_2\ge a{\mu }_1+{\mu }_2$, we have $r_{11}^{e,*}$ is equal to one if $C_1<0$, is equal to 0 if $C_1>0$, and can take any value in $[0,1]$ if $C_1=0.$ And $r_{21}^{e,*}$ is always equal to zero. When ${\lambda }_2<a{\mu }_1+{\mu }_2$, the optimal solution is summarized in the following cases.

• (1) If $C_1<0$, $r_{11}^{e,*}=1$ and $r_{21}^{e,*}=\max \{0,({\mu }_2-{\lambda }_2)/{\mu }_2\}$.

• (2) If $C_1=0$, $r_{11}^{e,*}\in [1+({\mu }_2-{\lambda }_2-{\mu }_2{r}_{21}^{e,*})/(a{\mu }_1),1]$ and $r_{21}^{e,*}=\max \{0,({\mu }_2-{\lambda }_2)/{\mu }_2\}$.

• (3) If $0<C_1/C_2<a$, $r_{11}^{e,*}=\min \{1+({\mu }_2-{\lambda }_2)/(a{\mu }_1),1\}$ and $r_{21}^{e,*}=\max \{0,({\mu }_2-{\lambda }_2)/{\mu }_2\}$.

• (4) If $C_1/C_2=a$, any feasible point on the line $a{\mu }_1{r}_{11}^{e,*}+{\mu }_2{r}_{21}^{e,*}+{\lambda }_2-a{\mu }_1-{\mu }_2=0$ is an optimal solution.

• (5) If $C_1/C_2>a$, $r_{11}^{e,*}=\max \{0,(a{\mu }_1-{\lambda }_2)/(a{\mu }_1)\}$ and $r_{21}^{e,*}=\min \{1+(a{\mu }_1-{\lambda }_2)/{\mu }_2,1\}$.

Remark 1.

From Section 4.4, we can construct a randomized policy based on the solution of the FCP for QCP. For example, in Case (1), when $C_1<0$, if ${\mu }_2>{\lambda }_2$, then $r_{21}^{e,*}=({\mu }_2-{\lambda }_2)/{\mu }_2\in (0,1).$ This says $r_{21}^{e,*}$ proportion of High-quality organs should be assigned to Sick patients and $1-r_{21}^{e,*}$ proportion of High-quality organs should be assigned to Health patients. However, in view of the optimal solution and its associated optimal state, we can also interpret the policy being of priority type or assortative. In Case (1), $r_{11}^{e,*}=1$ indicating the type 1 (Low-quality) organs should prioritize class 1 (Sick) patients. Next, $r_{22}^{e,*}=1-r_{21}^{e,*}=\min \{1,{\lambda }_2/{\mu }_2\}$. This says if ${\lambda }_2\ge {\mu }_2$, all the type 2 (High-quality) organs are allocated to class 2 (Healthy) patients and $x_2^{e,*}=({\lambda }_2-{\mu }_2)/\rho \ge 0$, and if ${\lambda }_2<{\mu }_2$, the type 2 (High-quality) organs should prioritize the class 2 (Healthy) patients such that $x_2^{e,*}=0$ and the rest ($r_{21}^{e,*}=({\mu }_2-{\lambda }_2)/{\mu }_2$ proportion) can be allocated to the class 1 (Sick) patients. In this way, we can propose an assortative policy for the QCP, which says the type 1 (Low-quality) organs should prioritize class 1 (Sick) patients and the type 2 (High-quality) organs should prioritize class 2 (Healthy) patients. Similar analysis can be applied to other cases. We summarize the results in Table 1.

However, not all optimal solutions of the FCP can be easily interpreted as being assortative or of priority type. For example, in Case (4) of the previous proposition, if we compute an optimal solution $(r_{11}^{e,*},r_{21}^{e,*})$ for which both $r_{11}^{e,*}$ and $r_{21}^{e,*}$ are within (0, 1) (this happens when the solution is in the interior of the line segment). In this situation, it is not straightforward to design an assortative or priority policies, and a randomized policy naturally arises, assigning $r_{11}^{e,*}$ proportion of Low-quality organs and $r_{21}^{e,*}$ proportion of High-quality organs to Sick patients, and the rest goes to Health patients.

The following two examples are concerned with two special cases to provide more insight: when ${\omega }_1=1$ and ${\omega }_2=0$ and when ${\omega }_1=0$ and ${\omega }_2=1$.

Table 1. Intuition for Results in Proposition 2

Example 1.

We consider the special case when ${\omega }_1=1$ and ${\omega }_2=0$, in which the DM seeks to minimize pretransplant mortality, as well as social costs corresponding to waiting on the list. In terms of application, it means that the DM does not include posttransplant survival, that is, matching values, in the objective. This is aligned with practice for some organs. For example, UNOS allocation rules for liver and heart do not include donor risk profiles and in broad view are medical urgency based (OPTN 2021). We have

$$C_1=a\left(\frac{c_1}{d_1}+\frac{c_2}{\rho }\right)-\frac{c_1}{d_1},\hspace{0.17em}\hspace{0.17em}{C}_2=\frac{c_2}{\rho },$$

which yields

$$C_1<(\ge )\hspace{0.17em}0\iff a<(\ge )\hspace{0.17em}\frac{c_1/d_1}{c_1/d_1+c_2/\rho },$$(19)

and

$$\frac{C_1}{C_2}=\frac{-c_1/d_1+\left(c_1/d_1+c_2/\rho \right)a}{c_2/\rho }=a-\frac{(1-a)c_1/d_1}{c_2/\rho }\le a.$$(20)

Thus, Case (5) of Proposition 2 does not happen. Proposition 2 provides the following insight into the optimal allocation: If the probability that class 2 (Healthy) patients accept type 1 (Low-quality) organs is less than the threshold $\left(c_1/d_1\right)/\left(c_1/d_1+c_2/\rho \right)$, the optimal policy is assortative in that type 1 (Low-quality) organs are matched with class 1 (Sick) patients and type 2 (High-quality) organs are matched with class 2 (Healthy) patients. However, if the probability that class 2 (Healthy) patients accept type 1 (Low-quality) organs is greater than the threshold, the optimal policy prioritizes class 2 (Healthy) patients: High-quality and Low-quality organs will satisfy Healthy patients first, and the rest goes to the Sick patients.

Example 2.

We consider the special case when ${\omega }_1=0$ and ${\omega }_2=1$, in which the DM maximizes the successful matching values, that is, posttransplant survival. We have

$$C_1=a{\vartheta }_{12}-{\vartheta }_{11},\hspace{0.17em}\hspace{0.17em}{C}_2={\vartheta }_{22}-{\vartheta }_{21},$$

which yields

$$C_1<(\ge )\hspace{0.17em}0\iff a<(\ge )\hspace{0.17em}\frac{{\vartheta }_{11}}{{\vartheta }_{12}},$$(21)

and

$$\frac{C_1}{C_2}=\frac{a{\vartheta }_{12}-{\vartheta }_{11}}{{\vartheta }_{22}-{\vartheta }_{21}}<(\ge )\hspace{0.17em}a\iff {\vartheta }_{12}-a^{-1}{\vartheta }_{11}<(\ge )\hspace{0.17em}{\vartheta }_{22}-{\vartheta }_{21}.$$(22)

The threshold of the acceptance probability in (21) is given as ${\vartheta }_{11}/{\vartheta }_{12}$, which only depends on the two matching values. From (22), we see that the relationship between $C_1/C_2$ and a is determined by the quantities ${\vartheta }_{12}-{\vartheta }_{11}$ and ${\vartheta }_{22}-{\vartheta }_{21}$ that represent the posttransplant survival difference between Healthy and Sick patients from the Low-quality and High-quality organs, respectively. More precisely, when $C_1>0$, we have

• If ${\vartheta }_{12}-{\vartheta }_{11}\le {\vartheta }_{22}-{\vartheta }_{21}$, then ${\vartheta }_{12}-a^{-1}{\vartheta }_{11}<{\vartheta }_{22}-{\vartheta }_{21}$ and $C_1/C_2<a$,

• If ${\vartheta }_{12}-{\vartheta }_{11}>{\vartheta }_{22}-{\vartheta }_{21}$, and $a<{\vartheta }_{11}/[{\vartheta }_{12}-({\vartheta }_{22}-{\vartheta }_{21})]$, then ${\vartheta }_{12}-a^{-1}{\vartheta }_{11}<{\vartheta }_{22}-{\vartheta }_{21}$ and $C_1/C_2<a$,

• If ${\vartheta }_{12}-{\vartheta }_{11}>{\vartheta }_{22}-{\vartheta }_{21}$, and ${\vartheta }_{11}/[{\vartheta }_{12}-({\vartheta }_{22}-{\vartheta }_{21})]\le a\le 1$, then ${\vartheta }_{12}-a^{-1}{\vartheta }_{11}\ge {\vartheta }_{22}-{\vartheta }_{21}$ and $C_1/C_2\ge a$,

Thus, Case (5) of Proposition 2 happens only when ${\vartheta }_{12}-{\vartheta }_{11}>{\vartheta }_{22}-{\vartheta }_{21}$ and the acceptance probability a is large enough such that $a>{\vartheta }_{11}/[{\vartheta }_{12}-({\vartheta }_{22}-{\vartheta }_{21})].$

Let $\mathbb{H}\times \mathbb{I}$ be a lattice and $\vartheta \equiv {\{{\vartheta }_{hi}\}}_{h,i\in \mathbb{H}\times \mathbb{I}}$ be a function defined on it. The condition ${\vartheta }_{12}-{\vartheta }_{11}\le (\ge )\hspace{0.17em}{\vartheta }_{22}-{\vartheta }_{21}$ means that the function ϑ is supermodular (submodular). Becker (1973) showed that in a static matching market with equal-sized groups supermodularity (submodularity) of matching values results in a positive (negative) assortative matching, that is, mating of likes (unlikes). Results in Proposition 2 has an assortative flavor when ${\lambda }_2<a{\mu }_1+{\mu }_2$. In particular, if ${\vartheta }_{12}-a^{-1}{\vartheta }_{11}\le {\vartheta }_{22}-{\vartheta }_{21}$, it seeks to maximize $r_{11}^e$ (the rate of assigning Low-quality organs to Sick patients) and minimize $r_{21}^e$ (the rate of assigning High-quality organs to Sick patients). Because of the existence of the acceptance probability a, the required condition becomes ${\vartheta }_{12}-a^{-1}{\vartheta }_{11}\le {\vartheta }_{22}-{\vartheta }_{21}$, with $a^{-1}\ge 1$, which provides the following insight: Because the Healthy patients may decline Low-quality organs, the condition for positive assortative matching becomes “easier” to satisfy.

5.2. An X Model with No Matching Failure

In this section, we consider a matching system with two types of resources and two classes of customers. We assume that the matching process is perfect, that is, $a_{11}=a_{12}=a_{21}=a_{22}=1$, and the matching topology is a complete bipartite graph, that is, $\mathbb{H}(1)=\mathbb{H}(2)=\{1,2\}$ and $\mathbb{I}(1)=\mathbb{I}(2)=\{1,2\}$. The DM is interested in minimizing the linear cost by considering the LP (14) with ${\omega }_1=1$ and ${\omega }_2=0$. Denote by $\mathcal{C}(M)$ the optimal value of the LP.

For this LP, if the system is underloaded or balanced, that is, ${\lambda }_1+{\lambda }_2\le {\mu }_1+{\mu }_2$, there is enough supply of resources for the demand of customers and the system will be empty under the optimal policy in the long run. When the system is overloaded, that is, ${\lambda }_1+{\lambda }_2>{\mu }_1+{\mu }_2$, the optimal solution is a priority policy that assigns priority to each class according to the index ${\sum }_{j=1}^2{c}_j{A}_{ji}$ for $i=1,2.$ Recall that A is the inverse of the rate matrix P. We thus refer to this index policy as the $c{P}^{-1}$ rule, where c is understood to be the row vector (c₁, c₂) and the indices are given as the products of c and the columns of $P^{-1}$. The optimal solutions depend on the following two quantities:

Under the overloaded condition, U > 0 and ${\rho }_{20}L<{\rho }_{10}U$, but it is possible that $L\le 0$. Furthermore, the FCP is equivalent to the following LP:

Proposition 3 characterizes the optimal solutions of the LP in details. Its proof can be found in Appendix B.2, in which we also provide details on deriving the previous LP.

Proposition 3.

If ${\lambda }_1+{\lambda }_2\le {\mu }_1+{\mu }_2$, then $\mathcal{C}(\mathcal{M})=0$ with the optimal solution $r_{ij}^{e,*}\ge 0,i,j=1,2,$ satisfying $r_{11}^{e,*}+r_{12}^{e,*}\le 1,r_{21}^{e,*}+r_{22}^{e,*}\le 1$ and

$$\left(\begin{array}{c}{\lambda }_1\\ {\lambda }_2\end{array}\right)=\left(\begin{array}{cc}{r}_{11}^{e,*}& r_{21}^{e,*}\\ r_{12}^{e,*}& r_{22}^{e,*}\end{array}\right)\left(\begin{array}{c}{\mu }_1\\ {\mu }_2\end{array}\right).$$

If ${\lambda }_1+{\lambda }_2>{\mu }_1+{\mu }_2$, then $r_{11}^{e,*}+r_{12}^{e,*}=r_{21}^{e,*}+r_{22}^{e,*}=1$, and the optimal solutions are given as follows.

• (1) When ${\sum }_{j=1}^2{c}_j{A}_{j2}>{\sum }_{j=1}^2{c}_j{A}_{j1}$ (equivalently, $c_2{\rho }_{10}>c_1{\rho }_{20}$), $r_{11}^{e,*}$ and $r_{21}^{e,*}$ take their minimum feasible values, that is, Class 2 customers receive the higher priority from both types of resources.

  1. If $L\le 0,\hspace{0.17em}{r}_{11}^{e,*}=r_{21}^{e,*}=0$.

  2. If $L>0,\hspace{0.17em}{r}_{11}^{e,*},r_{21}^{e,*}\in [0,1]$ such that ${\mu }_1{r}_{11}^{e,*}+{\mu }_2{r}_{21}^{e,*}=L/{\rho }_{10}$.

• (2) When ${\sum }_{j=1}^2{c}_j{A}_{j2}<{\sum }_{j=1}^2{c}_j{A}_{j1}$ (equivalently, $c_2{\rho }_{10}<c_1{\rho }_{20}$), $r_{11}^{e,*}$ and $r_{21}^{e,*}$ take their maximum feasible values, that is, Class 1 customers receive higher priority from both types of resources.

  1. If $U\ge {\rho }_{20}({\mu }_1+{\mu }_2),\hspace{0.17em}{r}_{11}^{e,*}=r_{21}^{e,*}=1$.

  2. If $U<{\rho }_{20}({\mu }_1+{\mu }_2),\hspace{0.17em}{r}_{11}^{e,*},r_{21}^{e,*}\in [0,1]$ such that ${\mu }_1{r}_{11}^{e,*}+{\mu }_2{r}_{21}^{e,*}=U/{\rho }_{20}$.

• (3) When ${\sum }_{j=1}^2{c}_j{A}_{j2}={\sum }_{j=1}^2{c}_j{A}_{j1}$ (equivalently, $c_2{\rho }_{10}=c_1{\rho }_{20}$), $r_{11}^{e,*}$ and $r_{21}^{e,*}$ can take any feasible values satisfying ${\rho }_{20}[{\mu }_1{r}_{11}^{e,*}+{\mu }_2{r}_{21}^{e,*}]\le U$ and ${\rho }_{10}[{\mu }_1{r}_{11}^{e,*}+{\mu }_2{r}_{21}^{e,*}]\ge L$, and the optimal value $\mathcal{C}(\mathcal{M})=0.$

Remark 2.

We first understand the role of the quantities L and U in (i), and then in (ii) compare the cP⁻¹ rule developed here with the cμ/θ rule.

• (i) The quantities L and U are used to define the traffic intensities for the prioritized queues. In Proposition 3 part (1), from (23), we have

  $$L\ge (<)\hspace{0.17em}0\iff \frac{{\lambda }_2+{\lambda }_1{\rho }_{12}/({\rho }_{10}+{\rho }_{12})}{{\mu }_1+{\mu }_2}\le (>)\hspace{0.17em}1.$$

  One can see that the ratio $[{\lambda }_2+{\lambda }_1{\rho }_{12}/({\rho }_{10}+{\rho }_{12})]/({\mu }_1+{\mu }_2)$ represents the traffic intensity for Class 2 customers when Class 2 is prioritized. Symmetrically, in Proposition 3 part (2), from (24),

  $$U\le (>)\hspace{0.17em}{\rho }_{20}({\mu }_1+{\mu }_2)\iff \frac{{\lambda }_1+{\lambda }_2{\rho }_{21}/({\rho }_{20}+{\rho }_{21})}{{\mu }_1+{\mu }_2}\le (>)\hspace{0.17em}1.$$

  Thus, the ratio $\left[{\lambda }_1+{\lambda }_2{\rho }_{21}/({\rho }_{20}+{\rho }_{21})]/({\mu }_1+{\mu }_2\right)$ represents the traffic intensity for Class 1 customers when Class 1 is prioritized. Under the corresponding priority policy, when the traffic intensity of the prioritized class is less than or equal to one, the prioritized class is always empty and the other class is always nonempty, otherwise, if the traffic intensity is greater than one, then both classes are nonempty.

• Comparing with the well-known $c\mu /\theta$ rule, the $c{P}^{-1}$ rule developed here only depends on the costs and class change rates, and does not depend on the resource arrival rates. In fact, different from the many-server queues considered in Atar et al. (2010, 2011) and Hu et al. (2021), in the bipartite matching queue with complete matching topology, there is no fixed “service rate” for each class of customers, instead each class of customers can be matched with all types of resources. In particular, in a many server queue there is a fixed pool of servers and each server serves class i customers with rate μ_i. However, in our bipartite matching queue, a “server” of type h arrives randomly over time and serves all customer classes with rate μ_h. Different resource types in our model impose different matching values, but in this example, matching values are ignored. (Recall that in an strictly overloaded system, for each resource type h, the priority is given by $a_{hi}({\sum }_{k\in \mathbb{I}}{\omega }_1{c}_k{A}_{ki}+{\omega }_2{\vartheta }_{hi})$, which depends on matching values as well.) Furthermore, if there is only one resource type, the $c{P}^{-1}$ rule is reduced to be the modified $c/\theta$ rule as in Hu et al. (2021), and if there is no class change, the $c{P}^{-1}$ rule is simplified to be the $c/\theta$ rule, which shows that the $c{P}^{-1}$ index policy generalizes the $c\mu /\theta$ rule and the modified $c\mu /\theta$ rule to an X matching model.

6. Asymptotic Framework

This section develops an asymptotic framework, in which suitably scaled stochastic control problems attain the FCP lower bound as the system scale and the time horizon T grow to infinity. We introduce the parameter n that represents the system scale and can be considered as the average number of customers and resource units arriving during a unit time interval. We introduce a sequence of queueing systems as described in Section 3, indexed by $n\in \mathbb{N}$. For the nth system, we append a superscript n to all system processes, random variables, and parameters. However, for simplicity, we assume that the Bernoulli random variables ${\{w_{hi}^k\}}_{k\in \mathbb{N}}$ and its success probability a_hi, and the matching value ${\vartheta }_{hi}$ and cost c_i in the objective function are all independent of n.

To construct the asymptotic setting, we study a large market setup in the following sense.

Assumption 2

(Large Scaled System). For each $n\in \mathbb{N}$, the parameters ${\lambda }^n,{\mu }^n,$ and ρⁿ are nonnegative, and there exist a positive I-dimensional vector $\overline{\lambda }$, a positive H-dimensional vector $\overline{\mu }$, and a nonnegative I × I matrix $\overline{\rho }$ such that as $n\to \infty$,

$$\frac{{\lambda }^n}{n}\to \overline{\lambda },\hspace{0.17em}\frac{{\mu }^n}{n}\to \overline{\mu },\hspace{0.17em}{\rho }^n\to \overline{\rho }.$$

Furthermore, the matrix $\overline{\rho }$ satisfies Assumption 1.

In the nth system, $X_i^n(t)$ represents the number of customers of class i in the system at time t, $U_{hi}^n(t)$ is the number of successful matches of type h resource to class i customers up to time t, and $V_{hi}^n(t)$ is the number of resource units of type h assigned to customer class i up to time t.

Assumption 3

(Initial Condition). There exists a deterministic $\overline{x}(0)\in {\mathbb{R}}_{+}^I$ such that $X^n(0)/n\to \overline{x}(0)$ in probability as $n\to \infty$.

We also recall that $A_i^n(t)$ and $E_h^n(t)$ respectively represent the Poisson arrival processes of customers of class i and resource units of type h for $i\in \mathbb{I}$ and $h\in \mathbb{H}$ and $N_{ij}^n,i\in \mathbb{I},j\in \mathbb{I}\cup \{0\}$ are independent unit rate Poisson processes, which are independent of the arrival processes $A_i^n,E_h^n,i\in \mathbb{I},h\in \mathbb{H}$. The state and control processes $X_i^n(t),\hspace{0.17em}{V}_{hi}^n(t)$, and $U_{hi}^n(t)$ are described as follows: For $h\in \mathbb{H},i\in \mathbb{I}$, and $t\ge 0$,

andwhere $\{{\pi }^n(t);t\ge 0\}$ is an admissible allocation control, ${\{{\nu }_{h,k}^n\}}_{k\in \mathbb{N}}$ are the arrival times of the Poisson process $E_h^n(t)$, and ${\{w_{hi}^k\}}_{k\in \mathbb{N}}$ are i.i.d. sequences of Bernoulli random variables with success probability a_hi, which denotes the probability that a match of a type h resource unit to a class i customer is successful. Under Assumption 2, we introduce the fluid scaled processes:

The control problem for the nth system is to choose an admissible allocation policy ${\pi }^n=\{{\pi }^n(t);t\ge 0\}$ to minimize the following fluid scaled average cost function

where ${\mathcal{M}}^n=({\lambda }^n,{\mu }^n,{\rho }^n,c,\vartheta )$ represents the known parameters of the nth system.

The previous control problem, the same as the original control problem (8), is intractable in direct analysis. Our goal in this section is to show that the proposed randomized allocation policy ${\pi }^{*}(\overline{\mathcal{M}})$ associated with the fluid-limit parameter $\overline{\mathcal{M}}=(\overline{\lambda },\overline{\mu },\overline{\rho },c,\vartheta )$ (see Section 4.4 for the definition of the policy) is asymptotically optimal in the following sense:

and furthermore,where ${\{{\pi }^n\}}_{n\in \mathbb{N}}$ is an arbitrary sequence of admissible policies, and $\mathcal{C}(\overline{\mathcal{M}})$ is the optimal value of the FCP associated with the fluid-limit parameters $\overline{\mathcal{M}}$ (it is the same as the FCP in Definition 2 with $\mathcal{M}$ replaced by $\overline{\mathcal{M}}$).

In (29) and (30), we consider both orders of the two limits as $T\to \infty$ and $n\to \infty$. To establish (29), we first let $n\to \infty$ to derive a deterministic fluid limit of ${\overline{X}}^n$ under the proposed policy and then let $T\to \infty$ to study the stability of the fluid limit, whereas in the study of (30), we first let $T\to \infty$ to reach the steady state of ${\overline{X}}^n(t)$ (which is a Markov chain under the proposed policy) and then let $n\to \infty$ to derive the fluid limit of the steady states. In particular, the study of (30) yields the ergodicity of the Markov chain ${\overline{X}}^n$ under the proposed policy for each sufficiently large n. The allocation policies satisfying (29) and (30) are thus asymptotically optimal under the long-run average cost criterion as in (29) and the ergodic cost criterion as in (30).

6.1. Asymptotic Optimality of the Proposed Policy

Let ${\overline{r}}_{hi}^{e,*}$ and ${\overline{x}}_i^{e,*}$ be an optimal solution and the corresponding optimal state of the FCP associated with $\overline{\mathcal{M}}.$ Following Section 4.4, we construct the randomized policy ${\pi }^{*}(\overline{\mathcal{M}})$ based on ${\overline{r}}_{hi}^{e,*}$. Thus, ${\pi }^{*}(\overline{\mathcal{M}})$ does not depend on n. We consider ${\pi }^{*}(\overline{\mathcal{M}})$ for each of the nth system. We next present our main results: Theorems 1 and 2. The proofs will be decomposed into various intermediate results shown in Sections 6.2 and 6.3. The complete proofs of both theorems are provided in Appendix B.3.3.

The first result is on the asymptotic optimality of the proposed policy.

Theorem 1.

The proposed policy ${\pi }^{*}(\overline{\mathcal{M}})$ is asymptotically optimal under the long-run average cost criterion as in (29) and the ergodic cost criterion as in (30).

The next theorem establishes the interchange limit theorem for the bipartite matching system under the proposed allocation policy ${\pi }^{*}(\overline{\mathcal{M}})$.

Theorem 2.

Under the proposed policy ${\pi }^{*}(\overline{\mathcal{M}}),\hspace{0.17em}\{{\overline{X}}^n(t);t\ge 0\}$ is a Markov chain for each n, and if there exists $N\in \mathbb{N}$ such that when $n\ge N$, it is irreducible, then for $i\in \mathbb{I},$

$$\underset{t\to \infty }{\lim } \underset{n\to \infty }{\lim } \mathbb{E}[|{\overline{X}}_i^n(t)-{\overline{x}}_i^{e,*}|]=\underset{n\to \infty }{\lim } \underset{t\to \infty }{\lim } \mathbb{E}[|{\overline{X}}_i^n(t)-{\overline{x}}_i^{e,*}|]=0.$$

Furthermore, for $i\in \mathbb{I}$ and $h\in \mathbb{H}(i)$,

Remark 3.

Although the proposed policy ${\pi }^{*}(\overline{\mathcal{M}})$ is independent of n, it is constructed by the fluid-limit parameter $\overline{\mathcal{M}}$. In practice, one needs to identify n and the model parameters ${\mathcal{M}}^n$ to compute $\overline{\mathcal{M}}$, for example, $\overline{\lambda }={\lim }_{n\to \infty }{\lambda }^n/n.$ However, the system scale n may not be easily identified. Instead of considering the fluid-limit parameters $\overline{\mathcal{M}}$, one can construct the proposed policy according to an optimal solution of the FCP associated with the unscaled system parameters. To be more precise, assume that we have the Nth system with N being large but unknown. Under Assumption 2, the FCP associated with ${\mathcal{M}}^N$ can also be reformulated as a simple linear program and admits an optimal solution $r_N^{e,*}$ with the optimal value $\mathcal{C}({\mathcal{M}}^N)$. Now one can show that sufficient conditions in Wets 1985 (proposition 8) hold and by Wets 1985 (theorem 2), the linear program FCP associated with ${\mathcal{M}}^N$ is continuous in its parameters. It follows that ${\lim }_{n\to \infty } \mathcal{C}({\mathcal{M}}^n)/n=\mathcal{C}(\overline{\mathcal{M}})$, which yields

$$\mathcal{C}({\mathcal{M}}^N)\approx N\mathcal{C}(\overline{\mathcal{M}}).$$(31)

Denote by ${\pi }^{N,*}$ the proposed policy according to $r_N^{e,*}$. Combining (29) and (30) with (31), when T is also large, we have

$$C_T^N({\pi }^{N,*};X^N(0),{\mathcal{M}}^N)\approx \mathcal{C}({\mathcal{M}}^N),$$(32)

which demonstrates that the proposed policy ${\pi }^{N,*}$ is a near-optimal policy. However, we may not have $r_N^{e,*}\approx {\overline{r}}^{e,*}$ because the FCP could have multiple optimal solutions.

As mentioned in Section 4.4, the randomized policy ${\pi }^{*}(\overline{\mathcal{M}})$ we propose is not work-conserving. In Corollary 1, we show that the policy is asymptotically work-conserving. For the kth arrival of the type h resource, let ${\overline{Z}}_h^k=({\overline{Z}}_{h0}^k,{\overline{Z}}_{h1}^k,\dots ,{\overline{Z}}_{hI}^k)\prime$ denote the generalized Bernoulli random according to the probability distribution $({\overline{r}}_{h0}^{e,*},{\overline{r}}_{h1}^{e,*},\dots ,{\overline{r}}_{hI}^{e,*})$ (see Section 4.4 for more explanation on the distribution). Then the process of successful matching can be formulated as

$$U_{hi}^n(t)={\displaystyle \sum _{k=1}^{E_h^n(t)}{\overline{Z}}_{hi}^k}{w}_{hi}^k\mathbf{1}\{X_i^n({\nu }_h^{k,n}-)>0\}.$$(33)

Recall that ${\{{\nu }_h^{k,n}\}}_{k=1}^{\infty }$ is the sequence of arrival times of the Poisson arrival process $E_h^n$ of type h resource. Now define for $t\ge 0$,

$${\tilde{U}}_{hi}^n(t)={\displaystyle \sum _{k=1}^{E_h^n(t)}{\overline{Z}}_{hi}^k}{w}_{hi}^k.$$

The quantity ${\tilde{U}}_{hi}^n(t)$ represents the number of type h resource units assigned to customer queue i over the time interval $[0,t]$ assuming the queue is nonempty for each assignment. The difference ${\tilde{U}}_{hi}^n(t)-U_{hi}^n(t)$ gives the number of type h resource units that are assigned to customer queue i and are wasted because of the emptiness of the queue over the time interval $[0,t]$. The following result as a corollary of Theorem 2 shows that the long run average wasted resource is asymptotically negligible in the fluid scaling. The proof can be found in Appendix B.3.3. In Section 7, we numerically explore the convergence behavior of ${\tilde{U}}_{hi}^n(t)-U_{hi}^n(t)$ with respect to n and t (see Section 7 for the related discussion).

Corollary 1.

We have the following interchange limit result for ${\tilde{U}}_{hi}^n(t)-U_{hi}^n(t)$.

$$\underset{n\to \infty }{\lim } \underset{t\to \infty }{\lim } \mathbb{E}\left[\frac{{\tilde{U}}_{hi}^n(t)-U_{hi}^n(t)}{nt}\right]=\underset{t\to \infty }{\lim } \underset{n\to \infty }{\lim } \mathbb{E}\left[\frac{{\tilde{U}}_{hi}^n(t)-U_{hi}^n(t)}{nt}\right]=0.$$(34)

The rest of the section will focus on the proofs of the two main theorems. Section 6.2 focuses on the study of (29). We first derive a deterministic limit, known as the fluid limit, of ${\overline{X}}^n(t)$ as $n\to \infty$ under the proposed policy, and then study the stability property of the fluid limit as $t\to \infty$. In Section 6.3, we show that under the proposed policy, ${\overline{X}}^n(t)$ is a Markov chain admitting a stationary distribution and derive the fluid limit of the stationary distribution as $n\to \infty .$ In the following sections, we use the L² norm $\Vert x\Vert =\sqrt{{\sum }_{i=1}^I{x}_i^2}$ for $x\in {\mathbb{R}}^I.$

6.2. Fluid Limit and Its Stability

We are interested in the asymptotic behavior of the matching system under the proposed policy ${\pi }^{*}(\overline{\mathcal{M}})$ as $n\to \infty .$ To that end, for a given T, we show that the scaled process ${\overline{X}}^n(t)$ under the proposed policy ${\pi }^{*}$ converges to a solution, denoted by $\overline{x}(t)$, of a reflected ODE uniformly on $[0,T]$. Then, the first natural question is: Does this dynamical system has a unique solution? Is ${\overline{x}}^{e,*}$, which is the corresponding optimal state of the FCP, an equilibrium point of $\overline{x}(t)$? The second natural question is: If $\overline{x}(t)$ converges to ${\overline{x}}^{e,*}$ as $t\to \infty$, how fast is the convergence? This is equivalent to study the stability property of $\overline{x}(t).$ The main challenge in addressing these questions is that the dynamical system has a reflection boundary, which creates a type of discontinuity. We provide affirmative answers to these questions by constructing an appropriate Lyapunov function, adopting results in the generalized linear Skorokhod problem and the associated variational inequality problem for an equivalent projected dynamical system. The complete proofs of all results in this section are provided in Appendix B.3.1.

In the first step, we present a law of large number result for the successful matching process under the proposed policy. Recall from (33) that

By constructing proper martingales and applying convergence theorems for martingales, we can show the following Lemma 4.

Lemma 4.

Under the proposed policy ${\pi }^{*}(\overline{\mathcal{M}})$, for any $T\ge 0$ and $i\in \mathbb{I},h\in \mathbb{H}(i)$,

$$\underset{n\to \infty }{\lim } \mathbb{E}\left[\underset{0\le t\le T}{\sup }\left|{\overline{U}}_{hi}^n(t)-a_{hi}{\overline{r}}_{hi}^{e,*}{\overline{\mu }}_h^n{\displaystyle {\int }_0^t\mathbf{1}}\{{\overline{X}}_i^n(\tau )>0\}d\tau \right|\right]=0.$$(35)

The following proposition establishes the fluid limits of the state and control processes under the proposed allocation policy ${\pi }^{*}(\overline{\mathcal{M}}).$

Proposition 4.

Under the proposed policy ${\pi }^{*}(\overline{\mathcal{M}})$, for any T > 0 and $i\in \mathbb{I},h\in \mathbb{H}(i)$,

$$\underset{n\to \infty }{\lim } \mathbb{E}\left[\underset{t\in [0,T]}{\sup }|{\overline{X}}_i^n(t)-{\overline{x}}_i(t)|\right]=0,$$(36)

$$\underset{n\to \infty }{\lim } \mathbb{E}\left[\underset{t\in [0,T]}{\sup }|{\overline{U}}_{hi}^n(t)-{\overline{u}}_{hi}(t)|\right]=0,$$(37)

where

$${\overline{u}}_{hi}(t)=\frac{a_{hi}{\overline{r}}_{hi}^{e,*}{\overline{\mu }}_h}{{\sum }_{\tilde{h}\in \mathbb{H}(i)}{a}_{\tilde{h}i}{\overline{r}}_{\tilde{h}i}^{e,*}{\overline{\mu }}_{\tilde{h}}}\left({\displaystyle \sum _{\tilde{h}\in \mathbb{H}(i)}{a}_{\tilde{h}i}}{\overline{r}}_{\tilde{h}i}^{e,*}{\overline{\mu }}_{\tilde{h}}t-{\overline{y}}_i(t)\right),$$(38)

and $\overline{x}=({\overline{x}}_1,\dots ,{\overline{x}}_I)\prime$ together with $\overline{y}=({\overline{y}}_1,\dots ,{\overline{y}}_I)\prime$ is the unique solution to the following generalized linear Skorokhod problem (SP): For $i\in \mathbb{I},$

$${\overline{x}}_i(t)={\overline{x}}_i(0)+{\overline{\lambda }}_{i}t-{\displaystyle \sum _{h\in \mathbb{H}(i)}{a}_{hi}}{\overline{r}}_{hi}^{e,*}{\overline{\mu }}_{h}t-{\displaystyle {\int }_0^t\left({\displaystyle \sum _{k\in \mathbb{I}\cup \left\{0\right\}}{\overline{\rho }}_{ik}}{\overline{x}}_i(\tau )-{\displaystyle \sum _{l\in \mathbb{I}}{\overline{\rho }}_{li}}{\overline{x}}_l(\tau )\right)}d\tau +{\overline{y}}_i(t),$$(39)

and ${\overline{y}}_i$ satisfies (i) ${\overline{y}}_i(0)=0$, (ii) ${\overline{y}}_i(·)$ is nondecreasing, and (iii) ${\overline{y}}_i(·)$ increases only when ${\overline{x}}_i(·)$ reaches zero, that is, ${\int }_0^{\infty }{\overline{x}}_i(t)d{\overline{y}}_i(t)=0$.

The proof of Proposition 4 follows a standard weak convergence argument. We first observe that $({\overline{X}}^n,{\overline{U}}^n)$ is C-tight and uniformly integrable, and then show that its weak limit satisfies (38) and the generalized linear SP (39).

The next step involves exploring the stability properties of the reflected ODE given in (39). To ease notation, let function $F:{\mathbb{R}}_{+}^I\to {\mathbb{R}}_{+}^I$ be such that for $x\in {\mathbb{R}}_{+}^I$,

where $\overline{P}$ and $\overline{b}$ are defined as $P$ and b in (12) and (13) with $\rho ,\lambda ,\mu$ and r^e replaced by $\overline{\rho },\overline{\lambda },\overline{\mu }$ and ${\overline{r}}^{e,*}$, respectively. Then, the vector representation of (39) is given by

Noting that ${\overline{x}}^{e,*}$ is the corresponding state of the FCP under the optimal solution ${\overline{r}}^{e,*}$, the pair $({\overline{x}}^{e,*},{\overline{r}}^{e,*})$ satisfies Constraint (11b), that is, $F({\overline{x}}^{e,*})=0.$ Consequently, ${\overline{x}}^{e,*}$ is an equilibrium point of the reflected ODE $\overline{x}(t)$. The following proposition establishes the uniqueness of the equilibrium point ${\overline{x}}^{e,*}$ as well as its stability.

Proposition 5.

The point ${\overline{x}}^{e,*}$ is the unique equilibrium point of the reflected ODE $\overline{x}(t)$, and it is globally exponentially stable; that is, there exist constants B > 0 and $\kappa >0$ such that

$$\Vert \overline{x}(t)-{\overline{x}}^{e,*}\Vert \le B{e}^{-\kappa t},\hspace{0.17em}t\ge 0.$$(42)

Furthermore,

$$\underset{t\to \infty }{\lim }\frac{\overline{y}(t)}{t}=0.$$(43)

Remark 4.

We provide here the main proof ideas of Proposition 5.

• (i) The proof of the uniqueness of the equilibrium point ${\overline{x}}^{e,*}$ in Proposition 5 relies on the observation that the reflected ODE $\overline{x}(t)$ is equivalent to the projected dynamical system (PDS) associated with ${\mathbb{R}}_{+}^I$ and F, and the equilibrium points of the reflected ODE coincide with the solutions of the variational inequality (VI) problem associated with ${\mathbb{R}}_{+}^I$ and F (Dupuis and Nagurney 1993, Nagurney and Zhang 2012). The rigorous definitions of the PDS and VI problem can be found in the proof of Proposition 5 in Appendix B.3.1.

• (ii) A key tool for the proof of the globally exponential stability in Proposition 5 is an appropriate Lyapunov function. For the nonsingular M-matrix $\overline{P}$, there exists a positive diagonal matrix D such that $\overline{P}\prime D+D\overline{P}$ is positive definite (Plemmons 1977). The Lyapunov function is defined as

  $$V(x)=\frac{1}{2}(x-{\overline{x}}^{e,*})\prime D(x-{\overline{x}}^{e,*})=\frac{1}{2}{\displaystyle \sum _{i=1}^I{D}_{ii}}{(x_i-{\overline{x}}_i^{e,*})}^2,\hspace{0.17em}x\in {\mathbb{R}}_{+}^I,$$(44)
  which measures a weighted distance from the point x to the equilibrium point ${\overline{x}}^{e,*}.$

The following corollary follows from Propositions 4 and 5.

Corollary 2.

Under the proposed policy ${\pi }^{*}(\overline{\mathcal{M}})$, for $i\in \mathbb{I}$,

$$\underset{t\to \infty }{\lim } \underset{n\to \infty }{\lim } \mathbb{E}[|{\overline{X}}_i^n(t)-{\overline{x}}_i^{e,*}|]=0,$$(45)

and for $h\in \mathbb{H}(i)$,

$$\underset{t\to \infty }{\lim } \underset{n\to \infty }{\lim } \mathbb{E}[|{\overline{U}}_{hi}^n(t)/t-{\overline{\mu }}_h{a}_{hi}{\overline{r}}_{hi}^{e,*}|]=0.$$(46)

6.3. Steady-State Analysis and Its Fluid Limit

Under the proposed allocation policy ${\pi }^{*}(\overline{\mathcal{M}})$, the state process $\{X^n(t);t\ge 0\}$ in the nth system is a Markov chain with the following generator ${\mathcal{L}}^n:\mathcal{M}({\mathbb{Z}}_{+}^I,\mathbb{R})\to \mathcal{M}({\mathbb{Z}}_{+}^I,\mathbb{R})$, where $\mathcal{M}({\mathbb{Z}}_{+}^I,\mathbb{R})$ is the set of measurable functions from ${\mathbb{Z}}_{+}^I$ to $\mathbb{R}$. For $g\in \mathcal{M}({\mathbb{Z}}_{+}^I,\mathbb{R})$ and $x\in {\mathbb{Z}}_{+}^I$,

where the three terms on the right-hand side of (47) correspond to external arrivals, successful matches or abandonment, and internal class changes, respectively.

It is not clear upfront whether the Markov chain $\{X^n(t);t\ge 0\}$ is irreducible because the transition rates ${\rho }_{ij}^n$ can be zero among some customer queues. Nevertheless, we can consider the limiting behavior of the chain.

Proposition 6.

Under the proposed policy ${\pi }^{*}(\overline{\mathcal{M}})$, for $i\in \mathbb{I}$,

$$\underset{n\to \infty }{\lim } \underset{t\to \infty }{\text{lim sup}} \mathbb{E}\left[|{\overline{X}}_i^n(t)-{\overline{x}}_i^{e,*}|\right]=0,$$(48)

and for $h\in \mathbb{H}(i)$,

$$\underset{n\to \infty }{\lim } \underset{t\to \infty }{\lim } \mathbb{E}\left[|{\overline{U}}_{hi}^n(t)/t-{\overline{\mu }}_h{a}_{hi}{\overline{r}}_{hi}^{e,*}|\right]=0.$$(49)

When the chain is irreducible, it can be shown to be ergodic with a unique stationary distribution.

Proposition 7.

Under the proposed policy ${\pi }^{*}(\overline{\mathcal{M}})$, there exists an $N\in \mathbb{N}$ such that when $n\ge N$, if the Markov chain $\{{\overline{X}}^n(t);t\ge 0\}$ is irreducible, it is ergodic with a unique stationary distribution.

Remark 5.

The proofs of the previous two propositions rely on constructing a similar Lyapunov function (see Appendix B.3.2 for the complete proofs). We consider the Lyapunov function defined in (44) and modify it for $X^n(t)$ in the nth system. Define the matrix $P^n$ in the same way as $P$ in (12) with ρ replaced by ρⁿ and r replaced by ${\overline{r}}^{e,*}$. Under Assumption 2, for large enough n, the matrix $P^n$ satisfies Assumption 1 and Lemma 1 still holds for $P^n$. Then, there exists a positive diagonal matrix Dⁿ such that $D^n{P}^n+(P^n)\prime D^n$ is positive definite. Define the following Lyapunov function for any given $x\in {\mathbb{Z}}_{+}^I$,

$$V^n(x)=(x-n{\overline{x}}^{e,*})\prime D^n(x-n{\overline{x}}^{e,*})={\displaystyle \sum _{i=1}^I{D}_{ii}^n}{(x_i-n{\overline{x}}_i^{e,*})}^2.$$(50)

A crucial step is to study ${\mathcal{L}}^n(V^n(x))$, which represents the rate of change of the weighted distance from x (a value of $X^n(t)$) to $n{\overline{x}}^{e,*}$ and show that it decreases linearly in $V^n(x)$ (see Lemma B.1 in the Appendix B.3.2).

7. Numerical Experiments

In this section, we provide numerical evidence for our results. We simulate a stochastic matching system and observe the performance of our proposed policy. In particular, we consider a heart transplant system with I = 4 queues for patients and H = 2 organ types. This categorization is inspired by the fact that health is a major factor for pre- and posttransplant survival for heart transplant and UNOS used four categories of “1A” (class 1), “1B” (class 2), “2” (class 3), and “Inactive” (class 4) for patient health group, where 1A denotes the sickest, 1B is less severe than 1A, 2 is less severe than 1B, and Inactive patients are not suitable for transplant (OPTN 2021). For organ type, donor age is crucial for posttransplant survival, and we consider donors with age [18,50) as type 1 and [50, 80] as type 2.

At each time $t=1,2,\dots ,T,$ the following sequence of events takes place in the simulation. First, for each patient queue i, a random number from a Poisson distribution with parameter ${\lambda }_i^n=n{\lambda }_i+\sqrt{n}$ is generated and patients are added to the corresponding queue. For each organ type h, a random number from a Poisson distribution with parameter ${\mu }_h^n=n{\mu }_h+\sqrt{n}$ is generated as the number of arrived organs of type h. For each arrived organ with type h, based on the given policy we decide which patient queue it will be matched to. Let i be that patient queue class. If patient queue i is empty, the organ is discarded. Otherwise, we offer the organ to the patient in the head of the queue, which is consistent with UNOS practice. We generate a uniform random number in $[0,1]$ and compare it to a_hi to decide whether the organ is accepted or not. On success, the patient leaves the system. If the patient declines the organ, it is discarded, and the patient stays in queue. Third, we decide on the death (abandonment) and class change for patients. To that end, for each patient in the system we roll an $(I+1)$-dimensional die with probabilities corresponding to abandonment and class change, that is, ρ_ij for all $j=0,1,\dots ,I$, the result of which determines what will happen to the patient: Staying in the queue, abandonment, or moving to another queue.

We use Hasankhani and Khademi (2017) to estimate the parameters of the model. We consider each period as a month. The initial number of patients in each queue is generated randomly according to a discrete uniform distribution between 200 and 250. The arrival rate of patient classes is approximately $\lambda =(60,120,60,60)$ patients per month and that of organs is approximately $\mu =(60,90)$ organs per month. The death rate for patient classes is $(0.0252,0.00981,0.00441,0.05853)$ patients per month. The estimate of class change rates is shown in Table 2. To estimate the values for matching an organ to a patient, we use posttransplant life months. In particular, for type 1 organ, the posttransplant life months of four patient classes are estimated as $(249,324.2,355.5,0)$, and for type 2 organ those are estimated as $(218.3,255.1,327,0)$. For Inactive patients, we set posttransplant life months to be zero because they do not receive organs while in that state. For the holding costs in queue, we consider pretransplant costs while waiting on the wait list. Specifically, based on the results of Evans (1987) and adjustment for the inflation rate, we estimate a value of $319,010 per year for the holding cost for each patient class. However, to be consistent with match values, which are based on life months, we convert this yearly cost to life months. To that end, we note that in cost-effective analysis in healthcare, each life year is roughly worth $100,000 (Goodman 2016). Therefore, the holding cost for each patient class will be around 3.2 life months per month. To estimate the abandonment (death) costs, we use the expected life months gained due to transplantation, which are 194 months for class 1A, 187.7 months for class 1B, 114.5 months for class 2, and 0 months for Inactive patients. We assume that two objectives of minimizing cost and maximizing value have the same weight and set ${\omega }_1=0.5$ and ${\omega }_2=0.5$. For this system, ${\pi }_{11}^{\ast }=0,{\pi }_{12}^{\ast }=0,{\pi }_{13}^{\ast }=1,{\pi }_{14}^{\ast }=0,{\pi }_{21}^{\ast }=1,{\pi }_{22}^{\ast }=0,{\pi }_{23}^{\ast }=0,{\pi }_{24}^{\ast }=0$ and $x_1^{e,*}=577.705,\hspace{0.17em}{x}_2^{e,*}=321.687,\hspace{0.17em}{x}_3^{e,*}=295.021$ and $x_4^{e,*}=2345.55$. The value of the lower bound, the optimal objective function, is $\mathcal{C}(\mathcal{M})=-12,233.1$.

Table 2. Estimates of Patient Class Change Rates

We explore the convergence behavior with respect to n and T. To that end, we set three values for T, that is, T = 500, T = 1,000, and T = 3,000 and then change n from 1 to 201 with increments of 10, that is, $n=1,11,\dots ,201$. We report the average numbers for 30 simulation replications. Figure 3 shows the value of the scaled cost and lower bound. The result for T = 500 is denoted by a dashed red curve, for T = 1,000 by a dotted brown curve, and for T = 3,000 by a solid black curve. As can be seen, the objective of the nth system stabilizes after n = 50 for all three cases for T. For T = 500, the scaled cost converges to −11,981, and for T = 1,000, it converges to −12,142. When T = 3,000, it converges to −12,231.5, which is roughly equal to the lower bound optimal value $\mathcal{C}(\mathcal{M})=-12,233.1$.

Furthermore, recall that the proposed policy will discard an organ upon its arrival if the result of the randomization is an empty queue. For example, in our numerical result, ${\pi }_{13}^{\ast }=1$ and if an organ of type 1 arrives and queue 3 is empty, it will be wasted. In this section, we numerically find ${\sum }_{h\in \mathbb{H}}{\sum }_{i\in \mathbb{I}}({\tilde{U}}_{hi}^n(T)-U_{hi}^n(T))/(nT)$ in our simulation and present it in Figure 4, which by Corollary 1 is asymptotically negligible. In particular, Figure 4 shows that the average (over simulation runs) of the scaled number of organs wasted because the corresponding queue is empty on organ arrival. For T = 500, T = 1,000, and T = 3,000, the scaled wasted organs stabilize at 0.052, 0.021, and 0.007, respectively. The quantity ${\sum }_{h\in \mathbb{H}}{\sum }_{i\in \mathbb{I}}({\tilde{U}}_{hi}^n(T)-U_{hi}^n(T))/n$ roughly represents the number of organs that are discarded because of the emptiness of the assigned patient queues over the time interval $[0,T]$. Also recall that the total arrival rate of the two types of organs is $60+90=150$ per month. Therefore, for T = 500, there are $0.052\times 500=26$ organs wasted during 500 months out of roughly 150 × 500 = 75,000 total organs. Such wastage is indeed asymptotically negligible.

In addition, we assume that if an organ is declined by a patient, it will be discarded. Next, we construct a policy $\widehat{\pi }$ that assigns organs to queues as ${\pi }^{\ast }$ does, but if the patient in the head of the queue declined the organ, the policy offers the organ to the next patient in that queue and continues this process until the organ is accepted by a patient or all the patients in the queue declined it. Our simulation results for T = 3,000 and n = 201, where the objective value is essentially equal to the lower bound, shows that the improvement of policy $\widehat{\pi }$ over ${\pi }^{*}$ is around 6%. This 6% improvement is notable because if a declined organ is eventually accepted, it will improve the objective function by increasing the life years instead of having a waiting cost. Under the policy $\widehat{\pi }$, the acceptance probability for each organ becomes larger because it can be offered multiple times. See Section 8 for more discussion on the acceptance probabilities. In fact, $\widehat{\pi }$ does not fall into the set of admissible policies we define for the contact acceptance probability.

8. Discussion

In this section, we discuss some major assumptions in the model and the implications of their relaxation. First, we assume that resources will not queue; for example, in the transplant application, if an organ arrives and finds all queues empty, it will be wasted. This is a simplifying assumption, but it is not restrictive in overloaded systems, that is, when the demand significantly exceeds supply. We make this argument rigorous in the following way: The scaled overall allocation process for a resource converges to the arrival process of that resource type. To that end, the first step is to observe the following result.

Lemma 5.

If $x_i^{e,*}>0$ in (11), ${\sum }_{k\in \mathbb{I}(h)}{r}_{hk}^{e,*}=1$ for all $h\in \mathbb{H}(i)$.

It implies that if customer queue i is positive in equilibrium, all the resources that supply patient queue i are exhausted. Let $\overline{I}≔\{i\in \mathbb{I}:x_i^{e,*}>0\}$. We call the system “overloaded” if ${\cup }_{i\in \overline{I}}\mathbb{H}(i)=\mathbb{H}$; that is, there are enough positive queues in equilibrium such that all resource types are exhausted. Therefore, we have the following result.

Corollary 3.

If the system is overloaded in the sense mentioned previously, for each $h\in \mathbb{H}$,

$$\underset{t\to \infty }{\lim } \underset{n\to \infty }{\lim } \mathbb{E}\left[\left|{\displaystyle \sum _{i\in \mathbb{I}(h)}{\overline{V}}_{hi}^n}(t)/t-{\overline{E}}_h^n(t)/t\right|\right]=\underset{n\to \infty }{\lim } \underset{t\to \infty }{\lim } \mathbb{E}\left[\left|{\displaystyle \sum _{i\in \mathbb{I}(h)}{\overline{V}}_{hi}^n}(t)/t-{\overline{E}}_h^n(t)/t\right|\right]=0.$$

The proofs of both results can be found in Appendix B.4. Second, we assume that if a resource is declined by a customer, it will be wasted. In organ transplant systems, however, if a patient declines an offered organ, it will be offered to the next patient in the waiting list based on patient scores. However, formulating the general allocation policy is challenging. In fact, if the patient in the head of the queue declines the organ, the policy should check whether there are other patients in that queue. If there are, it should check whether this patient accepts the organ or not by considering another Bernoulli random variable. This process continues until there are no more tried patients or the number of feasible offers are exhausted. If the process has to continue and all patients of the current queue have been tried, the policy must decide what queue is next. Therefore, the policy must completely characterize the path for organ offer, which makes the analysis challenging. Current fluid models in the literature approximate this process by considering the overall probability of organ acceptance. Specifically, let N denote the maximum number of times an organ can be offered. Recall that a_hi is the probability that a class i patient accepts an organ type h. Thus, assuming queue i has at least N patients, the probability of eventual organ acceptance is $1-{(1-a_{hi})}^N$, which is used instead of a_hi in Equation (11b) (Akan et al. 2012). Nonetheless, our proposed model applies to organs with short cold ischemic time. For example, unlike a kidney with a cold ischemic time of 48 hours, a heart only has a cold ischemic time of 4 hours, making it difficult to reoffer it after a decline. In our numerical results, we consider a policy $\widehat{\pi }$ that assigns organs to patient classes as ${\pi }^{\ast }$, but when the head of the queue patient declines the offered organ, it will offer it to the next patient in line until the organ is accepted or the organ is offered to all patients in the queue and declined. The probability of organ acceptance becomes $1-{(1-a_{hi})}^{X_i(t)}$ and is state dependent. Our results show that the improvement in the objective function of $\widehat{\pi }$ over ${\pi }^{\ast }$ is around 6% for large n and T.

Third, in the model, we assume that there is no cost for resource wastage. The total wastage for resource type h up to time t is $E_h(t)-{\sum }_{i\in \mathbb{I}(h)}{U}_{hi}(t)$. If the wastage cost of one unit of resource type h is $c_h^w$, the average wastage cost will be $T^{-1}{\sum }_{h\in \mathbb{H}}\mathbb{E}[c_h^w(E_h(T)-{\sum }_{i\in \mathbb{I}(h)}{U}_{hi}(T))]$. This addition will only add a corresponding term in the objective function and the constraints will not change. Because we have already showed the asymptotic results for $U_{hi}(t)$, all the results will hold by adding this extra term.

Finally, our proposed policy is randomized, and on arrival of a resource, a queue is determined randomly for assignment. If the queue is nonempty, the resource is assigned to the head of the queue; otherwise, the resource is wasted. In Corollary 1, we show that this randomized policy is asymptotically work-conserving. In our numerical example in Section 7, we show that the impact of nonconserving property becomes negligible for large n and T.

9. Conclusion and Future Work

We studied a bipartite matching system where customers of different classes and resources of different types arrive and need to be matched. Customers will join a corresponding queue on arrival and may change their queue or abandon the system probabilistically. Resources on arrival will be matched to customers where a match may be unsuccessful. Resources will be wasted if the match is unsuccessful or no customer is in queues. The DM will incur a cost due to customer waiting and abandonment and will accrue a reward for successful matches. We constructed a corresponding fluid control problem, which is an LP, and proposed a randomized policy based on its solution for the original problem. We showed that under the fluid scaling the proposed policy is asymptotically optimal and interchange of steady state and fluid limit holds. We also investigated the structure of the proposed policy under two X models.

There are some natural paths for future work. First, we assumed that resources must be assigned on arrival and cannot be kept in inventory. Although this assumption may be appropriate for overloaded queues (Corollary 3) like transplant systems, in underloaded queues, these resources may be kept in queues to model matching systems more realistically. Second, a match will be successful in the model based on a probability distribution. However, customers may be strategic in deciding to accept or decline a resource by solving an optimal stopping problem. The equilibrium analysis of this extension will provide more insight about this feature of the problem. Third, we assumed that the parameters of the model are known. However, some of the model parameters may be unknown but can be learned over time by sampling. The analysis of regret for such matching systems can be an interesting topic for future investigation. Last, we used a fluid-based approach to analyze the model, but considering a diffusion-based analysis will provide further realism.