# Stochastic non-bipartite matching models and order-independent loss
queues111Author version of the paper available at
https://doi.org/10.1080/15326349.2021.1962352.

Céline Comte  Eindhoven University of Technology, The Netherlands
<EMAIL_ADDRESS>
###### Abstract

The problem of appropriately matching items subject to compatibility
constraints arises in a number of important applications. While most of the
literature on matching theory focuses on a static setting with a fixed number
of items, several recent works incorporated time by considering a stochastic
model in which items of different classes arrive according to independent
Poisson processes and assignment constraints are described by an undirected
non-bipartite graph on the classes. In this paper, we prove that the Markov
process associated with this model has the same transition diagram as in a
product-form queueing model called an order-independent loss queue. This
allows us to adapt existing results on order-independent (loss) queues to
stochastic matching models and, in particular, to derive closed-form
expressions for several performance metrics, like the waiting probability or
the mean matching time, that can be implemented using dynamic programming.
Both these formulas and the numerical results that they allow us to derive are
used to gain insight into the impact of parameters on performance. In
particular, we characterize performance in a so-called heavy-traffic regime in
which the number of items of a subset of the classes goes to infinity while
items of other classes become scarce.
Keywords: Stochastic matching model, order-independent queue, product-form
stationary distribution, dynamic programming, heavy-traffic regime.

##  1 Introduction

Matching items with one another in such a way that an individual item’s
preferences are met is a well-known problem in mathematics, computer science,
and economics. Classical applications include assigning users to servers in
distributed computing systems, joining components in assembly systems,
matching passengers to drivers in ride-sharing applications, and assigning
questions to experts in question-and-answer websites.

1234 Figure 1: An undirected non-bipartite compatibility graph.

While most of the literature on matching theory focuses on a _static_ setting
in which a fixed set of items has to be matched, applications to modern large-
scale service systems require that we also consider the time dimension. In
assembly systems for instance, components of different types arrive at random
instants as they are manufactured, and the primary objective is to have
sufficient balance between components to maximize throughput while also
minimizing the number of components to be stored. This observation gave rise
to models that can be seen as stochastic generalizations of classical matching
problems. In these stochastic matching models, items of different classes
arrive according to independent Poisson processes. Compatibility constraints
between items are described by an undirected graph on the classes, so that
there is an edge between two classes if items of these classes can be matched
with one another. In the example of Figure 1, class-$3$ items can be matched
with items of classes $1$, $2$ and $4$, and items of classes $1$ and $2$ can
also be matched with one another. A _matching policy_ is a decision rule that
specifies, whenever an item arrives, to which compatible waiting unmatched
item, if any, it is matched. The primary objective of a matching policy is to
make the system _stable_ in the sense that the stochastic process describing
the evolution of the number of unmatched items over time is ergodic. The
secondary objective is to optimize performance metrics like the mean matching
time, defined as the average amount of time between the arrival of an item and
its matching with another item.

Two variants of the stochastic matching model have been studied in the
literature. The stochastic _bipartite_ matching model was introduced in [11]
and further studied in [3, 9, 1, 2]. As the name suggests, this model assumes
that the compatibility graph is bipartite. One can verify that such a model is
always unstable if items arrive one by one at random instants (as the
corresponding Markov process is either transient or null recurrent). Stability
in this model is made possible by imposing that items always arrive in pairs,
so that the classes of items in a pair belong to the two parts of the graph.
The stochastic _non-bipartite_ matching model, which we consider in this
paper, was introduced in [20] and further studied in [10, 21, 4]. In this
model, items arrive one at a time, and stability is made possible by imposing
the presence of odd cycles in the compatibility graph. Mairesse and Moyal [20]
consider matching policies that are _admissible_ in the sense that the
matching decision is based solely on the class of the incoming item and the
sequence, in order of arrival, of classes of unmatched items. This work
characterizes the maximum stability region, that is, the set of vectors of
per-class arrival rates under which there exists an admissible policy that
makes the system stable. The focus of [21, 10, 4] is on an admissible policy
called _first-come-first-matched_ ; this is also our focus. As the name
suggests, each incoming item is matched with the compatible item that has been
waiting the longest, if any. In addition to being perceived as fair, this
policy has the advantage of maximizing the stability region and leading to
tractable results, as we will develop in this paper. The rationale behind this
policy, which gives an intuition for its maximum stability, is as follows: if
an item has been waiting longer than another, it is likely that this item is
compatible with classes that are relatively scarcer, so that matching this
item if an opportunity arises is a good heuristic to preserve stability. It is
shown in [21] that this matching policy is indeed maximally stable and leads
to a product-form stationary distribution. This work also derives a closed-
form expression for the normalization constant of this stationary
distribution. A similar closed-form expression for the mean matching time is
proposed in [10], which applies this result to study the impact of the
compatibility graph on performance. The authors observe that adding edges
sometimes has a negative impact on performance, which is akin to Braess’s
paradox in road networks. Lastly, the recent work [4] adapts some of the above
results to a variant of the model in which the items of a given class can also
be matched with one another.

Several recent papers [3, 1, 2, 16] have pointed out the similarity between
the stationary distribution of stochastic matching models under this first-
come-first-matched policy and that of order-independent queues [5], a product-
form queueing model that recently gained momentum in the queueing-theory
community. Our first main contribution consists of formally proving that a
stochastic non-bipartite matching model is an order-independent _loss_ queue,
a loss variant of order-independent queues introduced in [6]. This allows us
to adapt known results on order-independent queues to stochastic non-bipartite
matching models, and in particular to provide simpler proofs for the product-
form and stability results derived in [21]. The relation with order-
independent loss queues also allows us to extend these results to several
variants of the model, some of which were already considered in the
literature. Our second main contribution consists of closed-form expressions
for several performance metrics like the waiting probability and the mean
matching time. Some of these expressions can be seen as recursive variants of
those derived in [21, 10], and are adapted from the works [22, 14, 12] which
focus on order-independent queues and related queueing models. The recursive
form of these expressions allows us to avoid duplicate calculations by using
dynamic programming, which significantly reduces the complexity of the
calculations. In addition to their numerical applications, these formulas
allow us to gain intuition on the impact of the parameters on performance, and
in particular to formalize what it means to have a _balanced_ system. Along
the same lines, our third and last contribution is a performance analysis in a
scaling regime, called _heavy traffic_ by analogy with the scaling regime of
the same name in queueing theory, in which the vector of per-class arrival
rates tends to a boundary of the stability region. This result can be seen as
a generalization of the heavy-traffic result of [12], which focuses on order-
independent queues, although the conclusion is different and illustrates the
subtle difference between stochastic matching models and conventional queueing
models.

The paper is organized as follows. Section 2 describes a continuous-time
variant of the stochastic non-bipartite matching model proposed in [20] and
introduces useful notation. In Section 3.1, we prove that this stochastic
matching model is an order-independent loss queue. This result is applied in
the rest of Section 3 and in Section 4 to translate known results for order-
independent queues to the stochastic matching model and to generalize them. In
particular, Sections 3.2 and 3.3 give simpler proofs of the product-form
result and stability condition of [21], while in Section 4 we derive closed-
form expressions for several performance metrics. These results are applied in
Section 5 to gain insight into the impact of parameters on performance. More
specifically, we propose several heuristics to minimize the mean matching time
and study what happens when part of the system becomes unstable. Numerical
results in Section 6 allow us to gain further insight into the dynamics of
stochastic matching models. Section 7 concludes the paper.

##  2 Stochastic non-bipartite matching model

We first define a continuous-time variant of the stochastic non-bipartite
matching model introduced in [20].

###  2.1 Continuous-time model

Let ${\mathcal{V}}=\\{1,2,\ldots,N\\}$ denote a finite set of item classes and
consider an undirected connected non-bipartite graph without loops with vertex
set ${\mathcal{V}}$. This graph will be called the _compatibility graph_ of
the matching model because it will eventually describe the matching
compatibilities between items. An example is shown in Figure 1. For each
$i,j\in{\mathcal{V}}$, we write $i\sim j$ if there is an edge between classes
$i$ and $j$ in the compatibility graph and $i\nsim j$ otherwise. For each
$i\in{\mathcal{V}}$, we also let ${\mathcal{E}}_{i}\subseteq{\mathcal{V}}$
denote the set of neighbors of class $i$ in the compatibility graph. With a
slight abuse of notation, for each set ${\mathcal{A}}\subseteq{\mathcal{V}}$
of classes, we also let
${\mathcal{E}}({\mathcal{A}})=\bigcup_{i\in{\mathcal{A}}}{\mathcal{E}}_{i}$
denote the set of classes that are neighbors of at least one class in
${\mathcal{A}}$. Our assumption that the compatibility graph is non-bipartite
is not necessary for the soundness of the model, but we will see in Section
3.3 that it is required for stability.

For each $i\in{\mathcal{V}}$, class-$i$ items enter the system according to an
independent Poisson process with rate $\alpha_{i}>0$. As we will see in
Section 3.2, we can (and will) assume without loss of generality that the
vector $\alpha=(\alpha_{1},\alpha_{2},\ldots,\alpha_{N})$ is normalized in the
sense that $\sum_{i\in{\mathcal{V}}}\alpha_{i}=1$. For each subset
${\mathcal{A}}\subseteq{\mathcal{V}}$ of classes, we also let
$\alpha({\mathcal{A}})=\sum_{i\in{\mathcal{A}}}\alpha_{i}$ denote the overall
arrival rate of the classes in ${\mathcal{A}}$. All unmatched items are queued
in a buffer in their arrival order. In Figure 2 for instance, unmatched items
are ordered from the oldest on the left to the newest on the right, and the
number written on each item represents its class. Each incoming item is
matched with an item of a compatible class present in the buffer, if any, in
which case both items disappear immediately; otherwise, the incoming item is
added at the end of the buffer. If an incoming item finds several compatible
items in the buffer, it is matched with the compatible item that has been in
the buffer the longest. This matching policy is called _first-come-first-
matched_ and was studied in [20, 21, 10, 4]. Note that this matching policy
can be applied with a more decentralized approach in which each item is only
aware of the arrival order of its _compatible_ items. Such a decentralized
approach leads to the same dynamics and therefore to the same performance
measures.

Buffer in state $c=(4,4,1,4,1)$441412New item Figure 2: Unmatched items are
ordered in the buffer from the oldest item on the left to the newest on the
right. In particular, in the state $c=(4,4,1,4,1)$ depicted in the picture,
the oldest item is of class $4$ and the newest is of class $1$. With the
compatibility graph of Figure 1, if a class-2 item arrives while the system is
in this state, this item scans the buffer from left to right until it finds a
compatible item, and is therefore matched with the oldest class-1 item. The
new system state after this transition is $d=(4,4,4,1)$.

###  2.2 Markov process

We now define a Markov process that describes the evolution of the continuous-
time stochastic matching model that we have just introduced.

#### Markovian state

We describe the system state with the sequence of unmatched item classes
present in the buffer. More specifically, we consider the sequence
$c=(c_{1},\ldots,c_{n})$, where $n$ is the number of items in the buffer and
$c_{p}$ is the class of the $p$-th oldest item, for each
$p\in\\{1,\ldots,n\\}$. In particular, $c_{1}$ is the class of the item that
has been in the buffer the longest. Figure 2 shows a possible buffer state
associated with the compatibility graph of Figure 1, with the newest items on
the left. The corresponding state descriptor is $c=(4,4,1,4,1)$. We assume
that the state is initially empty, with $n=0$, in which case we write
$c=\varnothing$. The assumption that each class of items arrives according to
an independent Poisson process guarantees that the stochastic process defined
by the evolution of this state descriptor over time has the Markov property.
When the system is in state $c=(c_{1},\ldots,c_{n})$ and a class-$i$ item
arrives, the new system state is $(c_{1},\ldots,c_{n},i)$ if $c_{p}\nsim i$
for each $p\in\\{1,\ldots,n\\}$ and
$(c_{1},\ldots,c_{q-1},c_{q+1},\ldots,c_{n})$, where
$q=\min\\{p\in\\{1,\ldots,n\\}:c_{p}\sim i\\}$, otherwise. The overall
departure rate from each state is $\sum_{i\in{\mathcal{V}}}\alpha_{i}=1$.

#### State space

The system state $c=(c_{1},\ldots,c_{n})$ belongs to the set
${\mathcal{V}}^{*}$ made of the finite sequences over the alphabet
${\mathcal{V}}$, but the matching policy imposes additional restrictions on
the form of this sequence. More specifically, the buffer cannot contain
customers of classes $i,j\in{\mathcal{V}}$ such that $i\sim j$, as the newest
of the two items would necessarily have been matched with the oldest (or with
an older compatible item) upon arrival. In Figure 2 for instance, an incoming
class-$2$ item would be matched with the oldest class-$1$ item, so that items
of classes $1$ and $2$ cannot be in the buffer at the same time. Therefore, in
general, the state space of the Markov process defined by the system state is
a strict subset of ${\mathcal{V}}^{*}$ which we denote by ${\mathcal{C}}$. To
better describe the structure of this state space, additional notation is
introduced in the next paragraph.

A nonempty set ${\mathcal{I}}\subseteq{\mathcal{V}}$ is called an _independent
set_ (of the compatibility graph) if $i\nsim j$ for each
$i,j\in{\mathcal{I}}$. In other words, the set ${\mathcal{I}}$ is independent
if the intersection of this set with the set ${\mathcal{E}}({\mathcal{I}})$ of
its neighbors is empty. The set of all independent sets is denoted by
${\mathbb{I}}$. As an example, the set of independent sets of the
compatibility graph of Figure 1 is
${\mathbb{I}}=\\{\\{1\\},\\{2\\},\\{3\\},\\{4\\},\\{1,4\\},\\{2,4\\}\\}$. In
general, if a set ${\mathcal{I}}\subseteq{\mathcal{V}}$ is an independent set,
then any nonempty subset of ${\mathcal{I}}$ is also an independent set. For
convenience, we also let ${\mathbb{I}}_{0}={\mathbb{I}}\cup\\{\emptyset\\}$
denote the set of independent sets completed with the empty set.

For each ${\mathcal{I}}\in{\mathbb{I}}_{0}$, we let
${\mathcal{C}}_{\mathcal{I}}$ denote the set of words in ${\mathcal{V}}^{*}$
that contain exactly the classes in ${\mathcal{I}}$. Equivalently, if
${\mathcal{V}}(c)\subseteq{\mathcal{V}}$ denotes the set of item classes
present in the word $c\in{\mathcal{V}}^{*}$, we have
$c\in{\mathcal{C}}_{\mathcal{I}}$ if and only if
${\mathcal{V}}(c)={\mathcal{I}}$. Observe that ${\mathcal{C}}_{\mathcal{I}}$
is a strict subset of ${\mathcal{I}}^{*}$ in general, as words in
${\mathcal{I}}^{*}$ need not contain _all_ classes in ${\mathcal{I}}$. In the
special case where ${\mathcal{I}}=\emptyset$, the set
${\mathcal{C}}_{\mathcal{I}}$ contains only the empty state $\varnothing$.
With this notation, the state space of the Markov process defined in the
previous paragraph can be partitioned as follows:

$\displaystyle{\mathcal{C}}=\bigcup_{{\mathcal{I}}\in{\mathbb{I}}_{0}}{\mathcal{C}}_{\mathcal{I}}.$
(1)

In particular, the set of item classes present in a feasible state of the
matching model is an independent set.

######  Remark.

The stochastic non-bipartite matching model of [20, 21, 10, 4] works in the
same way as the one presented above, except that time is slotted and there is
exactly one arrival during each time slot. More specifically, the classes of
incoming items during different time slots are independent and identically
distributed and, for each $i\in{\mathcal{V}}$, $\alpha_{i}$ is the probability
that an incoming item is of class $i$. One can verify that the (discrete-time)
Markov chain associated with the state of this discrete-time stochastic
matching model is the jump chain of the Markov process defined above. Since
the departure rate from each state in the Markov process is
$\sum_{i\in{\mathcal{V}}}\alpha_{i}=1$, inspection of the balance equations
reveals that the Markov chain and the Markov process have the same stationary
measures. Consequently, the results in [21, Theorem 1], derived for the
discrete-time stochastic matching model, also apply to the continuous-time
stochastic matching model defined above. These results will be recalled in
Sections 3.2 and 3.3. For simplicity, the continuous-time stochastic non-
bipartite matching model introduced in Section 2.1 will be called the
_stochastic matching model_ in the remainder.

##  3 Product-form queueing model

In Section 3.1, we prove that the stochastic matching model of Section 2.1 is
an instance of a queueing model, called an _order-independent loss queue_ [6],
that is known to have a product-form stationary distribution. We then identify
several extensions of the stochastic matching model that can also be cast as
order-independent loss queues. In Sections 3.2 and 3.3, we use this
observation to provide simpler proofs for two results from the literature on
stochastic matching models. The reader who is more interested in understanding
the long-term performance of the stochastic matching model can skip Section
3.1 and move directly to Section 3.2.

###  3.1 Order-independent loss queue

Our definition of order-independent loss queues, given in Definition 1 below,
differs in spirit from that of [6, Section 1] in that conditions are given
directly in terms of the associated Markov process, rather than in terms of
the queueing system itself. In particular, although the name _loss_ usually
entails rejecting customers, here this manifests itself via the fact that the
state space ${\mathcal{C}}$ may be a strict subset of ${\mathcal{V}}^{*}$.
This definition happens to be more convenient to show the connection with the
stochastic matching model of Section 2.1, and preserves all the properties of
the order-independent loss queues defined in [6]. We also make a few
restrictions (such as imposing constant arrival rates) compared to [6] to
avoid introducing superfluous notation.

######  Definition 1.

Consider a queueing system with a set ${\mathcal{V}}=\\{1,2,\ldots,N\\}$ of
customer classes. This queueing system is called an _order-independent loss
queue_ with state space ${\mathcal{C}}\subseteq{\mathcal{V}}^{*}$, arrival-
rate vector $\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{N})$, and
departure-rate function $\mu:{\mathcal{C}}\to\mathbb{R}_{+}$ if the following
conditions are satisfied:

  1. (a)

The evolution over time of the sequence
$c=(c_{1},\ldots,c_{n})\in{\mathcal{V}}$ of classes of present customers,
ordered by arrival, defines a Markov process such that:

    1. (i)

The state space of this Markov process is ${\mathcal{C}}$.

    2. (ii)

The transitions from each state $(c_{1},\ldots,c_{n})\in{\mathcal{C}}$ are
given as follows:

       * •

For each class $i\in{\mathcal{V}}$ such that
$(c_{1},\ldots,c_{n},i)\in{\mathcal{C}}$, there is a transition from state $c$
to state $(c_{1},\ldots,c_{n},i)$ with rate $\lambda_{i}$.

       * •

For each position $p\in\\{1,\ldots,n\\}$ such that
$\mu(c_{1},\ldots,c_{p})>\mu(c_{1},\ldots,c_{p-1})$, there is a transition
from state $c$ to state $(c_{1},\ldots,c_{p-1},c_{p+1},\ldots,c_{n})$ with
rate $\mu(c_{1},\ldots,c_{p})-\mu(c_{1},\ldots,c_{p-1})$ (with the convention
that $(c_{1},\ldots,c_{p-1})=\varnothing$ if $p=1$).

  2. (b)

The state space ${\mathcal{C}}$ satisfies the following conditions:

    1. (i)

if $(c_{1},\ldots,c_{n})\in{\mathcal{C}}$, then
$(c_{\sigma(1)},\ldots,c_{\sigma(n)})\in{\mathcal{C}}$ for each permutation
$\sigma$ of $\\{1,\ldots,n\\}$, and

    2. (ii)

if $(c_{1},\ldots,c_{n})\in{\mathcal{C}}\setminus\\{\varnothing\\}$, then
$(c_{1},\ldots,c_{n-1})\in{\mathcal{C}}$.

  3. (c)

The departure-rate function $\mu$ satisfies the following conditions:

    1. (i)

$\mu(c_{1},\ldots,c_{n})=\mu(c_{\sigma(1)},\ldots,c_{\sigma(n)})$ for each
state $(c_{1},\ldots,c_{n})\in{\mathcal{C}}$ and permutation $\sigma$ on
$\\{1,\ldots,n\\}$,

    2. (ii)

$\mu(c_{1},\ldots,c_{n},i)\geq\mu(c_{1},\ldots,c_{n})$ for each state
$(c_{1},\ldots,c_{n})\in{\mathcal{C}}$ and class $i\in{\mathcal{V}}$ such that
$(c_{1},\ldots,c_{n},i)\in{\mathcal{C}}$,

    3. (iii)

$\mu(\varnothing)=0$ and $\mu(c_{1},\ldots,c_{n})>0$ for each
$(c_{1},\ldots,c_{n})\in{\mathcal{C}}\setminus\varnothing$.

Proposition 2 below is our first main contribution. It proves that the
stochastic matching model is an order-independent loss queue. Note the form of
the state space ${\mathcal{C}}$ defined by (1), which differs from classic
applications of _loss_ queueing models in that the number of items of each
class can be arbitrarily large when it is not zero. Once Proposition 2 is
verified, applying [6, Theorem 1] suffices to prove that the stationary
measures of the Markov process defined in Section 2.2 have the product form
derived in [21, Theorem 1]. Both the result and its proof will be recalled in
Section 3.2 for completeness.

######  Proposition 2.

The stochastic matching model defined in Section 2.1 is an order-independent
loss queue, in the sense of Definition 1, with the state space ${\mathcal{C}}$
defined by (1), the arrival-rate vector
$\lambda=\alpha=(\alpha_{1},\alpha_{2},\ldots,\alpha_{N})$, and the departure-
rate function $\mu:{\mathcal{C}}\to\mathbb{R}_{+}$ defined by

$\displaystyle\mu(c)=\alpha({\mathcal{E}}({\mathcal{V}}(c)))\quad
c\in{\mathcal{C}}.$

###### Proof.

The details of checking the conditions of Definition 1 are left to the reader.
We simply make two remarks regarding the transitions of the Markov process
defined in Section 2.2. First, for each state
$c=(c_{1},\ldots,c_{n})\in{\mathcal{C}}$ and class $i\in{\mathcal{V}}$, we
have $(c_{1},\ldots,c_{n},i)\in{\mathcal{C}}$ if and only if
$i\notin{\mathcal{E}}({\mathcal{V}}(c))$, that is, if and only if class $i$
cannot be matched with any class present in state $c$. Second, if the function
$\mu:{\mathcal{C}}\to\mathbb{R}_{+}$ is as defined in the proposition, then
for each state $(c_{1},\ldots,c_{n})\in{\mathcal{C}}$ and position
$p\in\\{1,\ldots,n\\}$, the difference

$\displaystyle\mu(c_{1},\ldots,c_{p})-\mu(c_{1},\ldots,c_{p-1})=\alpha\left({\mathcal{E}}_{c_{p}}\setminus{\mathcal{E}}({\mathcal{V}}(c_{1},\ldots,c_{p-1}))\right)$

gives the arrival rate of the classes that can be matched with class $c_{p}$
but not with the classes present in $(c_{1},\ldots,c_{p-1})$. ∎

######  Remark.

The versatility of the order-independent framework allows us to generalize the
stochastic matching model introduced in Section 2.1 in several directions
while preserving its product-form nature. For instance, we again obtain an
order-independent loss queue if items of a given class can be matched with one
another. The main difference with the original model is that the state space
is reduced, as the buffer can contain at most one customer of such a class at
a time. We note that this extension was considered in the recent work [4], and
that the proofs of Theorems 3 and 4 in Sections 3.2 and 3.3 can be adapted to
provide a simpler proof of [4, Theorem 1]. Another extension, which again
leads to an order-independent loss queue, consists of describing
compatibilities with a directed graph (instead of an undirected graph), so
that there is an edge from class $i$ to class $j$ if incoming class-$i$ items
can be matched with class-$j$ items (which does not imply that incoming
class-$j$ items can be matched with class-$i$ items). Yet another extension
consists of allowing for item abandonment [23], meaning that an item may leave
the system without being matched. The stability region and product-form
stationary distribution of these extensions can be characterized by following
a similar approach as in the proofs of Theorems 3 and 4, or by applying known
results on order-independent queues and quasi-reversible queues, a more
general class of queueing models studied in [18, Chapter 3] and [13]. A last
extension consists of imposing an upper bound on the number of unmatched items
(either of each class or in total), or any other rejection rule that again
leads to an order-independent loss queue. In this case, the stationary
distribution is the restriction of that recalled in Theorem 3 to the set of
reachable states (after renormalization), and no stability condition is
needed.

######  Remark.

The usefulness of the equivalence between stochastic matching models and
conventional queueing models is particularly evident under the first-come-
first-matched policy, as the corresponding queueing model is known to have a
product-form stationary distribution. However, this equivalence may also prove
useful to transpose existing scheduling policies into matching policies, as
was done in [9, 20, 4], or to adapt exact or approximate analysis methods.

###  3.2 Product-form stationary distribution

The Markov process defined in Section 2.2 is irreducible. Indeed, for each
state $c=(c_{1},\ldots,c_{n})\in{\mathcal{C}}$ and each state
$d=(d_{1},\ldots,d_{m})\in{\mathcal{C}}$, we can first go from state $c$ to
state $\varnothing$ via $n$ transitions corresponding to arrivals of items
compatible with the items in state $c$, and then from state $\varnothing$ to
state $d$ via $m$ transitions corresponding to arrivals of the items present
in state $d$. Note that the first $n$ transitions occur with a positive
probability because the compatibility graph contains no isolated node;
additionally, the latter $m$ transitions indeed lead to state $d$ because the
set of classes in $d$ is an independent set by definition of ${\mathcal{C}}$.

Theorem 3 below recalls the form of the stationary measures of the Markov
process defined in Section 2.2. As observed before, this theorem is analogous
to [21, Theorem 1], which was stated for the discrete-time variant of the
stochastic matching model. Thanks to the relation with order-independent loss
queues proved in Proposition 2, we propose a simpler proof that consists of
explicitly writing the (partial) balance equations of the Markov process. This
proof, which is a special case of that of [6, Theorem 1], is sketched below
for completeness.

######  Theorem 3.

The stationary measures of the Markov process associated with the system state
are of the form

$\displaystyle\pi(c_{1},\ldots,c_{n})=\pi(\varnothing)\prod_{p=1}^{n}\frac{\alpha_{c_{p}}}{\alpha({\mathcal{E}}({\mathcal{V}}(c_{1},\ldots,c_{p})))},\quad(c_{1},\ldots,c_{n})\in{\mathcal{C}},$
(2)

where $\pi(\varnothing)$ is a normalization constant. The system is stable, in
the sense that this Markov process is ergodic, if and only if

$\displaystyle\sum_{(c_{1},\ldots,c_{n})\in{\mathcal{C}}}\prod_{p=1}^{n}\frac{\alpha_{c_{p}}}{\alpha({\mathcal{E}}({\mathcal{V}}(c_{1},\ldots,c_{p})))}<\infty,$
(3)

in which case the stationary distribution of the Markov process is given by
(2) with the normalization constant

$\displaystyle\pi(\varnothing)=\left(\sum_{(c_{1},\ldots,c_{n})\in{\mathcal{C}}}\prod_{p=1}^{n}\frac{\alpha_{c_{p}}}{\alpha({\mathcal{E}}({\mathcal{V}}(c_{1},\ldots,c_{p})))}\right)^{-1}.$
(4)

###### Sketch of proof.

We will prove that any measure $\pi$ of the form (2) satisfies the following
partial balance equations in each state
$c=(c_{1},\ldots,c_{n})\in{\mathcal{C}}$:

  * •

Equalize the flow out of state $c$ due to the arrival of an item that can be
matched with a present item and the flow into state $c$ due to the arrival of
an item that cannot be matched with a present item (if $c\neq\varnothing$):

$\displaystyle\pi(c)\alpha({\mathcal{E}}({\mathcal{V}}(c)))=\pi(c_{1},\ldots,c_{n-1})\alpha_{c_{n}}.$
(5)

  * •

Equalize the flow out of state $c$ due to the arrival of an item of a class
$i\in{\mathcal{V}}\setminus{\mathcal{E}}({\mathcal{V}}(c))$ that cannot be
matched with a present item and the flow into state $c$ due to the departure
of an item of this class:

$\displaystyle\pi(c)\alpha_{i}=\sum_{p=1}^{n+1}\pi(c_{1},\ldots,c_{p-1},i,c_{p},\ldots,c_{n})\alpha({\mathcal{E}}_{i}\setminus{\mathcal{E}}({\mathcal{V}}(c_{1},\ldots,c_{p-1}))),$
(6)

with the convention that $(c_{1},\ldots,c_{p-1})=\varnothing$ if $p=1$ and
$(c_{p},\ldots,c_{n})=\varnothing$ if $p=n+1$. Observe that, for each
$i\in{\mathcal{V}}\setminus{\mathcal{E}}({\mathcal{V}}(c))$ and
$p\in\\{1,\ldots,n+1\\}$, state $(c_{1},\ldots,c_{p-1},i,c_{p},\ldots,c_{n})$
belongs to ${\mathcal{C}}$ because the set of item classes present in this
state, ${\mathcal{V}}(c)\cup\\{i\\}$, is an independent set.

Proving that a measure $\pi$ satisfies the partial balance equations (5) and
(6) is sufficient to prove that $\pi$ is a stationary measure of the Markov
process defined by the system state, as summing these partial balance
equations yields the balance equations of the Markov process. We can easily
verify that any measure $\pi$ of the form (2) satisfies (5). That this measure
also satisfies (6) can be proved by induction over the buffer length $n$, in a
similar way as in [5, Theorem 1].

The stability condition (3) means that there exists a stationary measure whose
sum is finite, which is indeed necessary and sufficient for ergodicity of the
Markov process. Lastly, the constant $\pi(\varnothing)$ given by (4) is chosen
such that the stationary distribution sums to one. ∎

Multiplying all arrival rates $\alpha_{i}$ for $i\in{\mathcal{V}}$ by the same
positive constant does not modify the form of the stationary measures (2).
Indeed, this amounts to rescaling time without modifying the relative
importance of the states. In particular, as already stated in Section 2.1, we
can assume without loss of generality that
$\sum_{i\in{\mathcal{V}}}\alpha_{i}=1$, so that $\alpha_{i}$ is also the
fraction of arrivals that are of class $i$. In the remainder, it will also be
more convenient to define the stationary measures (2) with the following
recursion:

$\displaystyle\pi(c_{1},\ldots,c_{n})=\frac{\alpha_{c_{n}}}{\alpha({\mathcal{E}}({\mathcal{V}}(c_{1},\ldots,c_{n})))}\pi(c_{1},\ldots,c_{n-1}),\quad(c_{1},\ldots,c_{n})\in{\mathcal{C}}\setminus\\{\varnothing\\}.$
(7)

###  3.3 Stability condition

We now recall the stability condition derived in [21, Theorem 1] and again
provide a simpler proof based on the relation with order-independent loss
queues.

######  Theorem 4.

The stochastic matching model is stable, in the sense that the associated
Markov process is ergodic, if and only if

$\displaystyle\alpha({\mathcal{I}})<\alpha({\mathcal{E}}({\mathcal{I}})),\quad{\mathcal{I}}\in{\mathbb{I}}.$
(8)

###### Sketch of proof.

The proof consists of showing that (3) is satisfied if and only if the arrival
rates satisfy (8). The key idea is to observe that the denominators in (3)
only depend on the set of classes in the sequence $(c_{1},\ldots,c_{p})$.
Guided by this observation, we can define a new partition of the state space
${\mathcal{C}}$, that is a refinement of the partition
$({\mathcal{C}}_{\mathcal{I}},{\mathcal{I}}\in{\mathbb{I}}_{0})$, such that
the restriction of the sum in (3) to each part of this new partition can be
written as a finite product of geometric series that are convergent if and
only if the conditions (8) are satisfied. The details of the proof follow
along the same lines as in the proof of Theorem 1 in the appendix of [7]. The
only difference is that the set of customer classes that can be in the queue
at the same time is an independent set, so that the stability condition is
also restricted to independent sets. ∎

The stability condition (8) means that, for each independent set
${\mathcal{I}}$, there are enough items that can be matched with the classes
in ${\mathcal{I}}$ to prevent items of these classes from building up in the
buffer. As proved in [20], no matching policy can make the system stable if
the arrival rates do not satisfy the stability condition (8) (in particular,
first-come-first-matched is maximally stable). It is also shown in [20] that
we would not be able to find arrival rates that satisfy this stability
condition if the compatibility graph were bipartite. To better understand why
the presence of odd cycles is necessary, we examine two toy examples. First
consider a stochastic matching model similar to that of Section 2.1, except
that the graph is bipartite and consists of only two classes connected by an
edge. The stability condition (8) becomes $\alpha_{1}<\alpha_{2}$ and
$\alpha_{2}<\alpha_{1}$, and can therefore not be satisfied. Consistently, if
we examine the associated Markov process, we obtain a two-sided infinite
birth-and-death process, with transition rate $\alpha_{1}$ in one direction
and $\alpha_{2}$ in the other, that is either transient (if
$\alpha_{1}\neq\alpha_{2}$) or null recurrent (if $\alpha_{1}=\alpha_{2}$),
but cannot be positive recurrent. Now, if we instead consider a stochastic
matching model with three classes that are all compatible, the stability
condition (8) becomes $\alpha_{1}<\alpha_{2}+\alpha_{3}$,
$\alpha_{2}<\alpha_{1}+\alpha_{3}$, and $\alpha_{3}<\alpha_{1}+\alpha_{2}$,
and is satisfied for instance when
$\alpha_{1}=\alpha_{2}=\alpha_{3}=\frac{1}{3}$. If we examine the associated
Markov process, we obtain a three-sided infinite birth-and-death process that
is positive recurrent under the above conditions. In the remainder, we will
assume that the stability condition (8) is satisfied and let $\pi$ denote the
stationary distribution of the Markov process.

##  4 Performance metrics

Another consequence of Proposition 2 is that we can adapt numerical methods
originally developed for order-independent queues [22, 14, 12] to stochastic
matching models. Note that calculating average performance metrics associated
with _loss_ product-form queueing models is considered a hard problem in the
queueing literature [19]. Our task here is simplified by the fact that the
number of items of a given class can be arbitrarily large if it is not zero,
so that we can apply methods developed for _open_ queues. Also, since we
established that the continuous-time stochastic matching model and its
discrete-time counterpart have the same stationary distribution, the formulas
derived in this section can be applied without change to the discrete-time
variant of the model.

###  4.1 Probability of an empty system

We first propose a new formula to compute the normalization constant of the
stationary distribution of the stochastic matching model. With a slight abuse
of notation, for each ${\mathcal{I}}\in{\mathbb{I}}_{0}$, we let
$\pi({\mathcal{I}})$ denote the stationary probability that the set of
unmatched item classes is ${\mathcal{I}}$, that is,

$\displaystyle\pi({\mathcal{I}})=\sum_{c\in{\mathcal{C}}_{\mathcal{I}}}\pi(c),\quad{\mathcal{I}}\in{\mathbb{I}}_{0}.$
(9)

Equation (1) guarantees that
$\sum_{{\mathcal{I}}\in{\mathbb{I}}_{0}}\pi({\mathcal{I}})=1$. The following
proposition gives a recursive formula for $\pi({\mathcal{I}})$ for each
${\mathcal{I}}\in{\mathbb{I}}$. We will see later that this recursive formula
also gives a closed-form expression for the normalization constant
$\pi(\emptyset)=\pi(\varnothing)$. The proof technique is similar to that of
[14, Theorem 5.1], which was itself inspired from [22, Theorem 4], but the
proof is more straightforward because we skip the intermediary state
aggregation considered in these two works.

######  Proposition 5.

The stationary distribution of the set of unmatched item classes satisfies the
recursion

$\displaystyle\pi({\mathcal{I}})$
$\displaystyle=\frac{\sum_{i\in{\mathcal{I}}}\alpha_{i}\pi({\mathcal{I}}\setminus\\{i\\})}{\alpha({\mathcal{E}}({\mathcal{I}}))-\alpha({\mathcal{I}})},\quad{\mathcal{I}}\in{\mathbb{I}}.$
(10)

###### Proof.

Let ${\mathcal{I}}\in{\mathbb{I}}$. The proof of (10) relies on the following
partition of the set ${\mathcal{C}}_{\mathcal{I}}$:

$\displaystyle{\mathcal{C}}_{\mathcal{I}}=\bigcup_{i\in{\mathcal{I}}}\left(({\mathcal{C}}_{\mathcal{I}}\cdot
i)\cup({\mathcal{C}}_{{\mathcal{I}}\setminus\\{i\\}}\cdot i)\right),$ (11)

where the unions are disjoint and, for each
${\mathcal{D}}\subseteq{\mathcal{C}}$ and $i\in{\mathcal{V}}$, we write
${\mathcal{D}}\cdot
i=\\{(c_{1},\ldots,c_{n},i):(c_{1},\ldots,c_{n})\in{\mathcal{D}}\\}$. We first
apply (7) and (9) to rewrite $\pi({\mathcal{I}})$ as follows:

$\displaystyle\pi({\mathcal{I}})=\frac{1}{\alpha({\mathcal{E}}({\mathcal{I}}))}\sum_{c\in{\mathcal{C}}_{\mathcal{I}}}\alpha_{c_{n}}\pi(c_{1},\ldots,c_{n-1}).$

Then applying (11) yields

$\displaystyle\alpha({\mathcal{E}}({\mathcal{I}}))\pi({\mathcal{I}})=\sum_{i\in{\mathcal{I}}}\alpha_{i}\sum_{c\in{\mathcal{C}}_{\mathcal{I}}}\pi(c)+\sum_{i\in{\mathcal{I}}}\alpha_{i}\sum_{c\in{\mathcal{C}}_{{\mathcal{I}}\setminus\\{i\\}}}\pi(c)=\sum_{i\in{\mathcal{I}}}\alpha_{i}\pi({\mathcal{I}})+\sum_{i\in{\mathcal{I}}}\alpha_{i}\pi({\mathcal{I}}\setminus\\{i\\}).$

Rearranging the terms yields (10). ∎

Proposition 5 gives a closed-form expression for the normalization constant
$\pi(\emptyset)=\pi(\varnothing)$. It suffices to observe that the
unnormalized stationary measure
$\psi({\mathcal{I}})=\pi({\mathcal{I}})/\pi(\emptyset)$ also satisfies
recursion (10). Therefore, we can first compute $\psi({\mathcal{I}})$ for each
${\mathcal{I}}\in{\mathbb{I}}$ by applying recursion (10) with the base case
$\psi(\emptyset)=1$, and then derive $\pi(\emptyset)$ by normalization, that
is,
$\pi(\emptyset)=(\sum_{{\mathcal{I}}\in{\mathbb{I}}_{0}}\psi({\mathcal{I}}))^{-1}$.
Since there is a finite number of independent sets, this provides us with a
closed-form expression for the normalization constant. Note that the
denominator in (10) is always positive thanks to the stability condition (8).

One can verify that unfolding the above recursion yields the closed-form
expression derived in [21, Equation (5)]. The advantage of the above recursion
is that it avoids duplicate calculations. More specifically, the overall
complexity to evaluate the normalization constant using (10) with dynamic
programming is $O(MN)$, where $M=|{\mathbb{I}}|$ is the number of independent
sets and $N=|{\mathcal{V}}|$ is the number of item classes. By comparison, if
we naively apply [21, Equation (5)], the complexity is $O(MNP\times P!)$,
where $P$ is the independence number of the compatibility graph, that is, the
cardinality of a maximum independent set in this graph. In both cases however,
we need to enumerate all independent sets of the compatibility graph, which is
an NP-hard optimization problem in general. Consequently, both formulas can be
applied to make calculations only when there are few classes, when symmetries
between classes can be exploited to reduce complexity (see for instance [8]),
or when the graph structure guarantees that the number of independent sets is
small. The same remark holds for the formulas derived in Propositions 6 to 10
below. However, we will see in Section 5 that, even when these conditions are
not meet, these formulas can be used to gain insight into the impact of
parameters on performance.

###  4.2 Waiting probability

The result of Proposition 5 gives us directly a closed-form expression for the
waiting probability of the items of each class. Indeed, it follows from the
PASTA property that, for each $i\in{\mathcal{V}}$, the waiting probability of
class-$i$ items is given by

$\displaystyle\omega_{i}=\sum_{\begin{subarray}{c}{\mathcal{I}}\in{\mathbb{I}}_{0}:\\\
i\notin{\mathcal{E}}({\mathcal{I}})\end{subarray}}\pi({\mathcal{I}}).$ (12)

Upon recalling that $\sum_{i\in{\mathcal{V}}}\alpha_{i}=1$, Proposition 6
below shows that the average waiting probability is simply given by
$\frac{1}{2}$. This result is not surprising. Indeed, each matching occurs
between two items, one of that has just arrived (and therefore does not wait)
and another that was waiting. However, this result highlights that improving
the performance of one class (in terms of the waiting probability) necessarily
comes at the expense of another class.

######  Proposition 6.

The average waiting probability is given by
$\sum_{i\in{\mathcal{V}}}\alpha_{i}\omega_{i}=\frac{1}{2}$.

###### Proof.

We will verify that the per-class waiting probabilities satisfy the following
conservation equation:

$\displaystyle\sum_{i\in{\mathcal{V}}}\alpha_{i}\omega_{i}=\sum_{i\in{\mathcal{V}}}\alpha_{i}(1-\omega_{i}),$
(13)

after which the result follows by rearranging the terms. We have successively:

$\displaystyle\sum_{i\in{\mathcal{V}}}\alpha_{i}(1-\omega_{i})$
$\displaystyle=\sum_{i\in{\mathcal{V}}}\alpha_{i}\sum_{\begin{subarray}{c}{\mathcal{I}}\in{\mathbb{I}}:\\\
i\in{\mathcal{E}}({\mathcal{I}})\end{subarray}}\pi({\mathcal{I}})=\sum_{{\mathcal{I}}\in{\mathbb{I}}}\pi({\mathcal{I}})\sum_{i\in{\mathcal{E}}({\mathcal{I}})}\alpha_{i}=\sum_{{\mathcal{I}}\in{\mathbb{I}}}\pi({\mathcal{I}})\alpha({\mathcal{E}}({\mathcal{I}})),$

where the first equality follows from the definition of $\omega_{i}$, the
second by exchanging the two sums, and the third from the definition of
$\alpha({\mathcal{E}}({\mathcal{I}}))$. Applying (10) to the last member of
this equality yields

$\displaystyle\sum_{i\in{\mathcal{V}}}\alpha_{i}(1-\omega_{i})$
$\displaystyle=\sum_{{\mathcal{I}}\in{\mathbb{I}}}\left(\sum_{i\in{\mathcal{I}}}\alpha_{i}\pi({\mathcal{I}})+\sum_{i\in{\mathcal{I}}}\alpha_{i}\pi({\mathcal{I}}\setminus\\{i\\})\right)=\sum_{i\in{\mathcal{V}}}\alpha_{i}\sum_{\begin{subarray}{c}{\mathcal{I}}\in{\mathbb{I}}:\\\
i\in{\mathcal{I}}\end{subarray}}\left(\pi({\mathcal{I}})+\pi({\mathcal{I}}\setminus\\{i\\})\right),$

where the second equality follows by exchanging the sums. Equation (13)
follows by observing that, for each $i\in{\mathcal{V}}$, we have

$\displaystyle\sum_{\begin{subarray}{c}{\mathcal{I}}\in{\mathbb{I}}:\\\
i\in{\mathcal{I}}\end{subarray}}\left(\pi({\mathcal{I}})+\pi({\mathcal{I}}\setminus\\{i\\})\right)=\sum_{\begin{subarray}{c}{\mathcal{I}}\in{\mathbb{I}}_{0}:\\\
i\notin{\mathcal{E}}({\mathcal{I}})\end{subarray}}\pi({\mathcal{I}})=\omega_{i},$

where the first equality follows from a change of variable and the second by
definition of $\omega_{i}$. ∎

###  4.3 Mean number of unmatched items and mean matching time

Consider a random vector $X=(X_{1},X_{2},\ldots,X_{N})$ distributed as the
vector of numbers of unmatched items of each class in the stationary regime in
the stochastic matching model of Section 2.1. For now, we focus on the means
$L_{i}=\mathbb{E}\left[X_{i}\right]$ for each $i\in{\mathcal{V}}$, and we also
let $L=\sum_{i\in{\mathcal{V}}}L_{i}$ be the mean number of unmatched items,
all classes included. Propositions 7 and 8 below give a closed-form expression
for these quantities by using a similar aggregation technique as in the proof
of Proposition 5. As observed in [21, Section 3.4], these can be used to
calculate the mean matching time of items, that is, the mean time between the
arrival of an item and its matching with another item. Indeed, according to
Little’s law, the mean matching time of class-$i$ items is $L_{i}/\alpha_{i}$,
for each $i\in{\mathcal{V}}$, and the overall mean matching time is given by
$L/(\sum_{i\in{\mathcal{V}}}\alpha_{i})=L$ (since we assumed that
$\sum_{i\in{\mathcal{V}}}\alpha_{i}=1$).

######  Proposition 7.

For each $i\in{\mathcal{V}}$, the mean number of unmatched class-$i$ items is
given by

$L_{i}=\sum_{{\mathcal{I}}\in{\mathbb{I}}:i\in{\mathcal{I}}}L_{i}({\mathcal{I}})\pi({\mathcal{I}}),$

where $L_{i}({\mathcal{I}})$ is the mean number of unmatched class-$i$ items
given that the set of unmatched items is ${\mathcal{I}}$, and is given by the
recursion

$\displaystyle
L_{i}({\mathcal{I}})\pi({\mathcal{I}})=\frac{\alpha_{i}\pi({\mathcal{I}})+\alpha_{i}\pi({\mathcal{I}}\setminus\\{i\\})+\sum_{j\in{\mathcal{I}}\setminus\\{i\\}}\alpha_{j}L_{i}({\mathcal{I}}\setminus\\{j\\})\pi({\mathcal{I}}\setminus\\{j\\})}{\alpha({\mathcal{E}}({\mathcal{I}}))-\alpha({\mathcal{I}})},\quad{\mathcal{I}}\in{\mathbb{I}}:i\in{\mathcal{I}},$
(14)

with the base case $L_{i}({\mathcal{I}})=0$ for each
${\mathcal{I}}\in{\mathbb{I}}_{0}$ such that $i\notin{\mathcal{I}}$.

###### Proof.

The proof follows similar steps as that of Proposition 5, with some technical
complications. Let $i\in{\mathcal{V}}$. We have
$L_{i}=\sum_{{\mathcal{I}}\in{\mathbb{I}}_{0}}L_{i}({\mathcal{I}})\pi({\mathcal{I}})$
where, for each ${\mathcal{I}}\in{\mathbb{I}}_{0}$, $L_{i}({\mathcal{I}})$ is
the mean number of unmatched class-$i$ items given that the set of unmatched
item classes is ${\mathcal{I}}$. We have directly that
$L_{i}({\mathcal{I}})=0$ if $i\notin{\mathcal{I}}$. If $i\in{\mathcal{I}}$, we
have

$\displaystyle L_{i}({\mathcal{I}})\pi({\mathcal{I}})$
$\displaystyle=\sum_{c\in{\mathcal{C}}_{\mathcal{I}}}|c|_{i}\pi(c)=\sum_{c\in{\mathcal{C}}_{\mathcal{I}}}|c|_{i}\frac{\alpha_{c_{n}}}{\alpha({\mathcal{E}}({\mathcal{I}}))}\pi(c_{1},\ldots,c_{n-1}),$

where $|c|_{i}$ is the number of unmatched class-$i$ items in state $c$, for
each $c\in{\mathcal{C}}$, and the second equality follows from (7). Applying
partition (11) yields

$\displaystyle\alpha({\mathcal{E}}({\mathcal{I}}))L_{i}({\mathcal{I}})\pi({\mathcal{I}})$
$\displaystyle=\begin{aligned}
&\alpha_{i}\left[\sum_{c\in{\mathcal{C}}_{\mathcal{I}}}\left(|c|_{i}+1\right)\pi(c)+\sum_{c\in{\mathcal{C}}_{{\mathcal{I}}\setminus\\{i\\}}}\left(0+1\right)\pi(c)\right]\\\
&+\sum_{j\in{\mathcal{I}}\setminus\\{i\\}}\alpha_{j}\left[\sum_{c\in{\mathcal{C}}_{\mathcal{I}}}|c|_{i}\pi(c)+\sum_{c\in{\mathcal{C}}_{{\mathcal{I}}\setminus\\{j\\}}}|c|_{i}\pi(c)\right].\end{aligned}$

This, in turn, can be rewritten as

$\displaystyle\alpha({\mathcal{E}}({\mathcal{I}}))L_{i}({\mathcal{I}})\pi({\mathcal{I}})$
$\displaystyle=\begin{aligned}
&\alpha_{i}\left[L_{i}({\mathcal{I}})\pi({\mathcal{I}})+\pi({\mathcal{I}})+\pi({\mathcal{I}}\setminus\\{i\\})\right]+\sum_{j\in{\mathcal{I}}\setminus\\{i\\}}\alpha_{j}\left[L_{i}({\mathcal{I}})\pi({\mathcal{I}})+L_{i}({\mathcal{I}}\setminus\\{j\\})\pi({\mathcal{I}}\setminus\\{j\\})\right],\end{aligned}$
$\displaystyle=\begin{aligned}
&\alpha({\mathcal{I}})L_{i}({\mathcal{I}})\pi({\mathcal{I}})+\alpha_{i}\pi({\mathcal{I}})+\alpha_{i}\pi({\mathcal{I}}\setminus\\{i\\})+\sum_{j\in{\mathcal{I}}\setminus\\{i\\}}L_{i}({\mathcal{I}}\setminus\\{j\\})\pi({\mathcal{I}}\setminus\\{j\\}).\end{aligned}$

Rearranging the terms yields (14). ∎

To the best of our knowledge, no previous work obtained the above formula for
the stochastic matching model (either in recursive or in non-recursive form).
We now provide an analogous formula to directly calculate the mean number of
unmatched items, all classes included, without needing to calculate the mean
number of unmatched items of each class.

######  Proposition 8.

The mean number of unmatched items is given by

$\displaystyle
L=\sum_{{\mathcal{I}}\in{\mathbb{I}}}L({\mathcal{I}})\pi({\mathcal{I}}),$

where $L({\mathcal{I}})$ is the mean number of unmatched items given that the
set of unmatched items is ${\mathcal{I}}$, and is given by the recursion

$\displaystyle
L({\mathcal{I}})\pi({\mathcal{I}})=\frac{\alpha({\mathcal{E}}({\mathcal{I}}))\pi({\mathcal{I}})+\sum_{i\in{\mathcal{I}}}\alpha_{i}L({\mathcal{I}}\setminus\\{i\\})\pi({\mathcal{I}}\setminus\\{i\\})}{\alpha({\mathcal{E}}({\mathcal{I}}))-\alpha({\mathcal{I}})},\quad{\mathcal{I}}\in{\mathbb{I}},$
(15)

with the base case $L(\emptyset)=0$.

###### Proof.

The result follows by applying (14) to
$L({\mathcal{I}})=\sum_{i\in{\mathcal{I}}}L_{i}({\mathcal{I}})$ and
simplifying the expression with (10). ∎

Unfolding recursion (15) yields the formula given in [10, Proposition 4] but,
as for the normalization constant, applying dynamic programming leads to a
significant reduction of complexity compared to a naive application of this
proposition. More specifically, the time complexity to compute $L_{i}$ for
some $i\in{\mathcal{V}}$ or $L$ is $O(MN)$ if we use our approach, while the
time complexity to compute $L$ is $O(MNP\times P!)$ if we naively apply the
formula of [10, Proposition 4].

###  4.4 Distribution of the number of unmatched items

As before, let $X=(X_{1},X_{2},\ldots,X_{N})$ be a random vector distributed
like the vector of numbers of unmatched items of each class in stationary
regime in the stochastic matching model of Section 2.1. A closed-form
expression for the joint probability distribution of the vector $X$ can be
derived in the same way as in [14, Theorem 3.2, Equation (3.1)]. Here, we are
instead interested in the probability generating function $g_{X}$ of this
vector, defined as

$\displaystyle g_{X}(z)$
$\displaystyle=\mathbb{E}\left[\prod_{i\in{\mathcal{V}}}{z_{i}}^{X_{i}}\right],\quad
z=(z_{1},z_{2},\ldots,z_{N})\in{\mathcal{Z}},$ (16)

where
${\mathcal{Z}}=\\{z=(z_{1},z_{2},\ldots,z_{N})\in\mathbb{R}_{+}^{N}:z_{1}\leq
1,z_{2}\leq 1,\ldots,z_{N}\leq 1\\}$. One can show that this generating series
converges whenever $z\in{\mathcal{Z}}$. The following notation will be useful
to state Proposition 9 below. First, for each
$\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{N})\in\mathbb{R}_{+}^{N}$,
we write $\lambda({\mathcal{A}})=\sum_{i\in{\mathcal{A}}}\lambda_{i}$ for each
${\mathcal{A}}\subseteq{\mathcal{V}}$. Also, given two vectors
$\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{N})\in\mathbb{R}_{+}^{N}$
and $\mu=(\mu_{1},\mu_{2},\ldots,\mu_{N})\in\mathbb{R}_{+}^{N}$, we let
$\lambda\mu=(\lambda_{1}\mu_{1},\lambda_{2}\mu_{2},\ldots,\lambda_{N}\mu_{N})$
denote their elementwise product. We are now in position to give a closed-form
expression for the probability generating function of the vector $X$. Both
this result and its proof are adapted from [12, Proposition 3.1].

######  Proposition 9.

The probability generating function of the numbers of unmatched items of each
class in the buffer is given by

$\displaystyle
g_{X}(z)=\frac{\sum_{{\mathcal{I}}\in{\mathbb{I}}_{0}}\psi_{\alpha
z,\alpha}({\mathcal{I}})}{\sum_{{\mathcal{I}}\in{\mathbb{I}}_{0}}\psi_{\alpha,\alpha}({\mathcal{I}})},$
(17)

where, for each
$\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{N})\in\mathbb{R}_{+}^{N}$
and $\mu=(\mu_{1},\mu_{2},\ldots,\mu_{N})\in\mathbb{R}_{+}^{N}$ such that
$\lambda({\mathcal{I}})<\mu({\mathcal{E}}({\mathcal{I}}))$ for each
${\mathcal{I}}\in{\mathbb{I}}$, the set function $\psi_{\lambda,\mu}$ is
defined by the recursion

$\displaystyle\psi_{\lambda,\mu}({\mathcal{I}})=\frac{\sum_{i\in{\mathcal{I}}}\lambda_{i}\psi_{\lambda,\mu}({\mathcal{I}}\setminus\\{i\\})}{\mu({\mathcal{E}}({\mathcal{I}}))-\lambda({\mathcal{I}})},\quad{\mathcal{I}}\in{\mathbb{I}},$
(18)

with the base case $\psi_{\lambda,\mu}(\emptyset)=1$.

###### Proof.

It suffices to observe that, according to (2), (4), and (16), $g_{X}(z)$ can
be rewritten as

$\displaystyle g_{X}(z)$
$\displaystyle=\frac{\displaystyle\sum_{c\in{\mathcal{C}}}\prod_{p=1}^{n}\frac{z_{c_{p}}\alpha_{c_{p}}}{\alpha({\mathcal{E}}({\mathcal{V}}(c_{1},\ldots,c_{p})))}}{\displaystyle\sum_{c\in{\mathcal{C}}}\prod_{p=1}^{n}\frac{\alpha_{c_{p}}}{\alpha({\mathcal{E}}({\mathcal{V}}(c_{1},\ldots,c_{p})))}}=\frac{\displaystyle\sum_{{\mathcal{I}}\in{\mathbb{I}}_{0}}\sum_{c\in{\mathcal{C}}_{\mathcal{I}}}\prod_{p=1}^{n}\frac{z_{c_{p}}\alpha_{c_{p}}}{\alpha({\mathcal{E}}({\mathcal{V}}(c_{1},\ldots,c_{p})))}}{\displaystyle\sum_{{\mathcal{I}}\in{\mathbb{I}}_{0}}\sum_{c\in{\mathcal{C}}_{\mathcal{I}}}\prod_{p=1}^{n}\frac{\alpha_{c_{p}}}{\alpha({\mathcal{E}}({\mathcal{V}}(c_{1},\ldots,c_{p})))}}=\frac{\displaystyle\sum_{{\mathcal{I}}\in{\mathbb{I}}_{0}}\psi_{z\alpha,\alpha}({\mathcal{I}})}{\displaystyle\sum_{{\mathcal{I}}\in{\mathbb{I}}_{0}}\psi_{\alpha,\alpha}({\mathcal{I}})},$

where, for each
$\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{N})\in\mathbb{R}_{+}^{N}$
and $\mu=(\mu_{1},\mu_{2},\ldots,\mu_{N})\in\mathbb{R}_{+}^{N}$ such that
$\lambda({\mathcal{I}})<\mu({\mathcal{E}}({\mathcal{I}}))$ for each
${\mathcal{I}}\in{\mathbb{I}}$, we have

$\displaystyle\psi_{\lambda,\mu}({\mathcal{I}})=\sum_{c\in{\mathcal{C}}_{\mathcal{I}}}\prod_{p=1}^{n}\frac{\lambda_{c_{p}}}{\mu({\mathcal{E}}({\mathcal{V}}(c_{1},\ldots,c_{p})))},\quad{\mathcal{I}}\in{\mathbb{I}}_{0}.$

The recursive expression (18) follows from a similar argument as in the proof
of Proposition 5. ∎

Taking $\lambda=\mu=\alpha$ in (18) yields (10), so that in particular the
denominator in (17) is the normalization constant of the stationary
distribution (2). Referring back to the order-independent loss queue
introduced in Section 3, the vector
$\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{N})$ in (18) can be seen as
the arrival rates of the customer classes, while the vector
$\mu=(\mu_{1},\mu_{2},\ldots,\mu_{N})$ could be seen as service rates.

###  4.5 Distribution of the matching time

Let $T=(T_{1},T_{2},\ldots,T_{N})$ denote a vector distributed like the vector
of matching times of each class in the stationary regime in the stochastic
matching model of Section 2.1. For each $i\in{\mathcal{V}}$, the Laplace-
Stieltjes transform of the stationary matching time $T_{i}$ is defined as

$\displaystyle\varphi_{T_{i}}(u)=\mathbb{E}\left[e^{-uT_{i}}\right],\quad
u\in\mathbb{R}_{+}.$ (19)

One can show that this expectation is finite whenever $u\in\mathbb{R}_{+}$,
but we will be especially interested in the range $0\leq u\leq\alpha_{i}$.
Proposition 10 below gives a closed-form expression for this Laplace-Stieltjes
transform by applying the distributional form of Little’s law, in a similar
way as in [12, Corollary 3.2].

######  Proposition 10.

For each $i\in{\mathcal{V}}$, the Laplace-Stieltjes transform of the matching
time of class $i$ is given by

$\displaystyle\varphi_{T_{i}}(u)=g_{X}(z),\quad 0\leq u\leq\alpha_{i},$ (20)

where the function $g_{X}$ is defined on ${\mathcal{Z}}$ by (17) and the
vector $z\in{\mathcal{Z}}$ is given by

$\displaystyle z_{j}=\begin{cases}1-\frac{u}{\alpha_{i}}&\text{if $j=i$,}\\\
1&\text{if $j\in{\mathcal{V}}\setminus\\{i\\}$.}\end{cases}$

###### Proof.

Let $i\in{\mathcal{V}}$. The main argument consists of observing that class
$i$ satisfies the assumptions of the following theorem, proved in [17, Theorem
1]:

######  Theorem 11 (Distributional form of Little’s law).

Let an ergodic queueing system be such that, for a given class $i$ of
customers:

  1. (a)

arrivals form a Poisson process with rate $\alpha_{i}$;

  2. (b)

all arriving customers enter the system, and remain in the system until
served, i.e. there is no blocking, balking, or reneging;

  3. (c)

the customers leave the system one at a time in order of arrival;

  4. (d)

for any time $t$, the arrival process after time $t$ and the time in the
system of any customer arriving before $t$ are independent.

Then the moment generating function $g_{X_{i}}$ of the ergodic number $X_{i}$
of customers of this class in the system and the Laplace-Stieltjes transform
$\varphi_{T_{i}}$ of the ergodic time $T_{i}$ spent in the system by a
customer of this class satisfy
$g_{X_{i}}(z)=\varphi_{T_{i}}(\alpha_{i}(1-z))$.

The distributional form of Little’s law therefore implies that

$\displaystyle\varphi_{T_{i}}(u)=g_{X_{i}}\left(1-\frac{u}{\alpha_{i}}\right),\quad
0\leq u\leq\alpha_{i},$

where $g_{X_{i}}$ is the probability generating function of the stationary
number $X_{i}$ of unmatched class-$i$ items. We conclude by observing that,
for each $z_{i}\in[0,1]$, we have $g_{X_{i}}(z_{i})=g_{X}(z)$ where
$z\in{\mathcal{Z}}$ is the $N$-dimensional vector with $z_{i}$ in component
$i$ and $1$ elsewhere. ∎

##  5 Impact of load on performance

Performance in a stochastic matching model is the result of an intricate
interaction between arrival rates and matching compatibilities. Even finding
arrival rates that stabilize the matching model associated with a given
compatibility graph is non-trivial a priori. More subtly, it was observed in
[10] that, given a compatibility graph and a set of arrival rates that make
the system stable, adding more edges to the compatibility graph may hurt
performance (even if (8) guarantees that the system will remain stable).
Furthermore, applying the results of Sections 3 and 4 to derive performance in
a real-world matching problem will often be impossible due to the complexity
of the formulas. In this section, we show that these results are also useful
to gain intuition about the choices of parameters that optimize performance or
at least make the system stable. By analogy with queueing theory, we define
the _loads_ of the independent sets as

$\displaystyle\rho({\mathcal{I}})=\frac{\alpha({\mathcal{I}})}{\alpha({\mathcal{E}}({\mathcal{I}}))},\quad{\mathcal{I}}\in{\mathbb{I}}.$
(21)

These loads will be key to analyze performance, as for instance the stability
condition (8) can be rewritten as $\rho({\mathcal{I}})<1$ for each
${\mathcal{I}}\in{\mathbb{I}}$. Although this definition is inspired from the
analogy with queueing theory, there is a fundamental difference between (21)
and the regular definition of load in a queue, namely in (21) the arrival
rates appear both in the numerator and denominator. This implies in particular
that the loads are not increasing functions of the arrival rates.

###  5.1 Heuristics to optimize performance

Given the conclusions of [10], one may wonder, for a given vector of arrival
rates $\alpha=(\alpha_{1},\alpha_{2},\ldots,\alpha_{N})$ and a given
compatibility graph that lead to a stable stochastic matching model, whether
or not removing edges from the compatibility graph may improve performance,
and in this case which edge(s) should be removed. This discrete optimization
problem is difficult in general, as the number of configurations is
exponential in the number of classes. To gain insight into this question, we
consider a related problem that consists of finding arrival rates that
stabilize the system and minimize the mean matching time for a given
compatibility graph. Solving this optimization problem exactly with the
formulas of Section 4 is practically unfeasible when the number of classes is
large, but we propose two heuristics that yield acceptable performance in
practice.

#### Degree proportional

It was shown in [20, Theorem 1] that there exists a vector of arrival rates
$\alpha=(\alpha_{1},\alpha_{2},\ldots,\alpha_{N})$ that stabilizes the system
if and only if the compatibility graph is non-bipartite (which we assumed in
Section 2.1), but exhibiting such arrival rates is not trivial _a priori_.
Lemma 12 below gives a simple method to generate (an infinite number of) such
arrival rates.

######  Lemma 12.

Let $A=(a_{i,j})_{i,j\in{\mathcal{V}}}$ denote a symmetric matrix such that
$a_{i,j}>0$ if and only if nodes $i$ and $j$ are neighbors in the
compatibility graph. For each $i\in{\mathcal{V}}$, the weight of class $i$ is
defined as $d_{i}=\sum_{j\in{\mathcal{E}}_{i}}a_{i,j}$. The matching model is
stable if the arrival rates are chosen to be proportional to the weights, that
is,

$\displaystyle\alpha_{i}=\frac{d_{i}}{\sum_{j\in{\mathcal{V}}}d_{j}},\quad
i\in{\mathcal{V}}.$ (22)

###### Proof.

Assume that the arrival rates are given by (22) for some matrix $A$ that
satisfies the assumptions of the proposition, and let
$d=\sum_{i\in{\mathcal{V}}}d_{i}$. We will prove that these arrival rates
satisfy the stability condition (8). Consider an independent set
${\mathcal{I}}\in{\mathbb{I}}$. We have successively

$\displaystyle d\cdot\alpha({\mathcal{I}})$
$\displaystyle=\sum_{i\in{\mathcal{I}}}d_{i}=\sum_{i\in{\mathcal{I}}}\sum_{j\in{\mathcal{E}}_{i}}a_{i,j}=\sum_{j\in{\mathcal{E}}({\mathcal{I}})}\sum_{i\in{\mathcal{I}}\cap{\mathcal{E}}_{j}}a_{j,i}<\sum_{j\in{\mathcal{E}}({\mathcal{I}})}\sum_{i\in{\mathcal{E}}_{j}}a_{j,i}=\sum_{j\in{\mathcal{E}}({\mathcal{I}})}d_{j}=d\cdot\alpha({\mathcal{E}}({\mathcal{I}})).$

To prove that the above inequality is indeed strict, it suffices to show that
we cannot find an independent set ${\mathcal{I}}\in{\mathbb{I}}$ such that
${\mathcal{E}}({\mathcal{E}}({\mathcal{I}}))={\mathcal{I}}$. We can prove this
by contradiction. Indeed, if there were such an independent set
${\mathcal{I}}$, this would imply that
${\mathcal{E}}({\mathcal{I}})={\mathcal{V}}\setminus{\mathcal{I}}$ (because
the compatibility graph is connected) and that ${\mathcal{E}}({\mathcal{I}})$
is also an independent set, which would contradict our assumption that the
compatibility graph is non-bipartite. ∎

The matrix $A$ can be interpreted as the adjacency matrix of a weighted
variant of the compatibility graph. As a special case, if $A$ is the adjacency
matrix of the compatibility graph, then $d_{i}$ is the degree of class $i$, in
which case the arrival rates defined by (22) are called _degree proportional_.
For example, in the graph of Figure 1, the degree-proportional arrival rates
are $\alpha_{1}=\alpha_{2}=\frac{1}{4}$, $\alpha_{3}=\frac{3}{8}$, and
$\alpha_{4}=\frac{1}{8}$; choosing these arrival rates yields approximately a
probability 0.17 that the system is empty and a mean matching time of 2.25
time units. In general, if the number of classes is sufficiently small so that
all independent sets _can_ be enumerated, this degree-proportional solution
can also be used to initialize an optimization algorithm that searches for
arrival rates that minimize the mean matching time by applying Proposition 8.

#### Load minimization

The loads defined in (21) also play an instrumental role in better
understanding which arrival rates yield acceptable performance. To understand
this, let us first focus on the probability that the system is empty, which is
the inverse of the normalization constant and is given by Proposition 5. First
observe that (10) can be rewritten as

$\displaystyle\pi({\mathcal{I}})$
$\displaystyle=\frac{\rho({\mathcal{I}})}{1-\rho({\mathcal{I}})}\left(\sum_{i\in{\mathcal{I}}}\frac{\alpha_{i}}{\alpha({\mathcal{I}})}\pi({\mathcal{I}}\setminus\\{i\\})\right),\quad{\mathcal{I}}\in{\mathbb{I}},$
(23)

where the loads $\rho({\mathcal{I}})$ for ${\mathcal{I}}\in{\mathbb{I}}$ are
given by (21). Expanding the recursion yields

$\displaystyle\pi({\mathcal{I}})$
$\displaystyle=\pi(\emptyset)\sum_{s\in\mathfrak{S}_{\mathcal{I}}}\left(\prod_{p=1}^{|{\mathcal{I}}|}\frac{\rho(\\{s_{1},\ldots,s_{p}\\})}{1-\rho(\\{s_{1},\ldots,s_{p}\\})}\right)\left(\prod_{p=1}^{|{\mathcal{I}}|}\frac{\alpha_{s_{p}}}{\alpha(\\{s_{1},\ldots,s_{p}\\})}\right),\quad{\mathcal{I}}\in{\mathbb{I}},$

where $\mathfrak{S}_{\mathcal{I}}$ is the set of permutations of the set
${\mathcal{I}}$, interpreted as the set of all sequences
$s=(s_{1},s_{2},\ldots,s_{|{\mathcal{I}}|})$ in which each element of
${\mathcal{I}}$ appears exactly once. The first product may tend to infinity
if the load $\rho({\mathcal{J}})$ of any set
${\mathcal{J}}\subseteq{\mathcal{I}}$ tends to one, while the second product
is always between zero and one. By applying the normalization condition, we
obtain that $1/\pi(\emptyset)$ is a linear combination of products of the form

$\displaystyle\prod_{p=1}^{n}\frac{\rho(\\{s_{1},\ldots,s_{p}\\})}{1-\rho(\\{s_{1},\ldots,s_{p}\\})},\quad{\mathcal{I}}=\\{s_{1},s_{2},\ldots,s_{n}\\}\in{\mathbb{I}}.$

Similarly, we can rewrite (15) as follows:

$\displaystyle L({\mathcal{I}})\pi({\mathcal{I}})$
$\displaystyle=\frac{\pi({\mathcal{I}})}{1-\rho({\mathcal{I}})}+\frac{\rho({\mathcal{I}})}{1-\rho({\mathcal{I}})}\left(\sum_{i\in{\mathcal{I}}}\frac{\alpha_{i}}{\alpha({\mathcal{I}})}L({\mathcal{I}}\setminus\\{i\\})\pi({\mathcal{I}}\setminus\\{i\\})\right),\quad{\mathcal{I}}\in{\mathbb{I}}.$
(24)

In both cases, the variations of the function $x\mapsto\frac{x}{1-x}$ on
$(0,1)$ suggest that solving the following optimization problem is a good
heuristic to maximize the probability that the system is empty and minimize
the mean matching time:

$\displaystyle\begin{aligned}
\underset{\alpha}{\text{Minimize}}\quad&\max_{{\mathcal{I}}\in{\mathbb{I}}}\left(\rho({\mathcal{I}})\right),\\\
\text{subject to}\quad&\alpha_{i}\geq 0,\quad i\in{\mathcal{V}},\\\
&\sum_{i\in{\mathcal{V}}}\alpha_{i}=1.\end{aligned}$ (25)

One can verify that a solution of this optimization problem satisfies the
stability condition (8). In the example of Figure 1, the objective function of
the optimization problem (25) can be rewritten as

$\displaystyle\max\left(\frac{\alpha_{1}}{\alpha_{2}+\alpha_{3}},\frac{\alpha_{2}}{\alpha_{1}+\alpha_{3}},\frac{\alpha_{3}}{\alpha_{1}+\alpha_{2}+\alpha_{4}},\frac{\alpha_{4}}{\alpha_{3}},\frac{\alpha_{1}+\alpha_{4}}{\alpha_{2}+\alpha_{3}},\frac{\alpha_{2}+\alpha_{4}}{\alpha_{1}+\alpha_{3}}\right),$

and the unique solution is $\alpha_{1}=\alpha_{2}=\alpha_{3}=\frac{1}{3}$ and
$\alpha_{4}=0$. These arrival rates happen to be a global maximum for the
probability that the system is empty, with maximum value 0.25, and a local
minimum for the mean matching time, with minimum value 1.5 time
units222Although numerical evaluations suggest that this is also a global
minimum, proving this conjecture is complicated by the structure of (15).
Better understanding the properties of the mean matching time seen as a
function of the arrival rates and/or the graph structure would be an
interesting topic for future work..

In general, calculating a solution of the optimization problem (25) requires
enumerating all independent sets, which is precisely why we may not be able to
apply the results of Section 4 on the first place. This issue can be mitigated
by focusing on the independent sets with cardinality at most $n$ for some
$n\ll N$, or on the independent sets containing the most _central_ nodes
(under an appropriate definition of centrality), but the obtained solution may
not be stable. To further stress the importance of minimizing the loads, we
now consider a scaling regime in which the load of a (subset of) class(es)
becomes close to one, thus making the system unstable.

###  5.2 Heavy-traffic regime

We consider a scaling regime called _heavy traffic_ by analogy with the regime
of the same name studied in queueing theory. In a nutshell, the stability
condition associated with a maximal independent set becomes violated in (8),
so that items of these classes accumulate in the buffer (while items of other
classes become scarce); our result describes the corresponding limiting
distributions and performance metrics. The analysis relies on the closed-form
expressions derived in Section 4. The proof technique and the results
generalize those of [12, Theorem 3.1] but, as announced in the introduction,
the conclusions are different and illustrate the fundamental difference
between stochastic matching models and conventional queueing models.

#### Scaling regime

Fix ${\mathcal{I}}\in{\mathbb{I}}$, an independent set that is maximal with
respect to the inclusion relation. We have in particular that
${\mathcal{E}}({\mathcal{I}})={\mathcal{V}}\setminus{\mathcal{I}}$ and
$\alpha({\mathcal{I}})+\alpha({\mathcal{E}}({\mathcal{I}}))=\alpha({\mathcal{I}})+\alpha({\mathcal{V}}\setminus{\mathcal{I}})=1$.
We consider a scaling regime where, for each $i\in{\mathcal{V}}$,

$\displaystyle\alpha_{i}=\begin{cases}p_{i}\frac{\rho}{1+\rho},&i\in{\mathcal{I}},\\\
q_{i}\frac{1}{1+\rho},&i\in{\mathcal{V}}\setminus{\mathcal{I}},\end{cases}$
(26)

with
$\sum_{i\in{\mathcal{I}}}p_{i}=\sum_{i\in{\mathcal{V}}\setminus{\mathcal{I}}}q_{i}=1$
and $\rho\in(0,1)$. In this way,
$\rho=\alpha({\mathcal{I}})/\alpha({\mathcal{V}}\setminus{\mathcal{I}})=\rho({\mathcal{I}})$
is the ratio of the arrival rate of the classes in ${\mathcal{I}}$ to the
arrival rate of their compatible classes, that is, the load of set
${\mathcal{I}}$. We will show that, under some technical assumptions, as
$\rho\uparrow 1$, the buffer becomes saturated with items of the classes in
${\mathcal{I}}$ while running out of items of the classes in
${\mathcal{V}}\setminus{\mathcal{I}}$. That the classes in ${\mathcal{I}}$
become saturated is a consequence of (26), as we have

$\displaystyle\lim_{\rho\uparrow 1}\alpha({\mathcal{I}})=\lim_{\rho\uparrow
1}\alpha({\mathcal{V}}\setminus{\mathcal{I}})=\frac{1}{2}.$ (27)

The following technical assumption guarantees that the set ${\mathcal{I}}$ is
the only one that becomes saturated.

######  Assumption 13.

There exists $\rho^{*}\in[0,1)$ such that the stability conditions (8) are
satisfied by the measures $\alpha$ defined by (26) for each
$\rho\in(\rho^{*},1)$, and

$\displaystyle\lim_{\rho\uparrow 1}\alpha({\mathcal{J}})<\lim_{\rho\uparrow
1}\alpha({\mathcal{E}}({\mathcal{J}})),\quad{\mathcal{J}}\in{\mathbb{I}}\setminus\\{{\mathcal{I}}\\}.$

#### Asymptotic distribution

Proposition 14 below shows that, under the above technical assumption, the
mean number of items of the classes in ${\mathcal{I}}$ goes to infinity like
$(1-\rho)^{-1}$ as $\rho\uparrow 1$, while the mean number of items of the
classes in ${\mathcal{V}}\setminus{\mathcal{I}}$ goes to zero. Furthermore,
the distribution of items of the classes in ${\mathcal{I}}$ depends on their
respective arrival rates but not on their compatibility constraints with the
classes in ${\mathcal{V}}\setminus{\mathcal{I}}$. Similarly, as intuition
suggests, the waiting probability of the classes in ${\mathcal{I}}$ tends to
one as $\rho\uparrow 1$, while the waiting probability of the classes in
${\mathcal{V}}\setminus{\mathcal{I}}$ tends to zero. In this way, despite the
structural differences between the stochastic matching model and a more
conventional queueing model, the classes in ${\mathcal{I}}$ experience the
same performance as in an M/M/1 multi-class queue in which the load $\rho$
tends to one while, for each $i\in{\mathcal{I}}$, the relative arrival rate of
class $i$ is kept constant equal to $p_{i}$. The fundamental difference with
an M/M/1 multi-class queue, discussed in the remark below, is that the number
of items of the classes in ${\mathcal{V}}\setminus{\mathcal{I}}$ tends to
zero. Given $\rho^{*}\in[0,1)$ and two functions $f$ and $g$, defined on
$(\rho^{*},1)$, such that $g(\rho)>0$ for each $\rho\in(\rho^{*},1)$, we write
$f(\rho)\underset{\rho\uparrow 1}{\sim}g(\rho)$ if
$f(\rho)/g(\rho)\xrightarrow[\rho\uparrow 1]{}1$.

######  Proposition 14.

If Assumption 13 is satisfied, then the following limiting results hold:

  1. (14-a)

The stationary distribution of the set of unmatched item classes satisfies:

$\displaystyle\pi({\mathcal{I}})$ $\displaystyle\xrightarrow[\rho\uparrow
1]{}1,$ $\displaystyle\pi({\mathcal{J}})$
$\displaystyle\xrightarrow[\rho\uparrow
1]{}0,\quad{\mathcal{J}}\in{\mathbb{I}}_{0}\setminus\\{{\mathcal{I}}\\}.$

  2. (14-b)

The waiting probability of each item class satisfies:

$\displaystyle\omega_{i}$ $\displaystyle\xrightarrow[\rho\uparrow 1]{}1,\quad
i\in{\mathcal{I}},$ $\displaystyle\omega_{i}$
$\displaystyle\xrightarrow[\rho\uparrow 1]{}0,\quad
i\in{\mathcal{V}}\setminus{\mathcal{I}}.$

  3. (14-c)

The mean number of unmatched items of each class satisfies:

$\displaystyle L_{i}=\mathbb{E}\left[X_{i}\right]$
$\displaystyle\underset{\rho\uparrow 1}{\sim}p_{i}\frac{\rho}{1-\rho},\quad
i\in{\mathcal{I}},$ $\displaystyle L_{i}=\mathbb{E}\left[X_{i}\right]$
$\displaystyle\xrightarrow[\rho\uparrow 1]{}0,\quad
i\in{\mathcal{V}}\setminus{\mathcal{I}}.$

In particular, the limiting mean number of unmatched items (over all classes)
satisfies $L\underset{\rho\uparrow 1}{\sim}\frac{\rho}{1-\rho}$.

  4. (14-d)

The number of unmatched items of each class has the following limit in
distribution:

$\displaystyle(1-\rho)(X_{i})_{i\in{\mathcal{I}}}$
$\displaystyle\xrightarrow[\rho\uparrow
1]{d}\mathrm{Exp}(1)(p_{i})_{i\in{\mathcal{I}}},$
$\displaystyle(X_{i})_{i\in{\mathcal{V}}\setminus{\mathcal{I}}}$
$\displaystyle\xrightarrow[\rho\uparrow 1]{d}0,$

where $\mathrm{Exp}(1)$ represents a unit-mean exponentially-distributed
random variable.

  5. (14-e)

The mean matching time of each class satisfies:

$\displaystyle\mathbb{E}\left[T_{i}\right]$
$\displaystyle\underset{\rho\uparrow 1}{\sim}\frac{2}{1-\rho},\quad
i\in{\mathcal{I}},$ $\displaystyle\mathbb{E}\left[T_{i}\right]$
$\displaystyle\xrightarrow[\rho\uparrow 1]{}0,\quad
i\in{\mathcal{V}}\setminus{\mathcal{I}}.$

  6. (14-f)

The matching time of each class has the following limit in distribution:

$\displaystyle(1-\rho)T_{i}$ $\displaystyle\xrightarrow[\rho\uparrow
1]{d}\mathrm{Exp}\left(\frac{1}{2}\right),\quad i\in{\mathcal{I}},$
$\displaystyle T_{i}$ $\displaystyle\xrightarrow[\rho\uparrow 1]{d}0,\quad
i\in{\mathcal{V}}\setminus{\mathcal{I}},$

where $\mathrm{Exp}(\frac{1}{2})$ represents an exponentially-distributed
random variable with rate $\frac{1}{2}$.

###### Sketch of proof.

The proof of each property relies on the corresponding expression derived in
Section 4. Each proof follows the same pattern: the expression for which we
want to calculate the limit is a fraction whose numerator and denominator are
sums of terms given by recursive expressions; we first use the recursive
expressions to identify the dominating term in each sum, and then we simplify
the dominating terms to derive the limit. The complete proof is given in the
appendix. ∎

######  Remark.

The analysis is simplified by our choice of a maximal independent set and by
Assumption 13. Indeed, these two assumptions guarantee that ${\mathcal{I}}$ is
the only independent set that becomes saturated as $\rho\uparrow 1$, and that
all other classes are absorbed by the surplus of items in the classes in
${\mathcal{I}}$. We could also consider a scaling regime where these
assumptions are not satisfied. For instance, we could choose an independent
set ${\mathcal{I}}$ that is not maximal with respect to the inclusion
relation. Under some technical assumptions, we would obtain a scaling regime
where the buffer becomes saturated with items of the classes in
${\mathcal{I}}$ and runs out of items of the classes in
${\mathcal{E}}({\mathcal{I}})$, while containing a positive but finite number
of items of the classes in
${\mathcal{V}}\setminus({\mathcal{I}}\cup{\mathcal{E}}({\mathcal{I}}))$. This
intermediary scaling regime becomes apparent in the numerical results of
Section 6.

######  Remark.

The above-defined heavy-traffic regime is actually closer to a _light-traffic_
regime for the classes in ${\mathcal{V}}\setminus{\mathcal{I}}$, as
Proposition 14 shows that the number of items of these classes tends to zero.
Yet, one can verify that the loads of the classes of this set do not tend to
zero. These two observations may seem paradoxical, especially with
conventional queueing models, like the M/M/1 queue, in mind. This apparent
paradox can be explained by recalling that the arrival of an item can either
increase _or decrease_ the number of present items. This is different from
conventional queueing models, in which the arrival of a customer always
increases the number of present customers. Intuitively, in the scaling regime
studied in this section, the arrival of an item of a class in ${\mathcal{I}}$
will (almost) always increase the number of unmatched items, while the arrival
of an item of a class in ${\mathcal{V}}\setminus{\mathcal{I}}$ will (almost)
always decrease the number of unmatched items.

##  6 Numerical results

In this section, we study the toy examples of Figure 3 and evaluate two
performance metrics, the waiting probability and the mean matching time,
defined in Sections 4.2 and 4.3. All numerical results are computed using the
closed-form expressions derived in these two sections. As before, we impose
that $\sum_{i\in{\mathcal{V}}}\alpha_{i}=1$, so that $\alpha_{i}$ is the long-
term fraction of items that belong to class $i$, for each $i\in{\mathcal{V}}$.
More specifically, in each case, we impose that
$\alpha_{2}=\alpha_{3}=\ldots=\alpha_{N}$ and let the arrival rate
$\alpha_{1}$ of class $1$ vary such that its load
$\rho=\alpha_{1}/\alpha({\mathcal{E}}_{1})$ belongs to the interval $(0,1)$.
This allows us to gain insight into the impact of varying the load of one
class on performance and to illustrate the heavy-traffic result of Section
5.2.

$1$$2$$3$$4$$5$$6$$7$$8$$9$$1$ (a) A cycle graph.

$1$$2$$3$$4$$5$$6$$7$$8$$9$$1$ (b) A cycle graph with a chord between nodes
$5$ and $9$.

$5$$6$$7$$8$$9$$5$4321 (c) A racket-shaped graph.

Figure 3: Toy examples with $N=9$ classes.

###  6.1 Cycle graph

We first consider a stochastic matching model with a simple yet insightful
compatibility graph, namely a cycle graph with an odd number of nodes. More
specifically, we let $N=2K+1$ denote the number of classes, where
$K\in\\{1,2,3,\ldots\\}$, and we assume that, for each $i\in{\mathcal{V}}$,
items of classes $i$ and $i+1$ can be matched with one another (with the
convention that $i+1=1$ if $i=N$). An example of a cycle graph with $N=9$
nodes is shown in Figure 3a. The dynamics in a matching model with a cycle
graph are representative of the dynamics obtained with more complex
compatibility graphs. Indeed, as recalled in Section 3.3, a stochastic
matching model can be stabilized if and only if its compatibility graph is
non-bipartite, which means that it contains at least one odd cycle. The
arrival rates are given by

$\displaystyle\alpha_{1}$
$\displaystyle=\frac{\frac{\rho}{K}}{1+\frac{\rho}{K}},$
$\displaystyle\alpha_{i}$
$\displaystyle=\frac{\frac{1}{2K}}{1+\frac{\rho}{K}},\quad
i\in\\{2,3,\ldots,N\\},$ (28)

so that $\rho$ is the load of class $1$. One can show by a direct
reasoning333Let ${\mathcal{I}}\in{\mathbb{I}}$. The sets
${\mathcal{I}}+1=\\{i+1,i\in{\mathcal{I}}\\}$ and
${\mathcal{I}}-1=\\{i-1,i\in{\mathcal{I}}\\}$ (again with the convention that
$i+1=1$ if $i=N$ and $i-1=N$ if $i=1$) both contain $|{\mathcal{I}}|$ nodes
and are included into ${\mathcal{E}}({\mathcal{I}})$. It suffices to show that
at least one of these two sets contains an element that the other does not. In
turn, to prove this, it suffices to observe that an independent set
${\mathcal{I}}$ contains at most $K$ nodes, so that at least two of these
nodes are separated by at least two nodes that do not belong to
${\mathcal{I}}$. that $|{\mathcal{E}}({\mathcal{I}})|\geq|{\mathcal{I}}|+1$
for each ${\mathcal{I}}\in{\mathbb{I}}$, which is sufficient to prove that,
under the arrival rates (28), the system is stable for each $\rho\in(0,1)$. In
what follows, we focus on the case $N=9$ for simplicity of exposition, but the
results for $N\in\\{3,5,7,11,13,15\\}$ (not shown here) are similar. To
illustrate the performance gain permitted by the recursive expressions of
Section 4 compared to existing expressions, we observe that, again with $N=9$,
the number of terms to sum to derive each metric is equal to 75 using dynamic
programming and to 459 if we naively apply the formulas of [21, Equation (5)]
and [10, Proposition 4], giving a ratio of $459/75\simeq 6.12$; with $N=15$
classes, the numbers of terms to sum are $1,363$ and $234,405$, respectively,
giving a ratio of $234,405/1,363\simeq 171.98$.

Overall12 and 93 and 84 and 75 and 6

$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$0.2$$0.4$$0.6$$0.8$$1$Load $\rho$ of class
1Waiting probability

$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$20$$40$Load $\rho$ of class 1Mean matching time

Figure 4: Performance (overall and per class) in a cycle with $N=9$ classes.

The waiting probability and mean matching time are shown in Figure 4. Because
of the symmetry of the model, the performance of a class only depends on its
distance to class $1$, so that classes $i+1$ and $N-i+1$ have the same
performance for each $i\in\\{1,2,\ldots,K\\}$. Focusing on the waiting
probability, we can partition classes into two categories, those at an odd
distance from class $1$ (namely, classes 2, 4, 7, and 9) and those at an even
distance from class $1$ (namely, classes 1, 3, 5, 6, and 8). Indeed, as the
load of class $1$ increases, the waiting probability of the former set of
classes decreases while that of the latter set of classes increases. The only
exception is the waiting probability of classes $5$ and $6$, which first
increases and then decreases; we will mention this again at the end of this
paragraph. Intuitively, increasing the load of class $1$ has the following
cascading effect. To preserve the system stability, the additional class-$1$
items need be matched with items of classes $2$ and $9$, so that the waiting
probability of these two classes decreases. The side effect is that there are
fewer items of classes $2$ and $9$ to be matched with items of classes $3$ and
$8$, so that the waiting probability of classes $3$ and $8$ increases. In
turn, surplus items of classes $3$ and $8$ need be matched with items of
classes $4$ and $7$ to preserve stability, so that the waiting probability of
classes $4$ and $7$ decreases, and so on. The only exception is classes $5$
and $6$, whose waiting probability is first increasing and then decreasing.
Focusing on class $5$ for instance, the non-monotonic evolution of the waiting
probability is the result of two conflicting effects. On the one hand, the
even path $1$–$2$–$3$–$4$–$5$ suggests that increasing the load of class $1$
tends to increase the waiting probability of class $5$. On the other hand, the
odd path $1$–$9$–$8$–$7$–$6$–$5$ suggests that increasing the load of class
$1$ tends to decrease the waiting probability of class $5$.

Considering the mean matching time allows us to refine the above discussion.
Indeed, we can observe that, except for classes $1$, $2$, and $9$, the mean
matching time of all classes tends to infinity both when $\rho$ tends to zero
and when $\rho$ tends to one. This suggests that not only the performance of
classes $5$ and $6$ but also those of other classes are the result of two
opposite effects, one that is conveyed by the odd-length path from class $1$
and the other by the even-length path from class $1$.

To better understand the speeds at which the mean matching times of classes
tend to infinity, let us start with $\rho=\frac{1}{2}$ (meaning that all
arrival rates are equal) and consider the chain reaction on the path
$1$–$2$–$3$–$\cdots$-$8$–$9$ as the load $\rho$ decreases and tends to 1. The
first class to be impacted is class $2$, as this class needs the presence of
class $1$ to remain stable, and indeed the mean matching time of class $2$
tends to infinity the fastest. The side effect is that class-$3$ items are
matched more frequently with class-$2$ items, so that the mean matching time
of class $3$ decreases. This implies that class-$3$ items are less available
for class $4$, so that the mean matching time of class $4$ is the next to tend
to infinity. By repeating this reasoning, we obtain that the mean matching
time of class $6$ is the next to tend to infinity, followed by the mean
matching time of class $8$. A similar phenomenon occurs on the path
$1$–$9$–$8$–$\cdots$–$3$–$2$, so that the mean matching times of classes $9$,
$7$, $5$, and $3$ also tend to infinity one after the other.

###  6.2 Cycle graph with a chord

To complement our observations, we break the model symmetry by adding a chord
between classes $5$ and $9$. The arrival rates are still given by (28). It
follows from (8) that adding an edge to the compatibility graph cannot reduce
the stability region of the corresponding stochastic matching model, so that
the model is still stable for each $\rho\in(0,1)$. We again focus on a model
with $N=9$ classes. We have verified that the reasoning we develop below
generalizes to other numbers of classes and other placements of the chord
relative to class 1, although the results vary qualitatively.

Overall123456789

$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$0.2$$0.4$$0.6$$0.8$$1$Load $\rho$ of class
1Waiting probability

$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$20$$40$Load $\rho$ of class 1Mean matching time

Figure 5: Performance (overall and per class) in a cycle with $N=9$ classes
supplemented with a chord between classes $5$ and $9$.

The results are shown in Figure 5. Adding a chord breaks the symmetry between
classes, but we can still divide classes into several categories depending on
the limiting behavior of their waiting probability and mean matching time as
the load $\rho$ tends to either zero or one. Let us first focus on the
limiting regime where the load $\rho$ tends to zero. In view of the mean
matching times, the first class to become unstable is class $2$, which is
natural because the supply rate of class $3$ items is not sufficient to
maintain its stability. The main difference with the previous scenario is that
the stability of class $9$ is temporarily preserved by its compatibility with
classes $8$ and $5$. The overabundance of class $2$ leads to the exhaustion of
class $3$, which in turn leads to the overabundance of class $4$, which in
turn leads to the exhaustion of class $5$. Once class $5$ is exhausted, the
next classes to become unstable are its neighbors, classes $6$ and $9$, which
eventually leads to the overabundance of classes $7$ and $8$ as well. The
limiting behavior as the load $\rho$ tends to one is close to that observed
for the cycle without chord. The reason is that the first immediate impact of
increasing the load of class $1$ is the exhaustion of class $9$ (as well as
class $2$), rendering the presence of the chord useless, so that then we are
back to the scenario of Section 6.1.

###  6.3 Racket-shaped graph

We finally consider the racket-shaped graph of Figure 3c. Although a line
alone cannot be stabilized because it forms a bipartite graph, this example
gives us an idea of the dynamics that may arise in such a graph. One can also
think of this graph as being obtained by removing the edge between nodes $1$
and $9$ in the cycle graph with a chord of Figure 3b. The arrival rates of
classes are given by

$\displaystyle\alpha_{1}$
$\displaystyle=\frac{\frac{\rho}{N-1}}{1+\frac{\rho}{N-1}},$
$\displaystyle\alpha_{i}$
$\displaystyle=\frac{\frac{1}{N-1}}{1+\frac{\rho}{N-1}},\quad
i\in\\{2,3,\ldots,N\\},$

so that $\rho$ is again the load of class $1$. One can do a similar reasoning
as for the cycle to show that this system is stable whenever $\rho\in(0,1)$.
We again focus on a scenario with $N=9$ nodes in total, $4$ of which belong to
the line part and $5$ to the cycle part. In general, we observed that the
qualitative behavior of the results depends mainly on the parity of the
numbers of classes on the line part and on the circle part of the graph, and
we may again adapt the reasoning below to explain this qualitative behavior.

The results for the racket-shaped graph of Figure 3c are shown in Figure 6.
Along the line part of the graph, the impact of increasing or decreasing the
load $\rho$ of class $1$ is as one could expect. For instance, as $\rho$ tends
to one, class-$2$ items become scarce, which leads to the instability of class
$3$, which in turn leads to the scarcity of class $4$. Compared to the cycle
with a chord, the most striking observation is that classes 5, 6, 7, 8, and 9
remain stable as the load $\rho$ tends to one, and that these classes have the
same asymptotic waiting probability and mean matching time. The reason is
that, asymptotically, the model restricted to classes $5$ to $9$ evolves like
a cycle with five classes that all have the same arrival rate, and this model
is stable.

Overall123456 and 97 and 8

$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$0.2$$0.4$$0.6$$0.8$$1$Load $\rho$ of class
1Waiting probability

$0$$0.2$$0.4$$0.6$$0.8$$1$$0$$20$$40$Load $\rho$ of class 1Mean matching time

Figure 6: Performance (overall and per class) in the racket-shaped graph with
$N=9$ classes shown in Figure 3c.

If we again focus on the asymptotic regime where the load $\rho$ tends to one,
it seems that the overall mean matching time is lower in the racket-shaped
graph than in the cycle with a chord, which may seem counterintuitive after
observing that the former is obtained by _removing_ an edge from the latter.
This observation is however consistent with the discussion of [10], which
compared this phenomenon with Braess’s paradox in road networks.

##  7 Conclusion

In this paper, we proved that a stochastic non-bipartite matching model is an
order-independent loss queue. This equivalence allowed us to propose simpler
proofs for existing results and to derive new results regarding stochastic
matching models. In particular, we used the order-independent queue framework
to give alternative proofs for the product-form stationary distribution and
the stability condition derived in [21, Theorem 1]. By adapting numerical
methods developed in [22, 14, 12], we also derived new closed-form expressions
for the normalization constant, the mean matching time, and other performance
metrics. In turn, these formulas were applied to gain insight into the impact
of parameters on performance. By analogy with queueing theory, we highlighted
the importance of the so-called load parameters and studied the system
behavior in the heavy-traffic regime, in which the load of a subset of classes
becomes critical. The obtained formulas were also put in practice with
numerical results.

For future works, we would like to derive simpler formulas for the performance
metrics. Indeed, even though our recursive formulas allow for a dynamic-
programming approach, complexity remains exponential in the number of classes
in general, which limits their applicability to models with only a few
classes. In parallel, we would like to understand if and how these results can
be adapted to analyze the performance of stochastic matching models with a
bipartite compatibility graph, like the one studied in [11, 3, 9, 1, 2], in
which items arrive in pairs. Lastly, as mentioned before, we would like to
explore the generalizations of the stochastic matching model made possible by
the equivalence with order-independent loss queues. Yet another avenue for
future work, which goes beyond the scope of stochastic matching models,
consists of extending the heavy-traffic result proved for multi-class multi-
server queues in [12] to other order-independent (loss) queues, like those
considered in [14, Section 4.3].

#### Acknowledgement

The author is grateful to Sem Borst for his valuable comments on an earlier
draft of this paper and to Ellen Cardinaels for mentioning the reference [4].
The author thanks both of them for helpful discussions on the related work
[12]. The author is also grateful to the anonymous editor and reviewer for
their valuable suggestions on the contents and exposition of the paper, and in
particular for suggesting a simplification in Section 3.

## References

  * [1] I. Adan, A. Bušić, J. Mairesse, and G. Weiss.  Reversibility and further properties of FCFS infinite bipartite matching.  Mathematics of Operations Research, 43(2):598–621, 2017.
  * [2] I. Adan, I. Kleiner, R. Righter, and G. Weiss.  FCFS parallel service systems and matching models.  Performance Evaluation, 127-128:253–272, 2018.
  * [3] I. Adan and G. Weiss.  Exact FCFS matching rates for two infinite multitype sequences.  Operations Research, 60(2):475–489, 2012.
  * [4] J. Begeot, I. Marcovici, P. Moyal, and Y. Rahme.  A general stochastic matching model on multigraphs.  arXiv:2011.05169 [math], 2020.
  * [5] S. A. Berezner, C. F. Kriel, and A. E. Krzesinski.  Quasi-reversible multiclass queues with order independent departure rates.  Queueing Systems, 19(4):345–359, 1995.
  * [6] S. A. Berezner and A. E. Krzesinski.  Order independent loss queues.  Queueing Systems, 23(1):331–335, 1996.
  * [7] T. Bonald and C. Comte.  Balanced fair resource sharing in computer clusters.  Performance Evaluation, 116:70–83, 2017.
  * [8] T. Bonald, C. Comte, V. Shah, and G. de Veciana.  Poly-symmetry in processor-sharing systems.  Queueing Systems, 86(3):327–359, 2017.
  * [9] A. Bušić, V. Gupta, and J. Mairesse.  Stability of the bipartite matching model.  Advances in Applied Probability, 45(2):351–378, 2013.
  * [10] A. Cadas, J. Doncel, J.-M. Fourneau, and A. Bušić.  Flexibility can hurt dynamic matching system performance.  arXiv:2009.10009 [cs, math], 2020.
  * [11] R. Caldentey, E. H. Kaplan, and G. Weiss.  FCFS infinite bipartite matching of servers and customers.  Advances in Applied Probability, 41(3):695–730, 2009.
  * [12] E. Cardinaels, S. Borst, and J. S. H. van Leeuwaarden.  Heavy-traffic universality of redundancy systems with data locality constraints.  arXiv:2005.14566 [math], 2021.
  * [13] X. Chao.  Networks with customers, signals, and product form solution.  In R. J. Boucherie and N. M. van Dijk, editors, Queueing Networks: A Fundamental Approach, International Series in Operations Research & Management Science, pages 217–267. Springer US, 2011.
  * [14] C. Comte.  Resource management in computer clusters: algorithm design and performance analysis.  PhD thesis, Institut Polytechnique de Paris, 2019.
  * [15] W. Feller.  An Introduction to Probability Theory and Its Applications, Volume 2.  Wiley, 1966.
  * [16] K. Gardner and R. Righter.  Product forms for FCFS queueing models with arbitrary server-job compatibilities: an overview.  Queueing Systems, 96(1):3–51, 2020.
  * [17] J. Keilson and L. D. Servi.  A distributional form of little’s law.  Operations Research Letters, 7(5):223–227, 1988.
  * [18] F. P. Kelly.  Reversibility and Stochastic Networks.  Cambridge University Press, 2011.
  * [19] G. Louth, M. Mitzenmacher, and F. Kelly.  Computational complexity of loss networks.  Theoretical Computer Science, 125(1):45–59, 1994.
  * [20] J. Mairesse and P. Moyal.  Stability of the stochastic matching model.  Journal of Applied Probability, 53(4):1064–1077, 2016.
  * [21] P. Moyal, A. Bušić, and J. Mairesse.  A product form for the general stochastic matching model.  Journal of Applied Probability, 58(2):449–468, 2021.
  * [22] V. Shah and G. de Veciana.  High-performance centralized content delivery infrastructure: Models and asymptotics.  IEEE/ACM Transactions on Networking, 23(5):1674–1687, 2015\.
  * [23] T. H. D. Thi, J. Fourneau, and M. A. Tran.  Networks of order independent queues with signals.  In 2013 IEEE 21st International Symposium on Modelling, Analysis and Simulation of Computer and Telecommunication Systems, pages 131–140, 2013.

## Appendix: Proof of Proposition 14

As announced, the proof of each property relies on the corresponding
expression derived in Section 4. The key argument consists of observing that
Equation (27) and Assumption 13 can be reformulated as follows: as
$\rho\uparrow 1$, $\rho({\mathcal{J}})$ tends to one if
${\mathcal{J}}={\mathcal{I}}$ (as we have $\rho({\mathcal{I}})=\rho$) and to a
constant strictly less than one if
${\mathcal{J}}\in{\mathbb{I}}\setminus\\{{\mathcal{I}}\\}$.

###### Proof of Property (14-a)..

According to Proposition 5 and Equation (23), the stationary distribution of
the set of unmatched classes can be rewritten as

$\displaystyle\pi({\mathcal{J}})=\frac{\psi({\mathcal{J}})}{\sum_{{\mathcal{K}}\in{\mathbb{I}}_{0}}\psi({\mathcal{K}})},\quad{\mathcal{J}}\in{\mathbb{I}}_{0},$
(29)

where $\psi({\mathcal{J}})$ is given by $\psi(\emptyset)=1$, and

$\displaystyle\psi({\mathcal{J}})$
$\displaystyle=\frac{\rho({\mathcal{J}})}{1-\rho({\mathcal{J}})}\left(\sum_{i\in{\mathcal{J}}}\frac{\alpha_{i}}{\alpha({\mathcal{J}})}\psi({\mathcal{J}}\setminus\\{i\\})\right),\quad{\mathcal{J}}\in{\mathbb{I}}.$

Since $\rho({\mathcal{J}})$ tends to one if ${\mathcal{J}}={\mathcal{I}}$ and
to a constant strictly less than one if
${\mathcal{J}}\in{\mathbb{I}}\setminus\\{{\mathcal{I}}\\}$, it follows that
$\psi({\mathcal{J}})$ tends to infinity if ${\mathcal{J}}={\mathcal{I}}$ and
to a finite constant if
${\mathcal{J}}\in{\mathbb{I}}_{0}\setminus\\{{\mathcal{I}}\\}$. We conclude by
inserting this into (29). ∎

###### Proof of Property (14-b).

The result for the classes in ${\mathcal{I}}$ follows by inserting Property
(14-a) into (12). The result for the classes in
${\mathcal{V}}\setminus{\mathcal{I}}$ is then a consequence of (13) and (27).
∎

###### Proof of Properties (14-c) and (14-e).

Consider a class $i\in{\mathcal{I}}$. According to Proposition 7 and Equation
(29), the expected number of class-$i$ items can be rewritten as

$\displaystyle
L_{i}=\frac{\sum_{{\mathcal{J}}\in{\mathbb{I}}_{0}:i\in{\mathcal{J}}}L_{i}({\mathcal{J}})\psi({\mathcal{J}})}{\sum_{{\mathcal{J}}\in{\mathbb{I}}_{0}}\psi({\mathcal{J}})},$
(30)

where $L_{i}({\mathcal{J}})\psi({\mathcal{J}})$ is given by
$L_{i}({\mathcal{J}})\psi({\mathcal{J}})=0$ if $i\notin{\mathcal{J}}$, and

$\displaystyle
L_{i}({\mathcal{J}})\psi({\mathcal{J}})=\frac{\rho({\mathcal{J}})}{1-\rho({\mathcal{J}})}\begin{aligned}
\Bigg{(}&\frac{\alpha_{i}}{\alpha({\mathcal{J}})}\psi({\mathcal{J}})+\frac{\alpha_{i}}{\alpha({\mathcal{J}})}\psi({\mathcal{J}}\setminus\\{i\\})\\\
&+\sum_{j\in{\mathcal{J}}\setminus\\{i\\}}\frac{\alpha_{j}}{\alpha({\mathcal{J}})}L_{i}({\mathcal{J}}\setminus\\{j\\})\psi({\mathcal{J}}\setminus\\{j\\})\Bigg{)},\end{aligned}$

if $i\in{\mathcal{J}}$. By following a similar reasoning as in the proof of
Property (14-a) and recalling that $\rho({\mathcal{J}})$ tends to one if
${\mathcal{J}}={\mathcal{I}}$ and to a constant strictly less than one if
${\mathcal{J}}\in{\mathbb{I}}\setminus\\{{\mathcal{I}}\\}$, we obtain

$\displaystyle L_{i}\underset{\rho\uparrow
1}{\sim}\frac{\frac{\rho}{1-\rho}\frac{\alpha_{i}}{\alpha({\mathcal{I}})}\psi({\mathcal{I}})}{\psi({\mathcal{I}})}.$

After simplification, we conclude by observing that (26) implies
$\alpha_{i}/\alpha({\mathcal{I}})=p_{i}$. If we consider instead
$i\in{\mathcal{V}}\setminus{\mathcal{I}}$, a similar reasoning shows that all
terms in the numerator of (30) have a finite limit, while its denominator
still tends to infinity, so that $L_{i}$ tends to zero as $\rho\uparrow 1$.
The limiting result for $L$ follows by summation, and that for
$\mathbb{E}\left[T_{i}\right]$, $i\in{\mathcal{V}}$, follows by applying
Little’s law and simplifying the result. ∎

###### Proof of Property (14-d).

Consider the random vector $S=(S_{1},S_{2},\ldots,S_{N})$ defined by

$\displaystyle S_{i}=\begin{cases}(1-\rho)X_{i},&i\in{\mathcal{I}},\\\
X_{i},&i\in{\mathcal{V}}\setminus{\mathcal{I}}.\end{cases}$

The Laplace-Stieltjes transform of this random vector is defined, for each
$u\in\mathbb{R}_{+}^{N}$, by

$\displaystyle\varphi_{S}(u)$
$\displaystyle=\mathbb{E}\left[\prod_{i\in{\mathcal{V}}}e^{-u_{i}S_{i}}\right]=\mathbb{E}\left[\left(\prod_{i\in{\mathcal{I}}}\mathrm{e}^{-u_{i}(1-\rho)X_{i}}\right)\left(\prod_{i\in{\mathcal{V}}\setminus{\mathcal{I}}}\mathrm{e}^{-u_{i}X_{i}}\right)\right]=\mathbb{E}\left[\prod_{i\in{\mathcal{V}}}{z_{i}}^{X_{i}}\right]=g_{X}(z),$

where the vector $z=(z_{1},z_{2},\ldots,z_{N})$ is given by
$z_{i}=\mathrm{e}^{-u_{i}(1-\rho)}$ for $i\in{\mathcal{I}}$ and
$z_{i}=\mathrm{e}^{-u_{i}}$ for $i\in{\mathcal{V}}\setminus{\mathcal{I}}$. We
will use Proposition 9 to show that this Laplace-Stieltjes transform satisfies

$\displaystyle\varphi_{S}(u)\xrightarrow[\rho\uparrow
1]{}\frac{1}{1+\sum_{i\in{\mathcal{I}}}p_{i}u_{i}}.$ (31)

One can verify that this is also the Laplace-Stieltjes transform of a random
vector $\tilde{S}=(\tilde{S}_{1},\tilde{S}_{2},\ldots,\tilde{S}_{N})$ such
that $\tilde{S}_{i}=\mathrm{Exp}(1)p_{i}$ for each $i\in{\mathcal{I}}$ and
$\tilde{S}_{i}=0$ for each $i\in{\mathcal{V}}\setminus{\mathcal{I}}$.
According to [15, Section 13.1, Theorem 2], this suffices to conclude that $S$
weakly converges to $\tilde{S}$ as $\rho\uparrow 1$.

By following a similar approach as in the proof of Properties (14-a) and
(14-c) and recalling that $z_{i}\uparrow 1$ if $i\in{\mathcal{I}}$ and
$z_{i}=e^{-u_{i}}<1$ if $i\in{\mathcal{V}}\setminus{\mathcal{I}}$, we obtain

$\displaystyle\varphi_{S}(u)\underset{\rho\uparrow
1}{\sim}\frac{\psi_{z\alpha,\alpha}({\mathcal{I}})}{\psi_{\alpha,\alpha}({\mathcal{I}})}.$

Using (18), we can rewrite the right-hand side of this equivalence as

$\displaystyle\frac{\psi_{z\alpha,\alpha}({\mathcal{I}})}{\psi_{\alpha,\alpha}({\mathcal{I}})}=\frac{\displaystyle\frac{\sum_{i\in{\mathcal{I}}}z_{i}\alpha_{i}\psi_{z\alpha,\alpha}({\mathcal{I}}\setminus\\{i\\})}{\alpha({\mathcal{V}}\setminus{\mathcal{I}})-(z\alpha)({\mathcal{I}})}}{\displaystyle\frac{\sum_{i\in{\mathcal{I}}}\alpha_{i}\psi_{\alpha,\alpha}({\mathcal{I}}\setminus\\{i\\})}{\alpha({\mathcal{V}}\setminus{\mathcal{I}})-\alpha({\mathcal{I}})}}=\frac{\sum_{i\in{\mathcal{I}}}z_{i}\alpha_{i}\psi_{z\alpha,\alpha}({\mathcal{I}}\setminus\\{i\\})}{\sum_{i\in{\mathcal{I}}}\alpha_{i}\psi_{\alpha,\alpha}({\mathcal{I}}\setminus\\{i\\})}\cdot\frac{1-\frac{\alpha({\mathcal{I}})}{\alpha({\mathcal{V}}\setminus{\mathcal{I}})}}{1-\frac{(z\alpha)({\mathcal{I}})}{\alpha({\mathcal{V}}\setminus{\mathcal{I}})}}.$
(32)

As $\rho\uparrow 1$, the first factor tends to $1$ because $z_{i}\uparrow 1$
for each $i\in{\mathcal{I}}$, while we can show with a Taylor series expansion
that the second factor tends to $(1+\sum_{i\in{\mathcal{I}}}p_{i}u_{i})^{-1}$.
This proves (31) and completes the proof. ∎

###### Proof of Property (14-f).

We will show that, for each $i\in{\mathcal{I}}$, we have

$\displaystyle\lim_{\rho\uparrow
1}\varphi_{(1-\rho)T_{i}}(u)\xrightarrow[\rho\uparrow
1]{}\frac{\frac{1}{2}}{\frac{1}{2}+u},\quad
i\in{\mathcal{I}},\quad\qquad\lim_{\rho\uparrow
1}\varphi_{T_{i}}(u)\xrightarrow[\rho\uparrow 1]{}1,\quad
i\in{\mathcal{V}}\setminus{\mathcal{I}}.$ (33)

We recognize the Laplace-Stieltjes transform of an exponentially-distributed
random variable with rate $\frac{1}{2}$ for $i\in{\mathcal{I}}$ and the
degenerate Laplace-Stieltjes transform of a constant random variable equal to
$0$ for $i\in{\mathcal{V}}\setminus{\mathcal{I}}$. The conclusion of the
proposition then again follows from [15, Section 13.1, Theorem 2].

First let $i\in{\mathcal{I}}$. According to Proposition 10, we have

$\displaystyle\varphi_{(1-\rho)T_{i}}(u)=\varphi_{T_{i}}((1-\rho)u)=g_{X}(z),$

where $z=(z_{1},z_{2},\ldots,z_{N})$ is given by
$z_{i}=1-(1-\rho)\frac{u}{\alpha_{i}}$ and $z_{j}=1$ for each
$j\in{\mathcal{V}}\setminus\\{i\\}$. Since $z_{i}\uparrow 1$ as $\rho\uparrow
1$, and by following a similar reasoning as in the proof of Property (14-d),
we obtain

$\displaystyle\varphi_{(1-\rho)T_{i}}(u)\underset{\rho\uparrow
1}{\sim}\frac{\psi_{z\alpha,\alpha}({\mathcal{I}})}{\psi_{\alpha,\alpha}({\mathcal{I}})}.$

The right-hand side of this equivalence is again given by (32). By using the
definition of $z$, we can show that the second factor in (32) simplifies to
$\alpha({\mathcal{V}}\setminus{\mathcal{I}})/(\alpha({\mathcal{V}}\setminus{\mathcal{I}})+u)$,
which tends to $\frac{1}{2}/(\frac{1}{2}+u)$ according to (33). Since we also
know that the first factor in (32) tends to $1$, this proves (33). The proof
for $i\in{\mathcal{V}}\setminus{\mathcal{I}}$ is similar, the main difference
being that we have directly
$\psi_{z\alpha,\alpha}({\mathcal{I}})=\psi_{\alpha,\alpha}({\mathcal{I}})$
because $i\notin{\mathcal{I}}$. ∎