<figure><img src="image_1.png" /></figure>

HAL
open science

# Performance Paradox of Dynamic Matching Models under Greedy Policies

Bušić Ana, Cadas Arnaud, Josu Doncel, Fourneau Jean-Michel

<figure><img src="image_2.png" /></figure>

## To cite this version:

Bušić Ana, Cadas Arnaud, Josu Doncel, Fourneau Jean-Michel. Performance Paradox of Dynamic Matching Models under Greedy Policies. 2023. hal-04137823

HAL Id: hal-04137823

https://hal.science/hal-04137823

Preprint submitted on 22 Jun 2023

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Performance Paradox of Dynamic Matching Models under Greedy Policies

Bušić Ana, Cadas Arnaud, Josu Doncel, Jean-Michel Fourneau

► To cite this version:

Bušić Ana, Cadas Arnaud, Josu Doncel, Jean-Michel Fourneau. Performance Paradox of Dynamic Matching Models under Greedy Policies. Queueing Systems, 2024, 107 (3-4), pp.257-293. 10.1007/s11134-024-09924-z. hal-04137823v2

HAL Id: hal-04137823

https://hal.science/hal-04137823v2

Submitted on 24 Jul 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Performance Paradox of Dynamic Matching Models under Greedy Policies

Bušić Ana<fnref n="1" />, Cadas Arnaud<fnref n="1" />, Doncel Josu<fnref n="2" />* and Fourneau Jean-Michel<fnref n="3" />

*Corresponding author(s). E-mail(s): josu.doncel@ehu.eus;

Contributing authors: ana.busic@inria.fr;

cadas.arnaud@gmail.com; jean-michel.fourneau@uvsq.fr;

## Abstract

We consider the stochastic matching model on a non-bipartite matching graph and analyze the impact of adding an edge to the expected number of items in the system. One may see adding an edge as increasing the flexibility of the system, for example asking a family registering for social housing to list less requirements in order to be compatible with more housing units. Therefore it may be natural to think that adding edges to the matching graph will lead to a decrease of the expected number of items in the system and the waiting time to be matched. In our previous work, and we proved this is not always true for the First Come First Matched discipline and provided sufficient conditions for the existence of the performance paradox: despite a new edge in the matching graph, the expected total number of items can increase. These sufficient conditions are related to the heavy-traffic assumptions in queueing systems. The intuition behind is that the performance paradox occurs when the added edge in the compatibility graph disrupts the draining of a bottleneck. In this paper, we generalize this performance paradox result to a family of so called greedy matching policies and explore the type of matching graphs where such paradoxes occur. Intuitively, a greedy matching policy never leaves compatible items unmatched, so the state space of the system consists of finite words of item classes that belong to an independent set of the matching graph. Some examples of greedy

<footnote n="1">¹INRIA, Paris, France. DI ENS, CNRS, PSL Research University, Paris, France.</footnote>

<footnote n="2">²University of the Basque Country, UPV-EHU, Leioa, Spain.</footnote>

<footnote n="3">³DAVID, UVSQ, Université Paris-Saclay, Versailles, France.</footnote>
# Performance Paradox of Dynamic Matching Models under Greedy Policies

Bušić Ana¹, Cadas Arnaud¹, Doncel Josu²* and Fourneau Jean-Michel³,⁴

¹INRIA ARGO, Paris, France. DI ENS, CNRS, PSL Research University, Paris, France.

²University of the Basque Country, UPV-EHU, Leioa, Spain.

³DAVID, UVSQ, Université Paris-Saclay, Versailles, France.

⁴INRIA ARGO, Paris, France.

*Corresponding author(s). E-mail(s): josu.doncel@ehu.eus;
Contributing authors: ana.busic@inria.fr;

cadas.arnaud@gmail.com; jean-michel.fourneau@uvsq.fr;

## Abstract

We consider the stochastic matching model on a non-bipartite compatibility graph and analyze the impact of adding an edge to the expected number of items in the system. One may see adding an edge as increasing the flexibility of the system, for example asking a family registering for social housing to list fewer requirements in order to be compatible with more housing units. Therefore it may be natural to think that adding edges to the compatibility graph will lead to a decrease in the expected number of items in the system and the waiting time to be assigned. In our previous work, we proved this is not always true for the First Come First Matched discipline and provided sufficient conditions for the existence of the performance paradox: despite a new edge in the compatibility graph, the expected total number of items can increase. These sufficient conditions are related to the heavy-traffic assumptions in queueing systems. The intuition behind this is that the performance paradox occurs when the added edge in the compatibility graph disrupts the draining of a bottleneck. In this paper, we generalize this performance paradox result to a family of so called greedy matching policies and explore the type of compatibility graphs where such a paradox occurs. Intuitively, a greedy matching policy never leaves compatible items unassigned, so the state space of
matching policies are First Come First Match, Match the Longest, Match the Shortest, Random selection, Priority. We prove several results about the existence of performance paradoxes for greedy disciplines for some family of graphs. More precisely, we prove several results about the lifting of the paradox from one graph to another one. For a certain family of graphs we prove that there exists a paradox for the whole family of greedy policies. Most of these results are based on Strong Aggregation of Markov chains and graph theoretical properties.

**Keywords:** Matching models, Performance Paradox, Strong Aggregation, Separable solutions

# 1 Introduction

Braess showed that adding resources to a transportation networks can hurt the performance of the system [2]. Many authors have been interested in investigating the existence of such a paradox in several contexts related to queueing networks (see for instance [3–7]). In this work, we analyze whether such a phenomenon is achieved in dynamic matching models where the compatibility graph is non-bipartite.

In our previous work [1], we analyze the performance of the stochastic First Come First Match, (FCFM in the following) matching model with a general compatibility graph when the flexibility increases, i.e when an edge is added to the compatibility graph. We show that increasing the flexibility can increase the overall performance of the system, which is reminiscent of the Braess paradox. In this paper, we generalize the results of our previous work by investigating the existence of the performance paradox for greedy matching policies (which include the FCFM policy). We show that for a certain family of graphs, any greedy policy exhibits the performance paradox. This can be seen as a Braess paradox for stochastic matching: for a given family of graphs, any greedy matching policy leads to overall performance decrease when we add an additional resource (i.e. an edge in our case).

The technical part of the paper is as follows. In section 2, we describe the model and we summarize the results obtained in [1]. We also study a simple example of a matching graph with 4 nodes such that the paradox exists for the FCFM (the quasi-complete graph and the complete graph). Due to this simple graph structures and some lumpability arguments, we were able to numerically compute the expectation of the total number of items in the system and find the intervals of arrival probabilities which lead to a performance paradox.

The existence of such a performance paradox leads to many questions we now try to address:

* First, is it only due to the FCFM discipline? Are other disciplines like Match the Longest or Random also prone to this phenomenon?
the system consists of finite words of item classes that belong to an
independent set of the compatibility graph. Some examples of greedy
matching policies are First Come First Match, Match the Longest,
Match the Shortest, Random, Priority. We prove several results about
the existence of performance paradoxes for greedy disciplines for some
family of graphs. More precisely, we prove several results about the
lifting of the paradox from one graph to another one. For a cer-
tain family of graphs we prove that there exists a paradox for the
whole family of greedy policies. Most of these results are based on
Strong Aggregation of Markov chains and graph theoretical properties.

**Keywords:** Matching models, Performance Paradox, Strong Aggregation, Separable solutions

# 1 Introduction

Braess showed that adding resources to transportation networks can hurt the performance of the system [1]. Many authors have been interested in investigating the existence of such a paradox in several contexts related to queueing networks (see for instance [2–6]). In this work, we analyze whether such a phenomenon exists in dynamic matching models where the compatibility graph is non-bipartite.

In our previous work [7], we analyzed the performance of the stochastic First Come First Match (FCFM) matching model with a general compatibility graph, when the flexibility increases, i.e. when an edge is added to the compatibility graph. We showed that, when there is a unique bottleneck in the system, increasing the flexibility can decrease the overall performance of the system, which is reminiscent of the Braess paradox. The existence of such a performance paradox leads to many questions:

* First, is it only due to the FCFM discipline? Are other disciplines like Match the Longest or Random also prone to this phenomenon? In this article, we develop some theoretical techniques to transfer the existence of a paradox from FCFM discipline to any greedy discipline (i.e. to any discipline where an arriving item must be assigned to a compatible item immediately if there is one). Most of the disciplines considered in the literature are shown to be greedy with the notable exception of the threshold disciplines studied in [8] and [9]. We first prove that all greedy disciplines exhibit the performance paradox for quasi-complete compatibility graphs. The results are proved using strong aggregation of Markov chains. Intuitively we prove that all the greedy disciplines are equivalent for quasi-complete compatibility graphs when we are interested in the total number of items. We then introduce two operations on compatibility graphs, the JOIN and the UNION. We show that if compatibility graph *G* associated with a greedy discipline satisfies the conditions for the existence a performance paradox, then the compatibility
* Is the paradox related to the matching graph? The result we proved in [1] are based on the Independent Set which is the main bottleneck of the system and a neighbor node of this set. This construction does not imply at first glance some constraints on the topology. But we are not able to analyze an arbitrary matching graph to find the expectation of total number of items. Indeed, even if we know that some models have a product form solution, it is rather difficult to find the normalization constant which remains necessary to compute the expected total number of items. Thus one may ask if some constraints on the size of the compatibility graph are necessary.

* Does the paradox only appear when we have only one bottleneck in the system (i.e. this is the technical condition of our main theorem in [1])? Is this condition only technical or is it mandatory?

To answer these questions, we develop some theoretical techniques to transfer the existence of a paradox from one discipline to any greedy discipline for the graph studied in Section 2. Then we provide other results to lift the paradox from one graph to a more complex graph which is built from the former one. We also give some examples of paradoxes.

To be more precise, in section 3, we give an abstract definition of many disciplines and we define greedy disciplines. Most of the disciplines considered in the literature are shown to be greedy with the notable exception of the threshold disciplines studied in [8] and [9]. Then we prove that all greedy disciplines exhibit performance paradox for quasi-complete matching graphs. The results are proved using strong aggregation of Markov chains. Intuitively we prove that all the greedy disciplines are equivalent for quasi-complete matching graph when we are interested in the total number of items. In Section 4, we introduce two operations on matching graphs, the JOIN (noted $▷$) and the UNION (noted $∪$). We prove that if the matching graph $G$ is build by the JOIN of subgraphs $G1$ and $G2$, then one can find the steady-state distribution from two sub-models based on $G1$ and $G2$. Section 4 is also devoted to two designs of matching graphs: $G1 \bowtie IS_n$ ($IS$ being an independent set with size $n$) and $G1 \bowtie (G2 \cup G3)$. For both constructions we prove a transfer result: if matching graph $G1$ associated with a greedy discipline satisfies the conditions of Theorem 2 that imply a performance paradox, then the matching graph $G1 \bowtie IS_n$ associated with the same discipline also satisfies the conditions of Theorem 2 and thus also exhibits a performance paradox.

## 1.1 Related Work

The model we consider in this work has been introduced in [10], where it is called general stochastic matching model to empathize that the matching graph is non-bipartite, and further studied in [11]. The works [10] and [11] present interesting properties of this model such as that the policies Match the Longest and FCFM disciplines have a maximal stability region. Recently, the author in [12] shows that this matching model with the FCFM discipline is related to the order-independent loss queueing networks. An extension of
graph $G \succ IN_n$ ($IN_n$ being a set of $n$ independent nodes) associated with
the same discipline also satisfies these conditions and thus also exhibits a
performance paradox.

* Is the paradox related to the size or the number of edges of the compatibility graph? An important conclusion of our work is that there exists a performance paradox for a compatibility graph with $n > 3$ nodes and $4n - 11$ edges. Therefore, the paradox can be obtained for any number of nodes or any number of edges.

* Does the paradox only appear when we have only one bottleneck in the system? Is this condition only technical or is it mandatory? In Section 2.4, we provide an example with two bottlenecks where the performance paradox exists. Therefore, the assumption on the uniqueness of the bottleneck is only a technical condition required to prove our previous result about the existence of the performance paradox.

## 1.1 Related Work

The model we consider in this work was introduced in [10], where it is called
general stochastic matching model to emphasize that the compatibility graph
is non-bipartite, and further studied in [11]. The works [10] and [11] present
interesting properties of this model such as that the policies Match the Longest,
in which the incoming item is matched with an item of the compatible class
with the longest queue size, and FCFM disciplines have a maximal stabil-
ity region. Recently, Comte shows that this matching model with the FCFM
discipline is related to the order-independent loss queueing networks [12]. An
extension of FCFM stochastic matching model to multigraphs with self-loops
has been studied in [13].

A related model to ours is the bipartite dynamic matching model. In this
model, the graph that determines compatibilities between items is bipartite
and, thus, the nodes can be separated in two disjoint sets: server nodes and
customer nodes. To the best of our knowledge, Kaplan [14] was the first ana-
lyzing the fully dynamic setting of matching model, i.e., all the items arrive
to the system according to a random process. He analyzed the problem of
how to assign public houses to tenants. In that work, it is considered that an
available public house is assigned to the longest waiting family among those
that expressed their interest for that house. The First Come First Served infi-
nite bipartite matching model, proposed by Caldentey et al. [15], considers
an infinite sequence of server nodes, independent and identically distributed
according to a probability distribution on the server classes, and an indepen-
dent infinite sequence of job items, independent and identically distributed
according to a probability distribution on the job classes. Busic et al [16] study
the stability of the system for different matching policies, whereas in [17] Gard-
ner and Righter study the relation between the bipartite matching model under
FCFM and the order-independent queues. Optimal matching policies of bipar-
tite matching models have been studied in an asymptotic regime in [8] and for
the N-shaped model in [9]. Weiss in [18] studies a bipartite matching model, in
4 Performance Paradox of Dynamic Matching Models under Greedy Policies

FCFM stochastic matching to multigraphs with self-loops has been studied in
[13].

A related model to ours is the bipartite dynamic matching model. In this model, the graph that determines compatibilities between items is bipartite and, thus, the nodes can be separated in two disjoint sets: server nodes and customer nodes. To the best of our knowledge, [14] was the first analyzing the fully dynamic setting of matching model, i.e., all the items arrive to the system according to a random process. He analyzed the problem of how to assign public houses to tenants. In that work, it is considered that an available public house is assigned to the longest waiting family among those that expressed their interest for that house. The First Come First Served infinite bipartite matching model, proposed by Caldentey et al. [15], considers an infinite sequence of server nodes, independent and identically distributed according to a probability distribution on the server classes, and an independent infinite sequence of job items, independent and identically distributed according to a probability distribution on the job classes. In [16], the authors proved that an alternative Markov description from [15] has a product form stationary distribution. The authors in [17] study the stability of the system for different matching policies. Optimal matching policies of bipartite matching models have been studied in an asymptotic regime in [8] and for the N-shaped model in [9]. The author in [18] studies a bipartite matching model, in which jobs and servers are matched according to the First Come First Served policy, but jobs are immediately lost if they do not find an available server upon arrival.

The impact of flexibility in redundancy networks has been analyzed in [19]. Their main result shows that providing more redundancy to a class leads to a performance improvement of this case but it might not beneficial for the other classes. The authors in [16] show that, under the heavy traffic assumption on the arrivals, the First Come First Served infinite bipartite matching model has the same stationary distribution as the First Come First Served-Assign the Longest Idle Server queueing model. Furthermore, the authors in [20] show that the First Come First Served-Assign the Longest Idle Server model has the same stationary distribution as the redundancy service model. Therefore, from the work of [19], one might conclude that the performance paradox existence analysis in dynamic matching models has been already carried out. However, we would like to remark that these works assume a bipartite matching graph and strongly depend on the product form result for First Come First Served discipline so they cannot be generalized to any greedy discipline.

2 Matching Model and Performance Paradox

We consider a queueing system with *n* classes of items. Items of different classes arrive to the system according to independent Poisson processes, with rates $\lambda_i > 0$, $i = 1, \dots, n$. The compatibilities between item classes are described by a connected non-bipartite compatibility graph $G = (V, \mathcal{E})$, where $V = \{1, \dots, n\}$ is the set of item classes and $\mathcal{E}$ is the set of allowed matching pairs:
4 Performance Paradox of Dynamic Matching Models under Greedy Policies

which jobs and servers are assigned according to the First Come First Served policy, but jobs are immediately lost if they do not find an available server upon arrival.

Adan and Weiss in [19] show that, under the heavy traffic assumption on the arrivals, the First Come First Served infinite bipartite matching model has the same stationary distribution as the First Come First Served-Assign the Longest Idle Server queueing model. Furthermore, Adan et al. in [20] show that the First Come First Served-Assign the Longest Idle Server model has the same stationary distribution as the redundancy service model. In the context of redundancy networks, the work of [21] shows that providing more flexibility to a class leads to a performance improvement of this class but it might not be beneficial for the other classes (the work of [22] shows that the Least Redundant First scheduling policy that is optimal with respect to overall system response time, can be unfair in that it can hurt the jobs that become redundant). Therefore, from the aforementioned works, one might conclude that the performance paradox existence analysis in dynamic matching models has been already carried out. However, we would like to remark that these works assume a bipartite compatibility graph (whereas in our work we consider non-bipartite matching dynamic models) and strongly depend on the product form result for First Come First Served discipline so they cannot be generalized to any greedy discipline.

## 1.2 Organization

The rest of the article is organized as follows. In Section 2, we present the model we study as well as the previous results on the existence of the performance paradox for FCFM. In Section 3, we focus on the greedy policies and we study the existence of the performance paradox for quasi-complete graphs. In Section 4, we consider the join operation on compatibility graphs and analyze the performance paradox for this instance. In Section 5, we present the main conclusions of our work as well as the future work.

# 2 Matching Model and Performance Paradox

We consider a queueing system with $n$ classes of items. Items of different classes arrive to the system according to independent Poisson processes, with rates $\lambda_i > 0, i = 1, ..., n$. The compatibilities between item classes are described by a connected non-bipartite compatibility graph $G = (V, E)$, where $V = \{1, ..., n\}$ is the set of item classes and $E$ is the set of allowed compatible pairs: items of classes $i$ and $j$ are compatible if and only if $(i, j) \in E$. If an incoming item is incompatible with all items present in the system, it is placed at the end of the queue of unassigned items. If it is compatible, and if policies are not restricted to be greedy, the controller has the option of not matching it to one of the compatible items, in which case it is also added to the end of the queue. If a compatible item is matched (or assigned) to the incoming item, both items disappear.
items of classes i and j are compatible if and only if $(i, j) \in \mathcal{E}$. If an incoming item is compatible with one item present in the system, both items can be matched, in which case they disappear. Otherwise, the incoming item is placed at the end of the queue of unmatched items.

For a class $i \in V$, we denote by $\Gamma(i) = \{j \in V : (i, j) \in \mathcal{E}\}$ the set of item classes that are compatible with class i, i.e the set of all the neighbors of the node i in the compatibility graph G. For any subset of item classes $V1 \subseteq V$, let $\Gamma(V1) = \bigcup_{i \in V1} \Gamma(i)$, and $|\lambda_{V1}| = \sum_{i \in V1} \lambda_i$.

To more easily describe the models based on composition of matching graphs (see Section 4), we present the models in continuous time. Indeed it is easier to use race condition on continuous-time models to represent the interaction of items (see for instance [21] for an example on the compositions of stochastic automata). Therefore we describe the models in continuous time, we uniformize them and we analyze the discrete-time models using strong aggregation of DTMC and the existence of paradox is proved for discrete time models.

## 2.1 Markov Representation

Let $\mathcal{V}^*$ be the set of finite words over the alphabet V and we denote the empty word by $\emptyset$. Let

$$ \mathcal{W} = \{w = w_1 \cdots w_q \in \mathcal{V}^* : \forall (i, j) \in [1, q]^2, i \neq j, (w_i, w_j) \notin \mathcal{E}\} $$

be the subset of words without a compatible pair of letters, i.e. the set of ordered independent sets of G. For any $w \in \mathcal{W}$ and any $x \in V$, let $|w|_x$ be the number of occurrences of letter $x$ in word $w$. Let $|w|$ be the length of $w$ (i.e., the number of letters of the word $w$).

A state of the system right after the new arrival (if any) has been matched or placed in the queue of unmatched items can be described by a word $w \in \mathcal{W}$. Each letter $w_i \in V$ represents the class of an unmatched item waiting in the system and the order of the letters represents their order of arrival.

Let us present some notation that we will use throughout the paper. Let $M(G, \lambda, D)$ be the continuous-time Markov chain associated with matching graph G, matching discipline D and arrival rates of letters $\lambda$. Let $\mathbb{E}[M(G, \lambda, D)]$ be the expectation of the total number of letters for this Markov chain. $K_n$ will be a complete graphs with $n$ nodes, $IS_n$ will be an independent set with $n$ nodes (i.e. $n$ nodes without edges). $K_n - (a, b)$ will denote the complete graph with $n$ nodes without edge $(a, b)$: it is called a quasi-complete graph in this paper.

**Proposition 1** In the models under consideration, the continuous-time Markov chain that represents the number of unmatched items is uniformizable. Indeed $\sum_i \lambda_i < \infty$.
For a class $i \in V$, we denote by $\Gamma(i) = \{j \in V : (i,j) \in \mathcal{E}\}$ the set of all the neighbors of the node $i$ in the compatibility graph $G$, i.e., if $j \in \Gamma(i)$ items of class $i$ are compatible with items of class $j$. For any subset of item classes $V_1 \subseteq V$, let $\Gamma(V_1) = \bigcup_{i \in V_1} \Gamma(i)$, and $\lambda_{V_1} = \sum_{i \in V_1} \lambda_i$. A subset of nodes $\mathcal{I} \subseteq V$ is called an *independent set* if there is no edge between any two nodes in $\mathcal{I}$, i.e. for any $i, j \in \mathcal{I}$, $(i, j) \notin \mathcal{E}$.

## 2.1 Markov Representation for Greedy Policies

Let $\mathcal{V}^*$ be the set of finite words over the alphabet $V$ and we denote the empty word by $\emptyset$. Let

$$ \mathcal{W} = \{w = w_1 \cdots w_q \in \mathcal{V}^* : \forall (i, j) \in [1, q]^2, i \neq j, (w_i, w_j) \notin \mathcal{E}\} $$

be the subset of words without a compatible pair of letters, i.e. the set of ordered independent sets of $G$. For any $w \in \mathcal{W}$ and any $x \in V$, let $|w|_x$ be the number of occurrences of letter $x$ in word $w$. Let $|w|$ be the length of $w$ (i.e., the number of letters of the word $w$). A word containing only letters $i$ will be denoted by $i^*$.

In a greedy policy, a unique compatible item is matched with the incoming one and both disappear (a formal definition of greedy policies will be presented in Section 3). Under a greedy policy, a state of the system right after the new arrival (if any) has been assigned or placed in the queue of unassigned items can be described by a word $w \in \mathcal{W}$. Each letter $w_i \in V$ represents the class of an unassigned item waiting in the system and the order of the letters represents their order of arrival.

Let us present some notation that we will use throughout the paper. Let $M(G, \lambda, D)$ be the continuous-time Markov chain associated with compatibility graph $G$, matching discipline $D$ and arrival rates of letters $\lambda$. Let $\mathbb{E}[M(G, \lambda, D)]$ be the expectation of the total number of letters for this Markov chain in steady-state. Let $K_n$ be a complete graph with $n$ nodes and $\mathit{IN}_n$ be a set with $n$ independent nodes (i.e. $n$ nodes without edges). Similarly, $G - (a, b)$ denotes the subgraph of $G$ where edge (a,b) has been deleted. Let $K_n - (a, b)$ denote the complete graph with $n$ nodes without edge $(a, b)$: it is called a quasi-complete graph in this paper.

After applying standard uniformization technique, with a uniformization constant $\Lambda > \sum_{i=1}^n \lambda_i$, we obtain a matching model in discrete time. In each time slot $t \in \mathcal{N}$, one item arrives to the system with probability $1 - \alpha_0$, and there are no arrivals with probability

$$ \alpha_0 = 1 - \frac{\|\lambda\|_1}{\Lambda} > 0. $$

Thus each item belongs to a class within the set of item classes sampled from a conditional probability distribution over $V$ given the event that there is
6 Performance Paradox of Dynamic Matching Models under Greedy Policies

After applying standard uniformization technique, with a uniformization constant $\Lambda > \sum_{i=1}^{n} \lambda_i$, we obtain a matching model in discrete time. In each time slot $t \in N$, one item arrives to the system with probability $1 - \alpha_0$, and there are no arrivals with probability

$$ \alpha_0 = 1 - \frac{1}{\Lambda} \sum_{i=1}^{n} \lambda_i > 0. $$

Thus each item belongs to a class within the set of item classes sampled from a conditional probability distribution over $V$ given the event that there is an arrival: $\alpha = (\alpha_1, \dots, \alpha_n)$, with $\alpha_i = \frac{\lambda_i}{\sum_{i=1}^{n} \lambda_i}$, $\forall 1 \le i \le n$. It follows that $\alpha_i > 0, \forall i$.

$\mathbb{E}[M(G, \alpha, D)]$ will denote the expectation of the total number of letters for this discrete-time Markov chain with arrival probabilities $\alpha$.

A subset of nodes $\mathcal{I} \subseteq V$ is called an *independent set* if there is no edge between any two items in $\mathcal{I}$, i.e. for any $i, j \in \mathcal{I}$, $(i, j) \notin \mathcal{E}$. Let $\mathbb{I}$ be the set of independent sets of $G$. We assume that

$$ |\alpha_{\mathcal{I}}| < |\alpha_{\Gamma(\mathcal{I})}|, \quad \forall \mathcal{I} \in \mathbb{I}. \qquad (1) $$

According to [10, Proposition 2], the above condition is a necessary condition for any matching policy to be stable. Thus if the compatibility graph is bipartite, the system is not stable, see [10]). Throughout the paper, we assume that the final compatibility graph is not bipartite, even if we consider bipartite graph as subgraphs.

For any $\mathcal{I} \in \mathbb{I}$, denote by $\Delta_{\mathcal{I}} = |\alpha_{\Gamma(\mathcal{I})}| - |\alpha_{\mathcal{I}}|$. In the following $\Delta_{\mathcal{I}}$ is called the stability gap of independent set $\mathcal{I}$.

## 2.2 Performance Paradox for First Come First Match Discipline

We say that there exists a performance paradox for matching graph $G$ and discipline $D$ if there exists an edge $(i^*, j^*)$ such that

$$ \mathbb{E}[M(G, \alpha, D)] > \mathbb{E}[M(G - (i^*, j^*), \alpha, D)] \qquad (2) $$

that is, if the mean number of items can be increased by adding an edge to the compatibility graph.

The number of classes determines the number of nodes of the matching graph. Hence, the matching graphs we consider in this article are formed by, at least, four nodes. Clearly, all the connected matching graphs with less than four nodes are complete or bipartite (see Fig. 1).

Let us now show the link with our previous results [1]. We first present some notation to understand the main result of this section.
6 Performance Paradox of Dynamic Matching Models under Greedy Policies

an arrival: $\alpha = (\alpha_1, \dots, \alpha_n)$, with $\alpha_i = \frac{\lambda_i}{\|\lambda\|_1}$, $\forall 1 \le i \le n$. It follows that $\alpha_i > 0, \forall i$.

$\mathbb{E}[M(G, \alpha, D)]$ will denote the expectation of the total number of letters for this discrete-time Markov chain with arrival probabilities $\alpha$.

Let $\mathbb{I}$ be the set of independent sets of $G$. We assume that

$$ \alpha_{\mathbb{I}} < \alpha_{\Gamma(\mathbb{I})}, \quad \forall \mathbb{I} \in \mathbb{I}. \qquad (1) $$

According to [10, Proposition 2], the above condition is a necessary condition for any matching policy to be stable. As a consequence, if the compatibility graph is bipartite, the system is not stable, see [10]. Therefore, throughout the paper, we assume that the compatibility graph is not bipartite, even if we consider bipartite graphs as subgraphs. We also assume the compatibility graph has at least four nodes, to eliminate trivial cases.

For any $\mathbb{I} \in \mathbb{I}$, let $\Delta_{\mathbb{I}} = \alpha_{\Gamma(\mathbb{I})} - \alpha_{\mathbb{I}}$ be the stability gap of independent set $\mathbb{I}$.

We summarize the notation of this work in Table 1.

<table><caption>**Table 1:** A summary of the main notation.</caption><thead><tr><th>Symbol</th><th>Notation</th></tr></thead><tbody><tr><td>G</td><td>Compatibility graph</td></tr><tr><td>G &minus; (a, b)</td><td>Subgraph of G in which we remove the edge (a,b)</td></tr><tr><td>V = {1, . . . , n}</td><td>Set of item classes</td></tr><tr><td>&lambda;<sub>i</sub></td><td>Arrival rate of jobs of class i</td></tr><tr><td>&alpha;<sub>i</sub></td><td>Arrival probability of jobs of class i</td></tr><tr><td>w</td><td>A word over the alphabet V</td></tr><tr><td>x &isin; V</td><td>An arbitrary letter</td></tr><tr><td>&Gamma;(x)</td><td>The set of compatible items with x</td></tr><tr><td>D</td><td>An arbitrary matching discipline</td></tr><tr><td>M(G, &lambda;, D)</td><td>The Markov chain of graph G, vector of arrivals &lambda; and matching discipline D</td></tr></tbody></table>

## 2.2 Performance Paradox Analysis of [7]

We say that there exists a performance paradox for compatibility graph $G$ and discipline $D$ if there exists an edge $(a, b)$ such that

$$ \mathbb{E}[M(G, \alpha, D)] > \mathbb{E}[M(G - (a, b), \alpha, D)] \qquad (2) $$

that is, if the mean number of items increases by adding an edge to the compatibility graph.

Let us now recall our previous results [7]. We first present some notation to understand the main result of this section.

**Definition 1** (Bottleneck) A set $\mathbb{I} \in \text{argmin}_{\mathbb{I} \in \mathbb{I}} \Delta_{\mathbb{I}}$ will be called a *bottleneck set* in the sense that it has the smallest maximal draining speed.
<figure><img src="image_4.png" /><figcaption>**Fig. 1** All the connected compatibility graphs with less than four nodes are complete or bipartite.</figcaption></figure>

**Definition 1** (Bottleneck) A set $\mathcal{I} \in \text{argmin}_{\mathcal{I} \in \mathbb{I}} \Delta_{\mathcal{I}}$ will be called a bottleneck set in the sense that it has the smallest maximal draining speed.

Let

$$ \bar{\delta} = \min_{\mathcal{I} \in \mathbb{I}} \Delta_{\mathcal{I}} = \min_{\mathcal{I} \in \mathbb{I}} (|\alpha_{\Gamma(\mathcal{I})}| - |\alpha_{\mathcal{I}}|). \qquad (3) $$

We have $\bar{\delta} > 0$ as we assume that $\alpha$ satisfies (1). We select a bottleneck set (or saturated independent set) $\hat{\mathcal{I}} \in \text{argmin}_{\mathcal{I} \in \mathbb{I}} \Delta_{\mathcal{I}}$ with the highest cardinality, i.e.

$$ |\hat{\mathcal{I}}| = \max_{\mathcal{I} \in \mathbb{I} \text{ s.t. } \Delta_{\mathcal{I}} = \bar{\delta}} |\mathcal{I}|. \qquad (4) $$

We are interested in how the performance of the system evolves by adding an edge when $\Delta_{\hat{\mathcal{I}}}^-$ tends towards 0. First, we define a parameterized family of item class distributions:

$$ \alpha_i^{\delta} = \begin{cases} \alpha_i + \frac{\bar{\delta}}{2} \frac{\alpha_i}{|\alpha_{\hat{\mathcal{I}}}|} - \frac{\delta}{2} \frac{\alpha_i}{|\alpha_{\hat{\mathcal{I}}}|} & \text{if } i \in \hat{\mathcal{I}} \\ \alpha_i - \frac{\bar{\delta}}{2} \frac{\alpha_i}{|\alpha_{\Gamma(\hat{\mathcal{I}})}|} + \frac{\delta}{2} \frac{\alpha_i}{|\alpha_{\Gamma(\hat{\mathcal{I}})}|} & \text{if } i \in \Gamma(\hat{\mathcal{I}}) \\ \alpha_i & \text{otherwise} \end{cases} $$

for all $0 < \bar{\delta} \le \bar{\delta}$, where $\bar{\delta}$ is defined in (3) and $\hat{\mathcal{I}}$ in (4). It is clear that $\alpha^{\bar{\delta}} = \alpha$. By definition of $\alpha^{\delta}$,

$$ |\alpha_{\Gamma(\hat{\mathcal{I}})}^{\delta}| - |\alpha_{\mathcal{I}}^{\delta}| = |\alpha_{\Gamma(\hat{\mathcal{I}})}| - \frac{\bar{\delta}}{2} + \frac{\delta}{2} - |\alpha_{\hat{\mathcal{I}}}| - \frac{\bar{\delta}}{2} + \frac{\delta}{2} = \bar{\delta} - \bar{\delta} + \delta = \delta, $$

which tends to 0 when $\bar{\delta}$ tends to 0.

We now consider the expectations of the total number of items for both models as a function of $\bar{\delta}$ and analyze their difference when $\bar{\delta}$ tends to 0.

**Definition 2** (Saturated Independent Set) An independent set $\mathcal{I}$ is called saturated if $\Delta_{\mathcal{I}}^{\delta} = |\alpha_{\Gamma(\mathcal{I})}^{\delta}| - |\alpha_{\mathcal{I}}^{\delta}|$ tends to 0 when $\bar{\delta}$ tends to 0.

In our previous work [1], for technical reasons, we assume there is only one saturated independent set $\hat{\mathcal{I}}$. We now focus on the existence of a performance paradox. In Section 2.4. we show that, under FCFM, a performance paradox
Let

$$ \bar{\delta} = \min_{\mathcal{I} \in \mathcal{I}} \Delta_{\mathcal{I}} = \min_{\mathcal{I} \in \mathcal{I}} (\alpha_{\Gamma(\mathcal{I})} - \alpha_{\mathcal{I}}). \quad (3) $$

We have $\bar{\delta} > 0$ as we assume that $\alpha$ satisfies (1). We select a bottleneck set (or saturated independent set) $\hat{\mathcal{I}} \in \argmin_{\mathcal{I} \in \mathcal{I}} \Delta_{\mathcal{I}}$ with the highest cardinality, i.e.

$$ |\hat{\mathcal{I}}| = \max_{\mathcal{I} \in \mathcal{I} \text{ s.t. } \Delta_{\mathcal{I}} = \bar{\delta}} |\mathcal{I}|. \quad (4) $$

We are interested in how the performance of the system evolves by adding an edge when $\Delta_{\hat{\mathcal{I}}}^\delta$ tends towards 0. First, we define a parameterized family of item class distributions:

$$ \alpha_i^\delta = \begin{cases} \alpha_i + \frac{\bar{\delta}}{2} \frac{\alpha_i}{|\alpha_{\hat{\mathcal{I}}}^\delta|} - \frac{\delta}{2} \frac{\alpha_i}{|\alpha_{\hat{\mathcal{I}}}^\delta|}, & \text{if } i \in \hat{\mathcal{I}}, \\ \alpha_i - \frac{\bar{\delta}}{2} \frac{\alpha_i}{|\alpha_{\Gamma(\hat{\mathcal{I}})}|} + \frac{\delta}{2} \frac{\alpha_i}{|\alpha_{\Gamma(\hat{\mathcal{I}})}|}, & \text{if } i \in \Gamma(\hat{\mathcal{I}}), \\ \alpha_i, & \text{otherwise,} \end{cases} $$

for all $0 < \delta \le \bar{\delta}$, where $\bar{\delta}$ is defined in (3) and $\hat{\mathcal{I}}$ in (4). It is clear that $\alpha^\delta = \alpha$. By definition of $\alpha^\delta$,

$$ \alpha_{\Gamma(\hat{\mathcal{I}})}^{\delta} - \alpha_{\hat{\mathcal{I}}}^{\delta} = \alpha_{\Gamma(\hat{\mathcal{I}})} - \frac{\bar{\delta}}{2} + \frac{\delta}{2} - \alpha_{\hat{\mathcal{I}}} - \frac{\bar{\delta}}{2} + \frac{\delta}{2} = \bar{\delta} - \bar{\delta} + \delta = \delta, $$

which tends to 0 when $\delta$ tends to 0.

We now consider the expectations of the total number of items for the models both with and without edge as a function of $\delta$ and analyze their difference when $\delta$ tends to 0.

**Definition 2** (Saturated Independent Set) An independent set $\mathcal{I}$ is called saturated if $\Delta_{\mathcal{I}}^\delta = \alpha_{\Gamma(\mathcal{I})}^\delta - \alpha_{\mathcal{I}}^\delta$ tends to 0 when $\delta$ tends to 0.

In our previous work [7], we assume there is only one saturated independent set $\hat{\mathcal{I}}$.

**Theorem 1** [Adapted from Theorem 2 of [7]] If $\hat{\mathcal{I}}$ is uniquely defined for graph G, and if $\hat{\mathcal{I}}$ has both a and b as neighbors, then there exists a performance paradox for adding the edge (a, b) to G for $\delta$ sufficiently small.

We would like to emphasize that the assumption about the uniqueness of the saturated independent set is a technical condition required to prove the existence of a performance paradox. As we will see in Section 2.4. the performance paradox also occurs when this assumption does not hold.
exists when the saturated independent set is a neighbor of the nodes of the added edge.

**Theorem 1** [Adapted from Theorem 2 of [1]] If $\hat{\mathcal{I}}$ is uniquely defined, and if $\hat{\mathcal{I}}$ has both $i^*$ and $j^*$ as neighbors, then there exists a performance paradox for $\delta$ sufficiently small.

We provide the full proof in the Appendix ?? as [1] was a short paper and did not contain the complete proof.

## 2.3 An example of Performance Paradox

In the following, we provide an example in which we can establish the exact value of $\delta$ for the performance paradox to occur. The example is based on a matching model formed by a quasi-complete graph with four nodes (denoted as $K_4 - (3,4)$) (see Fig. 2). We also consider the graph where we add edge (3,4) (i.e. complete graph $K_4$). Therefore all the nodes different from $n-1$ and $n$ are independent sets that are connected to these nodes.

<figure><img src="image_5.png" /><figcaption>**Fig. 2** Quasi-complete compatibility graph with 4 nodes: $K_4 - (3,4)$.</figcaption></figure>

We consider the following conditional probability distribution of arrivals: $\alpha_1 = 0.45$, $\alpha_2 = 0.11$ and $\alpha_3 = \alpha_4 = 0.22$. For this instance, the saturated independent set is $\hat{\mathcal{I}} = \{1\}$ with $\bar{\delta} = |\alpha_{\{2,3,4\}}| - |\alpha_1| = 0.1$. We define a new collection of conditional probability distributions $\alpha^\delta$ for all $0 < \delta \le 0.1$, i.e $\alpha_1^\delta = 0.5 - \frac{\delta}{2}$, $\alpha_2^\delta = 0.1 + \frac{\delta}{10}$ and $\alpha_3^\delta = \alpha_4^\delta = 0.2 + \frac{\delta}{5}$. Since the saturated independent set has the nodes that connect the missing edge as neighbors (i.e., the node 1 is a neighbor of node 3 and node 4), we know from Theorem 1 that there exists a performance paradox for $\delta$ sufficiently small.

We study the exact value of the saturation threshold, i.e. the maximum $\delta$ value for the existence of the paradox under the FCFM policy. According to Lemma 3 and Lemma 6 (in the next section as they are proved for any greedy policy) we can conclude that, for FCFM policy, for the matching model under consideration here, the performance paradox exists if and only if $\delta < 0.0818369$. All the details of the computations are presented in Appendix A.
## 2.3 An Example of Performance Paradox

In the following, we provide an example in which we can establish the exact value of $\delta$ for the performance paradox to occur. The example is based on a matching model formed by a quasi-complete graph with four nodes (denoted as $K_4 - (3, 4)$) (see Fig. 1). We also consider the graph where we add edge (3, 4) (i.e. complete graph $K_4$). Therefore each node different from 3 and 4 is an independent set that is connected to these nodes.

<figure><img src="image_2.png" /><figcaption>Fig. 1: Quasi-complete compatibility graph with 4 nodes: $K_4 - (3, 4)$.</figcaption></figure>

We consider the following conditional probability distribution of arrivals: $\alpha_1 = 0.45$, $\alpha_2 = 0.11$ and $\alpha_3 = \alpha_4 = 0.22$. For this instance, the saturated independent set is $\hat{\mathcal{I}} = \{1\}$ with $\bar{\delta} = \alpha_{\{2,3,4\}} - \alpha_1 = 0.1$. We define a new collection of conditional probability distributions $\alpha^\delta$ for all $0 < \delta \le 0.1$, i.e. $\alpha_1^\delta = 0.5 - \frac{\delta}{2}$, $\alpha_2^\delta = 0.1 + \frac{\delta}{10}$ and $\alpha_3^\delta = \alpha_4^\delta = 0.2 + \frac{\delta}{5}$. Since the saturated independent set has the nodes that connect the missing edge as neighbors (i.e., the node 1 is a neighbor of node 3 and node 4), we know from Theorem 1 that there exists a performance paradox for $\delta$ sufficiently small.

We study the exact value of the saturation threshold, i.e. the maximum $\delta$ value for the existence of the paradox under the FCFM policy. According to Lemma 1 and Lemma 4 (which are presented in the next section as they are proved for any greedy policy) we can conclude that, for FCFM policy, for the matching model under consideration here, the performance paradox exists if and only if $\delta < 0.0818369$. All the details of the computations as well as a plot representing the mean number of items of both matching models when $\delta$ varies are presented in Appendix A.2.

## 2.4 An Example With Multiple Saturated Independent Sets

The definition of the parametrized $\alpha^\delta$ implies that the unique saturated independent set is $\hat{\mathcal{I}}$. We now discuss the situation where there are multiple saturated independent sets. This means that multiple independent sets have their stability gaps that tend to 0 as $\delta$ tends to 0. In that case, the conditions of Theorem 1 in [7] are not satisfied. However, in this section, we present an
## 2.4 Multiple Saturated Independent Sets

The definition of the parametrized $\alpha^\delta$ implies that the unique saturated independent set is $\hat{\mathcal{I}}$. We now discuss the situation where there are multiple saturated independent sets. This means that multiple independent sets have their stability gap which tends to 0 as $\delta$ tends to 0. In that case, the proof of Theorem 1 in [1] fails because we cannot prove the existence of a strictly positive (or strictly negative) constant at the numerator when we rewrite the difference in expectation as a rational fraction of $\delta$. However, in this section, we present an example with two saturated independent sets where the performance paradox exists.

Again we consider compatibility graph $K_4$ and $K_4-(3, 4)$. Let us define the conditional probability distribution of the arrivals as $\alpha_1 = \alpha_2 = 0.15$, $\alpha_3 = 0.4$ and $\alpha_4 = 0.3$. We choose the saturated independent sets to be $\{3\}$ and $\{1, 2\}$. We define a new parametrized family of conditional probability distributions $\alpha^\delta$, for all $0 < \delta \le 0.1$, as $\alpha_1^\delta = \alpha_2^\delta = 0.25 - \delta$, $\alpha_3^\delta = 0.5 - \delta$ and $\alpha_4^\delta = 0. + 3\delta$. We prove that there exists a performance paradox and compute exactly for which value of $\delta$ it appears. The proof is available in Appendix B.

**Proposition 2** For the dynamic matching model under consideration, there exists a performance paradox if and only if $\delta \in (0, 0.0563)$.

We conclude from the previous proof that the difference $\mathbb{E}[M(K_4, \alpha^\delta, FCFM)] - \mathbb{E}[M(K_4 - (3, 4), \alpha^\delta, FCFM)]$ is unbounded as $\delta$ tends to 0. In the following result, we quantify its growth rate. The proof is available in Appendix C.

**Proposition 3** When $\delta$ tends to 0,

$$ \delta(\mathbb{E}[M(K_4, \alpha^\delta, FCFM)] - \mathbb{E}[M(K_4 - (3, 4), \alpha^\delta, FCFM)]) \rightarrow \frac{1}{24}. $$

*Remark 1* This example shows that the existence of the paradox is not related to the uniqueness of a saturated independent set. This was a technical condition used to prove Theorem 1 in [1].

## 3 Greedy Matching Disciplines

In the following, $m$ will be a word (or a sequence of letters), $x$ will be a letter, $\Gamma(x)$ is the neighbor of $x$ in the matching graph, $\Gamma(m) = \cup_{x \in m} \Gamma(x)$. $S$ is the set of states and $V$ the set of letters.

**Definition 3** (Matching) Let $m$ be a state of the system and $x$ a letter which arrives in the system. We say that $x$ matches with $m$ if $x \in \Gamma(m)$.
example with two saturated independent sets where the performance paradox exists.

Now we consider compatibility graph $K_4$ and $K_4 - (1, 2)$. Let us define the conditional probability distribution of the arrivals as $\alpha_1 = \alpha_2 = 0.15$, $\alpha_3 = 0.4$ and $\alpha_4 = 0.3$. We choose the saturated independent sets to be $\{3\}$ and $\{1, 2\}$. We define a new parametrized family of conditional probability distributions $\alpha^\delta$, for all $0 < \delta \le 0.1$, as $\alpha_1^\delta = \alpha_2^\delta = 0.25 - \delta$, $\alpha_3^\delta = 0.5 - \delta$ and $\alpha_4^\delta = 3\delta$. In the following result, we prove that there exists a performance paradox and compute exactly for which value of $\delta$ it appears. Its proof is available in Appendix B.1.

**Proposition 1** For the dynamic matching model under consideration, there exists a performance paradox if and only if $\delta \in (0, 0.0563)$.

A plot representing the number of items of the matching models under study as a function of $\delta$ is represented in Appendix B.2. In the following result, we show that the difference $\mathbb{E}[M(K_4, \alpha^\delta, FCFM)] - \mathbb{E}[M(K_4 - (1, 2), \alpha^\delta, FCFM)]$ is unbounded as $\delta$ tends to 0 and we quantify its growth rate. Its proof is available in Appendix B.3.

**Proposition 2** When $\delta$ tends to 0,

$$ \delta(\mathbb{E}[M(K_4, \alpha^\delta, FCFM)] - \mathbb{E}[M(K_4 - (1, 2), \alpha^\delta, FCFM)]) \rightarrow \frac{1}{24}. $$

*Remark 1* This example shows that the existence of the paradox is not related to the uniqueness of a saturated independent set. This was only a technical condition used to prove Theorem 1 in [7].

# 3 Greedy Matching Disciplines

In the following, we denote by $\Gamma(w) = \cup_{x \in w} \Gamma(x)$ for any word $w$ and by $S$ the set of words. Let us first present some definitions.

**Definition 3** (Compatibility) Let $w$ be a state of the system and $x$ a letter which arrives in the system. We say that $x$ is compatible with $w$ if $x \in \Gamma(w)$.

Remember that a subsequence of a word (or a sequence of letters) $w$ is derived from $w$ by deleting some or no letters without changing the order. Subsequences can contain consecutive letters which were not consecutive in the original word. Thus subsequences are not necessarily substrings.

**Definition 4** (Effect of a compatibility) Let $w$ be a state of the system and $x$ a letter which arrives in the system. If $x$ is not compatible with $w$, it is appended at
10 Performance Paradox of Dynamic Matching Models under Greedy Policies

Remember that a subsequence of a word (or a sequence of letters) m is derived from m by deleting some or no letters without changing the order. Subsequence can contain consecutive letters which were not consecutive in the original word. Thus subsequences are not necessarily substrings.

**Definition 4** (Effect of a matching) Let $m$ be a state of the system and $x$ a letter which arrives in the system, if there is no matching, letter $x$ is appended at the end of word $m$. Otherwise, there is a matching and the matching discipline will explain the possible transitions and their respective probability.

**Definition 5** (Matching discipline) Let $m$ be a state of the system and $x$ a letter which arrives in the system and matches with the word $m$. A matching discipline $D$ is a function from $S \times V$ which returns a non empty subset of states $N_D(m, x)$ and a discrete distribution of probability $\psi_{N_D(m, x)}$ on this subset such that:

1. All the words in $N_D(m, x)$ are subsequences of $m$

2. The distribution gives the probability to make a transition to any state in $N_D(m, x)$: $\alpha_x \psi_{N_D(m, x)}(p)$ is the probability to jump from state $m$ to any state $p$ in $N_D(m, x)$, due to the arrival of an item of type $x$. Of course, we have:

$$ \sum_{p \in N_D(m, x)} \psi_{N_D(m, x)}(p) = 1 $$

Of course if the set $N_D(m, x)$ is a singleton, the distribution of probability is a Dirac.

*Remark 2* This definition allows to model disciplines where $N_D(m, x) = \{m\}$ (i.e. the matching has no effect on word $m$ even when $x$ matched a letter in $m$, for instance for a threshold based discipline where the deletion only occurs for long words). It is also possible to represent disciplines where the effect of a matching is to remove all the letters in $m$ which match with letter $x$. It is why we now introduce the notion of greedy matching discipline.

**Definition 6** (Greedy matching discipline) A matching discipline GD is greedy if for $m$ being a state of the system and $x$ a letter which arrives in the system such that $x \in \Gamma(m)$, for all state $p$ in $N_{GD}(m, x)$, we have $|p| = |m| - 1$,

*Example 1* Clearly, FCFM is a greedy discipline such that the set $N_D(m, x)$ is a singleton for all word $m$ and matching letter $x$. Match the Longest with random drawing of ties is a greedy discipline but the set $N_D(m, x)$ may contain several words.

**Definition 7** (RANDOM discipline) Assuming that a word and a letter match, we delete one matching letter in the word. And this letter is chosen with an uniform distribution among the matching letters.
10 Performance Paradox of Dynamic Matching Models under Greedy Policies

the end of word w. Otherwise, if x is compatible with w, the transition is described by the matching discipline.

**Definition 5** (Matching discipline) Let $x \in \Gamma(w)$. A matching discipline $D$ is a function from $S \times V$ which returns a non empty subset of states $N_D(w, x)$ and a discrete distribution of probability $\psi_{N_D(w,x)}$ on this subset such that:

1. All the words in $N_D(w, x)$ are possibly subsequences of the word $w$ concatenated with letter $x$.

2. The distribution gives the probability to make a transition to any state in $N_D(w, x)$: $\psi_{N_D(w,x)}(p)$ is the probability to jump from state $w$ to any state $p$ in $N_D(w, x)$, due to the arrival of an item of class $x$. Obviously:

$$ \sum_{p \in N_D(w,x)} \psi_{N_D(w,x)}(p) = 1, $$

and if the set $N_D(w, x)$ is a singleton, the probability distribution is a Dirac.

*Remark 2* This definition allows us to model disciplines where $N_D(w, x) = \{w\}$ (i.e. the matching has no effect on word $w$ even when $x$ is compatible with a letter in $w$). It is also possible to represent disciplines where the effect of a matching is to remove all the letters in $w$ which are compatible with letter $x$. We now introduce the notion of greedy matching discipline.

**Definition 6** (Greedy matching discipline) A matching discipline GD is greedy if, given state $w$ and arriving compatible letter $x$, for all states $p$ in $N_{GD}(w, x)$, we have $|p| = |w| - 1$ and $x \notin p$.

*Example 1* Clearly, FCFM is a greedy discipline such that the set $N_D(w, x)$ is a singleton for all words $w$ and letters $x$ that are compatible with $w$. Match the Longest with random drawing of tie breaking is a greedy discipline but the set $N_D(w, x)$ may contain several words.

**Definition 7** (RANDOM discipline) Assuming that a letter is compatible with a word, we delete one compatible letter in the word, where this letter is chosen with a uniform distribution among the compatible letters.

*Example 2* (RANDOM) Consider a state $w = abcba$. Suppose that a letter $t$ arrives and that $t$ is compatible with both $a$ and $b$ but it is not compatible with $c$.

$$ N_D(w, t) = \{bcaba, acaba, abcba, abcaa, abcab\} $$

Under the RANDOM discipline, each of these words has a probability of 1/5 to be selected.

*Remark 3* RANDOM is a greedy discipline.
*Example 2* Consider state $m = (a, b, c, a, b, a)$. Suppose that a letter $t$ arrives and that $t$ matches with both $a$ and $b$ but it does not match with $c$.

$$N_D(m, t) = \{(b, c, a, b, a), (a, c, a, b, a), (a, b, c, b, a), (a, b, c, a, a), (a, b, c, a, b)\}$$

Each of these words has a probability of 1/5 to be selected.

**Proposition 4** *RANDOM is a greedy discipline.*

**Proposition 5** *If the matching graph is such that the degree of every node is positive, the arrival rates of all items are positive and the discipline is greedy, then the Markov chain contains a state with 0 items which is reachable from any state.*

*Proof* Indeed all items can be deleted due to an arrival of an item of the desirable classes. □

Now we establish some relations between First Come First Match (FCFM) discipline and any greedy discipline (GD).

## 3.1 Complete Graphs and Greedy Disciplines

The performance paradox analysis consists of comparing the mean number of items in a quasi-complete graph and a complete graph. In the following result, we provide an explicit expression of the mean number of items of a complete graph with an arbitrary greedy matching policy.

**Lemma 1** Let GD be a greedy matching discipline, the states of the Markov chain associated with $K_n$ are words which are associated with the independent sets of the matching graph, i.e. the following words: $\emptyset, 1^*, 2^*, \dots, n^*$.

*Proof* by construction. First, states with several types of item are not reachable as items which match, instantaneously disappear even if we do not know which ones are deleted as we do not know exactly the discipline. Assuming now that the initial state is the empty state. The first arrival (say a type $x$ item) provokes a transition to word $(x)$. If the next arrival is again a type $x$ item (with rate $\lambda_x$), the next state is $(x, x)$, otherwise the arriving letter (say $y$) matches with the $x$ as the matching graph is a complete graph. For any greedy matching discipline, this matching provokes the destruction of both $y$ and $x$ and a transition to the empty word. Such an event occurs with rate $\lambda_y$. Thus, by induction on the transitions, we only obtain words with only one type of item or the empty word. As the valid states only contain one type of items, the discipline does not matter as soon as it is greedy and exactly one letter is deleted in the word. Furthermore, for this matching graph, the transition rates of the chain do not depend on the matching discipline. Note this is not true for sparser matching graph. The chains may be described as a collection of $n$ birth and death processes connected through state $\emptyset$. □
**Proposition 3** If the compatibility graph is such that the degree of every node is positive, the arrival rates of all items are positive and the discipline is greedy, then the Markov chain contains a state with 0 items which is reachable from any state.

*Proof* Indeed all items can be deleted due to a succession of arrivals of compatible classes. □

Now we establish some relations between the FCFM discipline and any greedy discipline (GD).

## 3.1 Complete Graphs and Greedy Disciplines

The performance paradox analysis consists of comparing the mean number of items for a quasi-complete graph and a complete graph. In the main result of this section, we provide an explicit expression for the mean number of items of a complete graph with an arbitrary greedy matching policy.

The following result characterizes the Markov chain associated with $K_n$ and any greedy matching policy as well as its expected value.

**Lemma 1** For a greedy matching discipline GD, the states of the Markov chain associated with $K_n$ are words which are associated with the independent sets of the compatibility graph, i.e. the following words: $\emptyset, 1^*, 2^*, ..., n^*$. In fact, the Markov chain consists of n birth and death processes which are connected through the empty word; when the state is $x^*$, with probability $\alpha_x$ the number of letters increases by one and with probability $1 - \alpha_x$ decreases by one. Assuming $\alpha_i < 0.5$ for all $i = 1, ..., n$, the mean number of items is

$$ \left(1 + \sum_{i=1}^{n} \frac{\alpha_i(1 - \alpha_i)}{1 - 2\alpha_i}\right)^{-1} \left(\sum_{i=1}^{n} \frac{\alpha_i(1 - \alpha_i)}{(1 - 2\alpha_i)^2}\right). \qquad (5) $$

*Proof* We assume that the initial state is the empty word. The first arrival (say a class x item) triggers a transition to word x. If the next arrival is again a class x item (with probability $\alpha_x$), the next state is xx, otherwise the arriving letter (say y) matches with the x as the compatibility graph is a complete graph. For any greedy matching discipline, this matching causes the destruction of both y and x and a transition to the empty word. Such an event occurs with probability $\alpha_y$. Thus, by induction on the transitions, we only obtain words with only one class of item or the empty word. As the valid states only contain one class of items, the discipline does not matter as soon as it is greedy and exactly one letter is deleted in the word. Furthermore, for this compatibility graph, the transition rates of the chain do not depend on the matching discipline (note that this is not true for sparser compatibility graphs). The derived Markov chain may be described as a collection of n birth and death processes connected through state $\emptyset$. When the state is $x^*$, the birth-probability is $\alpha_x$ and the death-probability $1 - \alpha_x$. It is easy to check that the mean number of items is (5). □
12 Performance Paradox of Dynamic Matching Models under Greedy Policies

**Corollary 1** The two Markov chains associated with matching graph $K_n$ and disciplines GD and FCFM are equal: $M(K_n, \bar{\lambda}, GD) = M(K_n, \bar{\lambda}, FCFM)$.

*Proof*: Indeed, both chains have the same state space and the same transitions rates. Remember that FCFM is a greedy discipline. □

**Lemma 2** We have: $\mathbb{E}[M(K_n, \bar{\lambda}, GD)] = \mathbb{E}[M(K_n, \bar{\lambda}, FCFM)]$.

*Proof*: This is a corollary of the previous results. □

**Lemma 3** Assume $\alpha_i < 0.5$ for all $i = 1, \dots, n$. For any greedy matching policy, the mean number of items in a complete graph with $n$ nodes is

$$ \left(1 + \sum_{i=1}^{n} \frac{\alpha_i}{1 - 2\alpha_i}\right)^{-1} \left(\sum_{i=1}^{n} \frac{\alpha_i(1 - \alpha_i)}{(1 - 2\alpha_i)^2}\right). \qquad (5) $$

*Proof* We note that all the words (different from the empty word) have a single letter. In fact, when the state is $k$ times the letter $x$, with probability $\alpha_x$ the number of letters increases by one and with probability $1 - \alpha_x$ decreases by one. This means that the Markov chain consists of $n$ birth and death processes which are connected through the empty word. As a result, since $\alpha_i < 0.5$ for all $i = 1, \dots, n$, we have that the steady-state distribution exists and it is unique. Let $\pi(x, k)$ be the steady-state probability of a word where the letter $x$ appears $k$ times. It is easy to see that $\pi(x, k) = \pi_0 \left(\frac{\alpha_x}{1-\alpha_x}\right)^k$, where $\pi_0$ is the normalization constant. It is also straightforward that $\pi_0 = \left(1 + \sum_{x=1}^n \frac{\alpha_x(1-\alpha_x)}{(1-2\alpha_x)^2}\right)^{-1}$. Finally, the mean number of items is given by

$$ \begin{aligned} \sum_{x=1}^{n} \sum_{k=1}^{\infty} k \pi(x, k) &= \left(1 + \sum_{x=1}^{n} \frac{\alpha_x(1-\alpha_x)}{(1-2\alpha_x)^2}\right)^{-1} \sum_{x=1}^{n} \sum_{k=1}^{\infty} k \left(\frac{\alpha_x}{1-\alpha_x}\right)^k \\ &= \left(1 + \sum_{x=1}^{n} \frac{\alpha_x(1-\alpha_x)}{(1-2\alpha_x)^2}\right)^{-1} \sum_{x=1}^{n} \frac{\frac{\alpha_x}{1-\alpha_x}}{\left(1-\frac{\alpha_x}{1-\alpha_x}\right)^2} \\ &= \left(1 + \sum_{x=1}^{n} \frac{\alpha_x(1-\alpha_x)}{(1-2\alpha_x)^2}\right)^{-1} \sum_{x=1}^{n} \frac{\alpha_x(1-\alpha_x)}{(1-2\alpha_x)^2}. \end{aligned} \qquad \square $$

The above result provides an explicit expression for the expectation of the total number of items if the matching is a complete graph. In the next section we give a similar result when the matching graph is a quasi-complete graph.
12 Performance Paradox of Dynamic Matching Models under Greedy Policies

Remark 4 From the above result, we conclude that the mean number of items associated with compatibility graph $K_n$ and disciplines GD and FCFM are equal, i.e.,

$$ \mathbb{E}[M(K_n, \lambda, GD)] = \mathbb{E}[M(K_n, \lambda, FCFM)]. \qquad (6) $$

The above result provides an explicit expression for the expectation of the total number of items if the matching is a complete graph. In the next section we give a similar result when the compatibility graph is a quasi-complete graph.

## 3.2 Quasi-Complete Graphs and Greedy Disciplines

Let us now study the expectation of the number of items for compatibility graph $K_n$ with a deleted edge (which is denoted by $K_n - (n - 1, n)$). We first show how to derive two compatibility graphs which have the same expected size of words in steady-state. This construction is based on the exact aggregation of Markov chains and the strong lumpability property (see [23] for the initial definition of aggregation for finite state space chains, and [24] for a recent description of this subject for denumerable ones). The following presentation follows [24].

Let $W$ be a Markov chain on set of states $\mathbb{W}$. Let $(B_1, .., B_k)$ be a partition of $\mathbb{W}$. We define a new process $Y$ as follows:

$$ Y_n = m \leftrightarrow W_n \in B_m. $$

The question is to find conditions such that $Y$ is also a Markov chain. Under these conditions, $Y$ will be denoted as an exact aggregation of $W$ for partition $(B_1, .., B_k)$. The strong lumpability condition (defined in the following) implies such a result (see [24] for the proof).

**Definition 8** (Strong Lumpability) $W$ is strongly lumpable for partition $(B_1, .., B_k)$ of its state space if for all subset indices $i$ and $j$ and for all states $m_1$ and $m_2$ in $B_i$, we have

$$ Pr(W_{n+1} \in B_j | W_n = m_1) = Pr(W_{n+1} \in B_j | W_n = m_2). $$

$B_i$ will be denoted as macro state $i$ in the following.

We first consider an arbitrary compatibility graph and an arbitrary node $x$. Let us denote by $G_x$ this graph. Let $W_x = M(G_x, \lambda, GD)$, i.e., $W_x$ is the Markov chain associated with matching $G_x$ and an arbitrary greedy matching policy GD.

**Definition 9** (Decomposition matching and Aggregated matching) We define a new matching by a decomposition of $x$ into two nodes $y$ and $z$. The decomposition is defined by:

$$ \Gamma(y) = \Gamma(z) = \Gamma(x) $$
## 3.2 Quasi-Complete Graphs and Greedy Disciplines

Let us now study the expectation of the number of items for matching graph $K_n$ with an edge deleted: (noted $K_n - (n-1, n)$). We first show how to derive two matching graphs which have the same expected size of words in steady-state. This construction is based on the exact aggregation of Markov chains and the strong lumpability property (see [22] for the initial definition of aggregation for finite state space chains, and [23] for a recent description of this subject for denumerable ones). The following presentation follows [23].

Let $W$ be a Markov chain on set of states $W$. Let $(B_1, .., B_k)$ be a partition of $W$. We define a new process $Y$ as follows:

$$Y_n = m \leftrightarrow W_n \in B_m.$$

The question is to find conditions such that $Y$ is also a Markov chain. Under these conditions, $Y$ will be denoted as an exact aggregation of $W$ for partition $(B_1, .., B_k)$. The strong lumpability condition (defined in the following) implies such a result (see [23] for the proof).

**Definition 8** (Strong Lumpability) $W$ is strongly lumpable for partition $(B_1, .., B_k)$ of its state space if for all subset index $i$ and $j$ and for all state $m1$ and $m2$ in $B_i$, we have

$$Pr(W_{n+1} \in B_j | W_n = m1) = Pr(W_{n+1} \in B_j | W_n = m2).$$

$B_i$ will be denoted as macro state $i$ in the following.

We first consider an arbitrary matching graph and an arbitrary node $x$. Let us denote by $G_x$ this graph. Let $W_x$ denote the Markov chain associated with matching $G_x$.

**Definition 9** (Decomposition matching and Aggregated matching) We define a new matching by a decomposition of $x$ into two nodes $y$ and $z$. The decomposition is defined by:

$$\bullet \Gamma(y) = \Gamma(z) = \Gamma(x)$$

$$\bullet \alpha_y > 0$$

$$\bullet \alpha_z > 0$$

$$\bullet \alpha_y + \alpha_z = \alpha_x.$$

Let $G_{yz}$ be the matching graph where $x$ is decomposed into $y$ and $z$. $G_{yz}$ will be denoted as the decomposition matching while $G_x$ is called the aggregated matching. $W_{yz}$ is the Markov chain associated with $G_{yz}$.

For instance we consider an aggregated matching in the right part Fig. 3. Node $x$ is decomposed in nodes $n$ and $n-1$ to build the decomposition matching graph (left part of the same figure).
<figure><img src="image_3.png" /><figcaption>**Fig. 2:** compatibility graphs: $K_n$ (a), $K_n - (n-1, n)$ (b), $K_{n-1}$ (c). The triple edge represents that the node $(n-1$ and $n$ for (a) and (b), and $x$ for (c)) is connected to all the nodes in $K_{n-2}$.</figcaption></figure>

* $\alpha_y > 0$

* $\alpha_z > 0$

* $\alpha_y + \alpha_z = \alpha_x$.

Let $G_{yz}$ be a new compatibility graph where $x$ is decomposed into $y$ and $z$. $G_{yz}$ will be denoted as the decomposition compatibility graph while $G_x$ is called the aggregated compatibility graph. Let $W_{yz} = M(G_{xy}, \lambda, GD)$. i.e., $W_{yz}$ is the Markov chain associated with $G_{yz}$ and an arbitrary greedy matching policy GD.

For instance we consider an aggregated matching in Fig. 2c. Node $x$ is decomposed into nodes $n$ and $n-1$ to build the decomposition compatibility graph (see Fig. 2b).

**Proposition 4** If the aggregated matching is associated with a stable Markov chain, so is the decomposition matching.

Note that by construction $y \notin \Gamma(z)$ and $z \notin \Gamma(y)$.

**Lemma 2** We consider the continuous-time Markov chain associated with compatibility graph $K_n - (n-1, n)$, arrival rates $\lambda$ and a greedy discipline GD: $M(K_n - (n-1, n), \lambda, GD)$. The states of the chain are the words $\emptyset, 1^*, 2^*, 3^*, \dots, (n-2)^*$ and words written with letters $n-1$ and $n$. The chain is lumpable according to the following partition.

* Each of the states represented by $i^*$ remain as individual states, for $i > 0$, as does state $\emptyset$.

* All the states $w$, formed only by letters $n$ and $n-1$ and such that $|w| = l > 0$, are gathered into a macro state called $C_l$.
<figure><img src="image_6.png" /><figcaption>**Fig. 3** Matching graphs: $K_n$ (left), $K_n - (n-1, n)$ (middle), $K_{n-1}$ (right). In all three graphs, there is an edge between single nodes $(n-1$ and $n$ for the first two graphs, and $x$ for the third graph) and any node in $K_{n-2}$. This is depicted as a triple edge.</figcaption></figure>

**Proposition 6** If the aggregated matching is associated with a stable Markov chain, the same property holds for the decomposition matching.

Note that by construction $y \notin \Gamma(z)$ and $z \notin \Gamma(y)$.

**Lemma 4** We consider the continuous time associated with matching graph $K_n - (n-1, n)$, arrival rates $\vec{\lambda}$ and a greedy discipline GD: $M(K_n - (n-1, n), \vec{\lambda}, GD)$. The states of the chain are the words $\emptyset, 1^*, 2^*, 3^*, \dots, (n-2)^*$ and words written with letters $n-1$ and $n$. The chain is lumpable according to the following partition.

* states $\emptyset, 1^*, 2^*, 3^*$ remain in singletons.

* all the states $m$, written with letters $n$ and $n-1$ and such that $|m| = l > 0$, are gathered into a macro state called $C_l$.

Let $Y$ be the lumped Markov chain.

*Proof* We consider the uniformized version of the chain with rate $\Lambda$ as mentioned formerly to get $M(K_n - (n-1, n), \vec{\alpha}, GD)$. Let $P_{GD}$ the transition probability matrix of this DTMC. First, we will prove that this chain is lumpable for the partition. Let $S$ be its state space. We have to prove the following equality for the macro states which are not singleton. Let $i$ and $j$ be macro-state indices

$$ \sum_{k \in C_i} P_{GD}[k, m] = \sum_{k \in C_i} P_{GD}[k, n] \quad \forall m, n \in C_j. $$

If such a condition holds, we note $P_{GD}(C_i, C_j) = \sum_{k \in C_i} P_{GD}[k, m]$ where $m$ is any state in $C_j$.

We only need to prove that this property holds for macro-states with more than one state: i.e. the macro states which contain the words $m$ which contains letters $n-1$ and $n$. Let $C_l$ be such a macro-state. From the definition, all the words in $C_l$ have length equal to $l$. We have to consider all the events:

* Arrival of a type $n$ item. A type $n$ item does not match any letter in word $m$ (remember that $m$ only contains letters $n$ and $n-1$). Thus the letter $n$ is appended to word $m$ and the state becomes $(m|n)$. This state is in macro-state $C_{l+1}$. And the probability of this transition is $\alpha_n$. Thus from any state in $C_l$, we have a single transition with probability $\alpha_n$ to a state in $C_{l+1}$.
14 Performance Paradox of Dynamic Matching Models under Greedy Policies

Proof We consider the uniformized version of the chain with uniformization rate $\Lambda$ as mentioned formerly to get $M(K_n - (n-1, n), \alpha, GD)$. Let $P_{GD}$ denote the transition probability matrix of this DTMC. First, we will prove that this chain is lumpable for the partition. Let $S$ be its state space. We have to prove the following equality for all macro states $C_l$. Let $i$ and $j$ be macro-state indices

$$ \sum_{k \in C_i} P_{GD}[k, m] = \sum_{k \in C_i} P_{GD}[k, n] \quad \forall m, n \in C_j. $$

If such a condition holds, we note $P_{GD}(C_i, C_j) = \sum_{k \in C_i} P_{GD}[k, m]$ where $m$ is any state in $C_j$.

Since all the words in $C_l$ have length equal to $l$, we have to consider all the events:

* Arrival of a class $n$ item. A class $n$ item is not compatible with any letter in word $w$ (remember that $w$ only contains letters $n$ and $n-1$). Thus letter $n$ is appended to word $w$ and the state becomes $(w|n)$. This state is in macro-state $C_{l+1}$, and the probability of this transition is $\alpha_n$. Thus from any state in $C_l$, we have a single transition with probability $\alpha_n$ to a state in $C_{l+1}$.

* Arrival of a class $n-1$ item: same property, from any state in $C_l$, we have a transition with probability $\alpha_{n-1}$ to a state in $C_{l+1}$.

* Arrival of a class $k$ item (with $k < n-1$): such an arrival deletes a class $n$ or class $n-1$ item. In the chain we have a transition from state $w$ to all the states $p$ in set $N_{GD}(w, k)$ with probability $\alpha_k \psi_{N_D(w,x)}(p)$. As the discipline is greedy, set $N_{GD}(w, k)$ is not empty. And all the states in $N_{GD}(w, k)$ have a length equal to $l-1$. Thus they are all included into macro-state $C_{l-1}$. As

$$ \sum_{p \in N_D(w,x)} \psi_{N_D(w,x)}(p) = 1, $$

we clearly have

$$ P(C_l, C_{l-1}) = \sum_{p \in N_D(w,x)} \alpha_k \psi_{N_D(w,x)}(p) = \alpha_k. $$

Thus, we have one transition with probability $\alpha_k$ from any state in $C_l$, to a state in $C_{l-1}$.

□

Let $Y$ be the lumped Markov chain presented in the above result. Note that both the arrival rates and the discipline have been modified when we switch from the decomposition compatibility graph to the aggregated one. Let $\lambda$ be the arrival rate vector in the model before aggregation of nodes $n$ and $n-1$, we define the rates $\mu$ in the aggregated model as follows: $\mu_i = \lambda_i$ for all $i < n-1$ and $\mu_{n-1} = \lambda_n + \lambda_{n-1}$. For the matching discipline, as we change $y$ and $z$ into $x$, we modify the sets $N_D$ and the distributions of probability for the aggregated model. However it is not necessary to describe them precisely. We just remark that the discipline is still greedy in the aggregated model and we emphasize that the discipline may change in general by changing its name to $GD'$ in the equation. From the above result, we directly obtain the following.
* Arrival of a type $n-1$ item: same property, from any state in $C_l$, we have a transition with probability $\alpha_{n-1}$ to a state in $C_{l+1}$.

* Arrival of a type $k$ item (with $k < n-1$): such an arrival deletes a type $n$ or type $n-1$ item. In the chain we have a transition from state $m$ to all the states $p$ in set $N_{GD}(m, k)$ with probability $\alpha_k$ $psi_{N_D(m,x)}(p)$. As the discipline is greedy, set $N_{GD}(m, k)$ is not empty. And all the states in $N_{GD}(m, k)$ have a length equal to $l-1$. Thus there are all included into macro-state $C_{l-1}$. As

$$ \sum_{p \in N_D(m,x)} \psi_{N_D(m,x)}(p) = 1 $$

we clearly have

$$ P(C_l, C_{l-1}) = \sum_{p \in N_D(m,x)} \alpha_k \psi_{N_D(m,x)}(p) = \alpha_k $$

Thus, we have one transition with probability $\alpha_k$ from any state in $C_l$, to a state in $C_{l-1}$.

<figure><img src="image_7.png" /></figure>

From the above result, the following one follows directly.

**Proposition 7** *Y can be identified with the Markov chain associated with matching graph $K_{n-1}$ and the same discipline.*

We now present the following result that proves that the expected total number of items coincides for all greedy disciplines in a quasi-complete graph.

**Lemma 5** *For matching graph $K_n - (n-1, n)$, all greedy disciplines provide the same expectation for the total number of items.*

*Proof:* Let $GD$ be an arbitrary greedy discipline and $\vec{\mu}$ defined by $\mu_i = \lambda_i$ for $i < n-1$ and $\mu_{n-1} = \lambda_n + \lambda_{n-1}$. By Lemma 2:

$$ \mathbb{E}[M(K_{n-1}, \vec{\mu}, GD)] = \mathbb{E}[M(K_{n-1}, \vec{\mu}, FCFM)] $$

and by Proposition 7:

$$ \mathbb{E}[M(K_{n-1}, \vec{\mu}, FCFM)] = \mathbb{E}[M((K_n - (n-1, n)), \vec{\mu}, FCFM)] $$

<figure><img src="image_8.png" /></figure>

Thus, one can obtain from Lemma 3 the expected number of items with a simple modification of the arrival rates for all greedy disciplines.
**Proposition 5** Y can be identified with the Markov chain associated with compatibility graph $K_{n-1}$, arrival rate vector $\mu$ and matching discipline $GD'$. Therefore,

$$ \mathbb{E}[M(K_n - (n, n-1), \lambda, GD)] = \mathbb{E}[M(K_{n-1}, \mu, GD')]. \quad (7) $$

*Remark 5* In some cases, it is possible to easily obtain the matching discipline in the aggregated model. For instance, if the original model uses FCFM discipline for the decomposition model, then the matching discipline after aggregation is also FCFM. Therefore

$$ \mathbb{E}[M(K_n - (n, n-1), \lambda, FCFM)] = \mathbb{E}[M(K_{n-1}, \mu, FCFM)]. \quad (8) $$

We now present the following result that proves, for a quasi-complete graph, that the expected total number of items coincides for all greedy disciplines.

**Lemma 3** For compatibility graph $K_n - (n-1, n)$, all greedy disciplines provide the same expectation for the total number of items. More precisely,

$$ \mathbb{E}[M(K_n - (n, n-1), \lambda, GD)] = \mathbb{E}[M(K_n - (n, n-1), \lambda, FCFM)]. $$

*Proof* : Let $GD$ be an arbitrary greedy discipline. From Proposition 5, we have

$$ \mathbb{E}[M(K_n - (n, n-1), \lambda, GD)] = \mathbb{E}[M(K_{n-1}, \mu, GD')]. $$

And according to Remark 4, we have for any greedy discipline $GD'$,

$$ \mathbb{E}[M(K_{n-1}, \mu, GD')] = \mathbb{E}[M(K_{n-1}, \mu, FCFM)]. $$

Remark 5 allows to conclude as:

$$ \mathbb{E}[M(K_n - (n, n-1), \lambda, FCFM)] = \mathbb{E}[M(K_{n-1}, \mu, FCFM)]. \quad (9) $$

□

Thus, one can obtain from (5) the expected number of items with a simple modification of the arrival rates for all greedy disciplines.

**Lemma 4** Assume $\alpha_i < 0.5$ for all $i = 1, \dots, n-2$ and $\alpha_{n-1} + \alpha_n < 0.5$. For any greedy matching policy, the mean number of items in a quasi-complete graph with $n$ nodes and edge $(n, n-1)$ missing, is

$$ \left( 1 + \sum_{i=1}^{n-2} \frac{\alpha_i}{1 - 2\alpha_i} + \frac{\alpha_{n-1} + \alpha_n}{1 - 2(\alpha_{n-1} + \alpha_n)} \right)^{-1} \left( \sum_{i=1}^{n-2} \frac{\alpha_i(1 - \alpha_i)}{(1 - 2\alpha_i)^2} + \frac{(\alpha_{n-1} + \alpha_n)(1 - \alpha_{n-1} - \alpha_n)}{(1 - \alpha_{n-1} - \alpha_n)^2} \right). \quad (10) $$
**Lemma 6** Assume $\alpha_i < 0.5$ for all $i = 1, \dots, n-2$ and $\alpha_{n-1} + \alpha_n < 0.5$. For any greedy matching policy, the mean number of items in a quasi-complete graph with $n$ nodes is

$$ \left( 1 + \sum_{i=1}^{n-2} \frac{\alpha_i}{1 - 2\alpha_i} + \frac{\alpha_{n-1} + \alpha_n}{1 - 2(\alpha_{n-1} + \alpha_n)} \right)^{-1} \left( \sum_{i=1}^{n-2} \frac{\alpha_i(1 - \alpha_i)}{(1 - 2\alpha_i)^2} + \frac{(\alpha_{n-1} + \alpha_n)(1 - \alpha_{n-1} - \alpha_n)}{(1 - \alpha_{n-1} - \alpha_n)^2} \right). \quad (6) $$

### 3.3 Existence of a performance paradox for any greedy discipline for $K_n - (n-1, n)$ matching graph

As a paradox occur for graphs $K_n$ and $K_n - (n-1, n)$, and FCFM discipline it also occurs for any greedy discipline.

**Theorem 2** For any greedy discipline there is a paradox between $K_n$ and $K_n - (n-1, n)$.

*Proof* As we have a paradox for $K_n$ and $K_n - (a, b)$ for FCFM, there exists a vector of arrivals $\vec{\lambda}$ such that:

$$ \mathbb{E}[M(K_n, \vec{\alpha}, \text{FCFM})] > \mathbb{E}[M(K_n - (n-1, n), \vec{\alpha}, \text{FCFM})]. $$

By Lemma 5, we have:

$$ \mathbb{E}[M(K_n - (n-1, n), \vec{\alpha}, \text{GD})] = \mathbb{E}[M(K_n - (n-1, n), \vec{\alpha}, \text{FCFM})], $$

and due to Lemma 2 we also have

$$ \mathbb{E}[M(K_n, \vec{\alpha}, \text{GD})] = \mathbb{E}[M(K_n, \vec{\alpha}, \text{FCFM})]. $$

Therefore the paradox exists for all greedy discipline. □

**Corollary 2** If a discipline does not exhibit such a paradox for graph $K_n - (1, 2)$, this discipline is not greedy.

## 4 The JOIN operation on matching graphs

First we have to restrict ourselves to a subset of matching disciplines.

**Definition 10** A discipline is consistent if for all word $m$, if two letters $x$ and $y$ have the same neighborhood within $m$, they also have the same subset of states $N_D(m, x)$ and the same discrete distribution of probability $\psi_{N_D(m, x)}$ on this subset. More formally

$$ \text{If } m \cap \Gamma(x) = m \cap \Gamma(y), \text{ then } N_D(m, x) = N_D(m, y) \text{ and } \psi_{N_D(m, x)} = \psi_{N_D(m, y)}. $$
## 3.3 Existence of a Performance Paradox for any Greedy Discipline for $K_n - (n-1, n)$ Compatibility Graph

From the above results, we conclude that, if a paradox occurs for graphs $K_n$ and $K_n - (n-1, n)$ under FCFM discipline, it also occurs for any greedy discipline.

**Theorem 2** *Combining previous lemmas, we get that:*

* if a paradox exists for compatibility graph $K_n - (n-1, n)$ and discipline FCFM, it also exists for any greedy discipline GD with the same arrival rates

* a paradox exists for $(K_4 - (3, 4))$ for any greedy discipline GD

Proving the existence of a performance paradox for the complete graph with arbitrary size $n$ and discipline FCFM will need first that we present some results about the modular construction of compatibility graphs. This is the aim of the next section.

# 4 Modular Construction of Matching Models

In this section, we aim to analyze operations on the compatibility graph that preserve the performance paradox. We present a modular construction of matching models by defining operations on compatibility graphs, on arrival processes and on the matching disciplines. For this purpose, we restrict ourselves to consistent matching policies, which are a subset of greedy matching policies.

**Definition 10** A discipline is consistent if for any word $w$, if two letters $x$ and $y$ have the same neighborhood within $w$, they also have the same subset of states $N_D(w, x)$ and the same discrete distribution of probability $\psi_{N_D(w,x)}$ on this subset. More formally,

if $w \cap \Gamma(x) = w \cap \Gamma(y)$, then $N_D(w, x) = N_D(w, y)$ and $\psi_{N_D(w,x)} = \psi_{N_D(w,y)}$.

**Definition 11** We define the compatibility index of a letter $x$ in word $w$ as the binary vector $IC_{w,x}$ with size $|w|$ such that, for all $i$ between 1 and $|w|$, $IC_{w,x}[i] = 1$ if $w[i] \in \Gamma(x)$ and 0 otherwise.

**Definition 12** A position-based discipline is a policy which uniquely uses the compatibility index $IC_{w,x}$ to build set $N_D(w, x)$ and probability distribution $\psi_{N_D(w,x)}$.

The following proposition follows directly from the definitions.

**Proposition 6** *Position-based disciplines are consistent.*
We now present some matching disciplines that are consistent and one matching discipline which is not.

Remark 3 FCFM, Match the Longest and Random are consistent.

Remark 4 We remark that there exist greedy disciplines which are not consistent. For instance, consider the word $m = (a, b, c)$ and two items $x$ and $y$ such that

$$ \Gamma(x) \cap m = \{a, c\} = \Gamma(y) \cap m. $$

One can design a discipline $D$ such that $N_D(m, x) = a$ and $N_D(m, y) = c$. The greedy assumption is satisfied for this word and these items and the discipline is not consistent.

In the following, we assume that the matching disciplines are greedy and consistent.

We consider the following operations to build matching graphs: the JOIN operation and the UNION operation. These two operations allow to have a modular presentation of matching graphs and how to combine them. Again this is easier in continuous time thanks to the race condition. For a composition of two matching graphs $G1$ and $G2$ associated with transition rates vectors $\vec{\lambda}$ and $\vec{\mu}$ we denote as $(\vec{\lambda}, \vec{\mu})$ the rate vectors associated with the composition of $G1$ and $G2$. Let us now begin with the definition of both operations.

**Definition 11** (JOIN operation) We consider two arbitrary graphs $G1 = (V1, E1)$ and $G2 = (V2, E2)$. The JOIN of $G1$ and $G2$ is graph $G = (V, E)$ defined as follows:

* Nodes: $V = V1 \cup V2$,

* Edges: $E = E1 \cup E2 \cup \{(x, y), x \in V1, y \in V2\}$.

Intuitively, we keep the nodes and edges of $G1$ and $G2$ and we add all the edges between $V1$ and $V2$. The JOIN operation will be noted $\bowtie$.

We depict in the next figure the JOIN of an independent set (nodes 4 to 7) and a complete graph (nodes 1 to 3).

<figure><img src="image_9.png" /><figcaption>Fig. 4 Graph $IS_4 \bowtie K_3$.</figcaption></figure>
Remark 6

(a) FCFM, Last Come First Match and Random are position-based disciplines while Match the Longest and Priority are not.

(b) Match the Longest is not position-based but it is consistent.

(c) We remark that Priority is not a consistent discipline. For instance, consider the word $w = abc$ and two items $x$ and $y$ such that

$$ \Gamma(x) \cap w = \{a, c\} = \Gamma(y) \cap w. $$

One can design a discipline $D$ such that $N_D(w, x) = \{bc\}$ and $N_D(w, y) = \{ab\}$. The greedy assumption is satisfied for this word and these items and the discipline is not consistent.

In the following, we assume that the matching disciplines are greedy and consistent. We would like to remark that this assumption excludes matching disciplines that make use of item class information, such as priorities. We now consider the following operations to build compatibility graphs: the JOIN operation and the UNION operation. These two operations allow to have a modular presentation of compatibility graphs and how to combine them.

**Definition 13** (∪ operation) We consider two arbitrary disjoint graphs $G_1 = (V_1, \mathcal{E}_1)$ and $G_2 = (V_2, \mathcal{E}_2)$. The UNION of $G_1$ and $G_2$ is graph $G = (V, \mathcal{E})$ defined as follows:

* Nodes: $V = V_1 \cup V_2$,

* Edges: $\mathcal{E} = \mathcal{E}_1 \cup \mathcal{E}_2$.

**Definition 14** (JOIN operation) We consider two arbitrary disjoint graphs $G_1 = (V_1, \mathcal{E}_1)$ and $G_2 = (V_2, \mathcal{E}_2)$. The JOIN of $G_1$ and $G_2$ is graph $G = (V, \mathcal{E})$ defined as follows:

* Nodes: $V = V_1 \cup V_2$,

* Edges: $\mathcal{E} = \mathcal{E}_1 \cup \mathcal{E}_2 \cup \{(x, y), x \in V_1, y \in V_2\}$.

In words, we keep all nodes and edges of $G_1$ and $G_2$ and we add all the edges between nodes in $V_1$ and $V_2$. The JOIN operation will be denoted by $\bowtie$.

We depict in Figure 3 the JOIN of a graph with 4 isolated nodes (nodes 4 to 7) and a complete graph with 3 nodes (nodes 1 to 3).

Remark 7 If $\mathcal{E}_1 = \mathcal{E}_2 = \emptyset$, then $G$, which is the join of $G_1$ and $G_2$, is a complete bipartite graph. Remember that we do not study model associated with bipartite compatibility graphs as their associated Markov chains are not ergodic.
18 Performance Paradox of Dynamic Matching Models under Greedy Policies

Remark 5 If $\mathcal{E}1 = \mathcal{E}2 = \emptyset$, then $G$ is a complete bipartite graph. Remember that we do not study model associated to bipartite matching graphs as their chains are not ergodic.

**Definition 12** (∪ operation) We consider two arbitrary graphs $G1 = (V1, \mathcal{E}1)$ and $G2 = (V2, \mathcal{E}2)$. The UNION of $G1$ and $G2$ is graph $G = (V, E)$ defined as follows:

* Nodes: $V = V1 \cup V2$,

* Edges: $\mathcal{E} = \mathcal{E}1 \cup \mathcal{E}2$.

**Assumption 1** (Discipline and Operations) We assume that the discipline is the same on both subgraphs when we build a JOIN or a UNION of matching graphs $G1$ and $G2$.

## 4.1 Matching graphs $G1 \bowtie G2$

We consider any greedy and consistent discipline $D$. The results are not based on any particular discipline. When we give examples to illustrate the results, the matching discipline is mentioned.

<figure><img src="image_10.png" /><figcaption>Fig. 5 Graph $G1 \bowtie G2$.</figcaption></figure>

**Lemma 7** Consider a matching graph $G$ which is the JOIN of graph $G1$ and $G2$. Let $M1$ (resp. $M2$) the continuous-time Markov chain associated with $G1$ (resp. $G2$) and vector of arrival rates $\vec{\lambda}$ (resp. $\vec{\text{vec}\mu}$). Both chains have an empty state because the discipline is greedy. Then the continuous time Markov chain associated to $G$ has the following states which are a couple of words:

* The states associated of $M1$ (no items of $G2$ are in the system) : the states will be denoted as $(x, \emptyset)$ where $x$ is a state of $M1$ (i,e a word). This set of states will be denoted as $S_1$.

* The states associated with $M2$ (no items of $G1$ are in the system) : the states will be denoted as $(\emptyset, y)$ where $y$ is a node of $M2$. Similarly, we denote as $S_2$ this set of states.

* Both chains are connected through their empty states which are merged.

And the transitions are the same as in the Markov chains associated with $G1$ or $G2$. More precisely : we have a transition from $(x1, \emptyset)$ to $(x2, \emptyset)$ if there is a transition
<figure><img src="image_4.png" /><figcaption>Fig. 3: Graph $IN_4 \bowtie K_3$.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Fig. 4: Graph $G_1 \bowtie G_2$.</figcaption></figure>

As a matching model is a triple with a compatibility graph, a collection of arrival processes and a matching discipline, we also have to explain how we associate the last two parts of the model to both modular constructions of compatibility graphs. For the arrival processes, we consider the union of the sets of Poisson processes associated with $G_1$ and $G_2$. This is easier in continuous time thanks to the race condition which is already well-known for the modular construction of stochastic models. For a composition of two compatibility graphs $G_1$ and $G_2$ associated with transition rates vectors $\lambda$ and $\mu$ we denote as $(\lambda, \mu)$ the rate vector associated with the composition of $G_1$ and $G_2$.

For the matching disciplines, we first have to find the state space of the models as they are defined as sets of states and probability distributions on these sets.

## State Space for UNION

Let $G_1$ and $G_2$ be two disjoint compatibility graphs. Consider the compatibility graph $G$ which is the UNION of graphs $G_1$ and $G_2$. Then the state space of the continuous time Markov chain associated with $G$ is the Cartesian product of the state spaces of the two Markov chains associated with $G_1$ and $G_2$.

## State Space for JOIN

*Remark 8* Consider a compatibility graph $G$ which is the JOIN of graphs $G_1$ and $G_2$. Remember that $G_1$ and $G_2$ are disjoint. Let $M_1$ (resp. $M_2$) be the continuous-time Markov chain associated with $G_1$ (resp. $G_2$) and vectors of arrival rates $\lambda$ (resp. $\mu$). Both chains have an empty state because the discipline is greedy. Then the
from x1 to x2 in M1. Similarly there is a transition from (Ø, y1) to (Ø, y2) if there is a transition from y1 to y2 in M2. Thus the set of states of the chain is S1 ∪ S2. Let E be the empty state: E = (Ø, Ø).

The proof is trivial as it is not possible to reach a state (x, y) with both
x ≠ Ø and y ≠ Ø due to the edges betwwen G1 and G2 after the JOIN. See
Fig 6 for an example.

<figure><img src="image_11.png" /><figcaption>**Fig. 6** Markov chain of the matching graph $IS_2 \bowtie K_2$ for RANDOM discipline. The chain is truncated to words smaller than 4 letters. The labels (except E) and the rates are omitted for the sake of readability.</figcaption></figure>

**Lemma 8** Let $\vec{\lambda}$ be the vector of arrival rates for matching graph G1 and let $\vec{\mu}$ be the vector of rates for items in G2. After uniformization with rate $\Lambda = 2(\|\vec{\lambda}\|_1 + \|\vec{\mu}\|_1)$, the transition probability matrix of discrete-time Markov chain associated with G1 $\bowtie$ G2 and vector of arrivals $(\vec{\lambda}, \vec{\mu})$ has the following block decomposition associated to the partition of the states $(\{E\}, S1 \setminus \{E\}, S2 \setminus \{E\})$:

$$
M = \left( \begin{array}{c|c|c} \frac{1}{2} & L1 & L2 \\ \hline C1 & P1 & 0 \\ \hline C2 & 0 & P2 \end{array} \right),
$$

where L1 and L2 are row vectors, C1 and C2 are column vectors and P1 and P2 are sub-stochastic matrices. Similarly, if the Markov chain is ergodic, we decompose the steady-state distribution $\pi^M$ as $(\pi_0^M, \pi_{S1}^M, \pi_{S2}^M)$.

*Proof* : We have:

* due to the uniformization rate, $\|L1\|_1 = \frac{\|\vec{\lambda}\|_1}{\Lambda}$ and $\|L2\|_1 = \frac{\|\vec{\mu}\|_1}{\Lambda}$. Therefore the transition probability between E and E is 1/2.

* There is no transition between a state (Ø, y) to (x, Ø) if y and x are not equal to Ø. Therefore these two blocks are null.
continuous time Markov chain associated with G has the following states which are a couple of words:

* The states associated with $M_1$ (no items of $G_2$ are in the system) denoted by $(w1, \emptyset)$ where $w1$ is a state of $M_1$ (i.e., a word). This set of states will be denoted by $S_1$.

* The states associated with $M_2$ (no items of $G_1$ are in the system) denoted by $(\emptyset, w2)$ where $w2$ is a state of $M_2$. Similarly, we denote as $S_2$ this set of states.

* Both chains are connected through their empty states which are merged.

The proof is trivial as it is not possible to reach a state $(w1, w2)$ with both $w1 \neq \emptyset$ and $w2 \neq \emptyset$ due to the edges between $G_1$ and $G_2$ after the JOIN under a greedy policy. See Fig. 5 for an example.

Finally, we explain how we build a matching discipline on these constructions of compatibility graphs. Again we have to give separate statements. To be more precise for these definitions, we add a superscript to the name of the sets to know from which compatibility graphs they come.

## Discipline for UNION

Let $(w1, w2)$ a state of the chain associated with $G_1 \cup G_2$. We have to consider two types of arrival: a letter $x$ in $V(G_1)$ or a letter $y$ in $V(G_2)$. We define the discipline on the UNION as follows:

$$N_D^{G_1 \cup G_2}((w1, w2), x) = N_D^{G_1}(w1, x), \quad (11)$$

and

$$N_D^{G_1 \cup G_2}((w1, w2), y) = N_D^{G_2}(w2, y). \quad (12)$$

The probability distributions are also defined similarly.

Thus, due to this discipline and the race condition between the arrival processes, the transition matrix of the Markov chain is the Kronecker sum of the transition matrices associated with $G_1$ and $G_2$ (see Plateau [25] for such a result for stochastic automata networks).

## Discipline for JOIN

We consider an arbitrary non empty set $(w1, \emptyset)$. Indeed there is no need for a matching discipline for the empty state and states $(\emptyset, w2)$ play a symmetrical role. We have two cases, according to the arriving letter (say $x$):

* If $x \in V(G_1)$, if there is compatibility with $w1$, then we keep the same discipline

$$N_D^{G_1 \bowtie G_2}((w1, \emptyset), x) = N_D^{G_1}(w1, x), \quad (13)$$

and the distribution of probability does not change.
<figure><img src="image_12.png" /></figure>

We now prove that the steady-state distribution of the chain associated with G have a closed form solution based on the steady-state solutions of chains associated with matching graphs we now describe. We call this solution a separable solution for the steady-state distribution. Let us begin by the description of the sub-models.

<figure><img src="image_13.png" /><figcaption>Fig. 7 G'1: New matching graph for the first sub-model.</figcaption></figure>

**Proposition 8** We build a simpler matching graph as follows: we replace G1 by a single node s1, we add a loop on s1, we keep G2 unchanged and we add the edges between s1 and all the nodes in G2 (see Fig. 7). Matching graphs with self loops were recently introduced by Moyal et al. in [13] and independently in [24]. Let G'2 be this matching graph. Assume that the Markov chain associated G'2 and vector of arrival rates ($\sum_i \lambda_i, \vec{\mu}$ is ergodic. Let M2 be its transition probability matrix after uniformization with rate $\Lambda$ and let $\pi^{M2}$ be its steady state distribution The state space of the Markov chain associated to G'2 is the following (see Fig. 8):

* The state $(1, \emptyset)$ with one item of type s1 and no items of G2. Note that this is the only state with a positive number of items of type s1 as G'2 contains a loop on s1.

* The state $(0, \emptyset) = E$ which represents an empty system.

* The states associated with items of G2 (no s1 items are present in the system) : the states will be denoted as $(0, y)$ where y is a node of G2. Clearly, there is a one to one mapping between states (0, y) in Markov chain M2 and states $(\emptyset, y)$ in Markov chain P. Therefore we also denote as $S_2$ this set of states.

$M2$ has the following block decomposition associated to the partition of the states $((1, \emptyset)), \{E\}, S2 \setminus \{E\})$.

$$M2 = \left( \begin{array}{c|c|c} \begin{array}{c} 1/2 \\ a \\ 0 \end{array} & \begin{array}{c} 1/2 \\ 1/2 \\ C2 \end{array} & \begin{array}{c} \vec{0} \\ L2 \\ P2 \end{array} \\ \hline \begin{array}{c} 1/2 \\ 0 \end{array} & \begin{array}{c} 1/2 \\ C2 \end{array} & \begin{array}{c} \vec{0} \\ P2 \end{array} \end{array} \right),$$

where blocks L2, C2 and P2 have already been obtained in the decomposition of matrix M. We also consider a decomposition of the steady state distribution of M2: $(\pi_1^{M2}, \pi_0^{M2}, \pi_{S1}^{M2})$.
* $x \in V(G_2)$. Because of the JOIN between $G_1$ and $G_2$, all the letters in $w_1$ match with $x$. We take as a discipline in that case (i.e. $N_D^{G_1 \triangleright G_2}((w_1, \emptyset), x)$), any consistent discipline. Indeed in the next section, we will aggregate all the letters $x$ into only one letter, thus we need that the discipline does not depend on $x$ in that case.

The transitions are the same as in the Markov chains associated with $G_1$ or $G_2$. More precisely : we have a transition from $(x_1, \emptyset)$ to $(x_2, \emptyset)$ if there is a transition from $x_1$ to $x_2$ in $M_1$. Similarly there is a transition from $(\emptyset, y_1)$ to $(\emptyset, y_2)$ if there is a transition from $y_1$ to $y_2$ in $M_2$. Thus the set of states of the chain is $S_1 \cup S_2$. Let $E$ be the empty state: $E = (\emptyset, \emptyset)$.

We are now able to study the models based on these modular decompositions.

<figure><img src="image_6.png" /><figcaption>**Fig. 5:** Markov chain of the compatibility graph $IN_2 \bowtie K_2$ for RANDOM discipline. The chain is truncated to words smaller than 4 letters. The labels (except $E$) and the rates are omitted for the sake of readability.</figcaption></figure>

## 4.1 Compatibility Graphs $G_1 \bowtie G_2$

We first consider graph $G_1$ and $G_2$ which both contain at least 2 nodes and one edge (formally $K_2 \subset G_1$ and $K_2 \subset G_2$). The case where one of these graphs is a set of isolated nodes is studied in section 4.2. We consider any greedy and consistent discipline $D$ built as in the previous section. We assume that all the chains we define are ergodic.

*Remark 9* Let $\lambda$ be the vector of arrival rates for compatibility graph $G_1$ and let $\mu$ be the vector of rates for items in $G_2$. After uniformization with rate $\Lambda = 2(\|\lambda\|_1 + \|\mu\|_1)$, the transition probability matrix of discrete-time Markov chain associated with $G_1 \bowtie G_2$ and vector of arrivals rates $(\lambda, \mu)$ has the following block decomposition associated
<figure><img src="image_14.png" /><figcaption>Fig. 8 Markov chain for G'1 for G1 = K2 and Random discipline.</figcaption></figure>

*Proof*: We have to prove that the blocks L2, C2 and P2 are the same as in block decomposition of matrix M and give the value of a.

* From state (1, ∅) all the arrivals match letter s1 and the transitions leads to (0, ∅). Thus due to the uniformization rate, this transition has probability 1/2 and there is a loop on state (1, ∅) with probability 1/2.

* The transition from (0, ∅) leads to (1, ∅) for an arrival of letter s1 (i.e. with a probability equal to $\frac{\|\vec{\lambda}\|_1}{\Lambda}$). Therefore $a = \frac{\|\vec{\mu}\|_1}{\Lambda}$ and there is a loop with probability 1/2 on this state.

* The transition from (0, ∅) to a state in S2 for an arrival of a letter of G2 (i.e. block L2). This is the same transition probability as in Matrix M as it is based on the same arrival rates, the same uniformization rate and the same discipline.

* The transition from a state in S2 to state (0, ∅) for an arrival of a letter of G1 or G2 (i.e. block C2). All letters of G1 has the same effect as item s1 due to a consistent discipline and all letters of G2 have the same effect in M and in M2. The uniformization rate is the same in both models. Therefore both matrices have the same block C2 to model these transitions.

□

We do a similar construction for G'1 which is depicted in Fig. 9 by aggregation all the nodes of G2 into a single node s2 and adding a self loop on s2. Let M1 be the Markov chain associated with G'1 after uniformization with rate $\|\vec{\lambda}\|_1 + \|\vec{\mu}\|_1$ and ($\pi^{M1}$ its steady state distribution after assuming that M1 is ergodic. The state space is partitioned as follows: ({(1, ∅)}, {E}, S1 \ {E}). Similarly, we have a block decomposition for M1 based on this partition:

$$M1 = \begin{pmatrix} \frac{1/2}{b} & \frac{1/2}{1/2} & \vec{0} \\ \frac{1/2}{0} & \frac{1/2}{C1} & \vec{1} \\ 0 & 1/2 & P1 \end{pmatrix},$$
with the partition of the states ({E}, S₁ \ {E}, S₂ \ {E}):

$$M = \begin{pmatrix} \frac{1}{2} & L_1 & L_2 \\ \frac{C_1}{C_2} & P_1 & 0 \\ 0 & 0 & P_2 \end{pmatrix},$$

where L₁ and L₂ are row vectors such that ||L₁||₁ = ||λ||₁/λ and ||L₂||₁ = ||μ||₁/λ, C₁ and C₂ are column vectors and P₁ and P₂ are sub-stochastic matrices. Similarly, we decompose the steady-state distribution π as (π₀, πS₁, πS₂). Note that we only need that λ > ||λ||₁ + ||μ||₁ for uniformization. This value of λ has been chosen to improve the readability of the matrices.

We now prove that the steady-state distribution of the chain associated with G has a closed form solution based on the steady-state solutions of chains associated with compatibility graphs we now describe. We call this solution a separable solution for the steady-state distribution. Let us begin with the description of the sub-models.

<figure><img src="image_7.png" /><figcaption>Fig. 6: $G'_2$: New compatibility graph for the first sub-model.</figcaption></figure>

We build a simpler compatibility graph as follows: we replace $G_1$ by a single node $s_1$, we add a loop on $s_1$ due to the edges in $G_1$, we keep $G_2$ unchanged and we add the edges between $s_1$ and all the nodes in $G_2$ (see Fig. 6). Compatibility graphs with self loops were recently introduced by Moyal et al. in [13] and independently in [26]. Let $G'_2$ be this compatibility graph. The arrival rates associated with this compatibility graph are (||λ||₁, μ). The discipline associated with $G'_2$ is derived from D. As D is consistent, all the letters of $G_1$ provoke the same transitions on a word (Ø, m2) and we use this set of nodes and this distribution to define the discipline.

Let $M_2$ be the transition probability matrix after uniformization with rate λ and let $π^{M_2}$ be its steady state distribution. The state space of the Markov chain associated with $G'_2$ is the following (see Fig. 7):

* The state (1, Ø) with one item of class $s_1$ and no items of $G_2$. Note that this is the only state with a positive number of items of class $s_1$ as $G'_2$ contains a loop on $s_1$.

* The state (0, Ø) = E which represents an empty system.

* The states associated with items of $G_2$ (no $s_1$ items are present in the system) : the states will be denoted as (0, y) where y is a node of $G_2$. Clearly,
with

$$b = \frac{\|\vec{\lambda}\|_1}{\|\vec{\lambda}\|_1 + \|\vec{\mu}\|_1}.$$

<figure><img src="image_15.png" /><figcaption>Fig. 9 G'1: New matching graph for the other sub-model.</figcaption></figure>

**Theorem 3** Let G is the JOIN of graph G1 and G2, and M the continuous-time Markov chain associated with G and arrival rates $(\vec{\alpha}, \vec{\beta})$. Assume that M, M1 and M2 are associated with ergodic discrete-time Markov chains. Let $\pi_M$ be the steady state distribution of the chain associated with M. We decompose this distribution into three parts: the probability of the empty state, the probability of the states of $S_1$ and the probability of the states of $S_2$.

$$\pi_M = (\pi_0^M, \pi_{S_1}^M, \pi_{S_2}^M),$$

where these elements are obtained through the steps detailed in the following. The steady-state distribution of M1 is:

$$\pi_{M1} = (\pi_1^{M1}, \pi_0^{M1}, \pi_{S_1}^{M1}),$$

with an abuse of notation here. Indeed $S1$ is the set of states of M (not of M1) but there is a one to one mapping between the set of non zero states of M1 and $S1$. Therefore we use the same index for the decomposition of the probability vector. Similarly, we note:

$$\pi_{M2} = (\pi_1^{M2}, \pi_0^{M2}, \pi_{S2}^{M2}).$$

Then we have:

$$\pi_{S_1}^M = \pi_{S1}^{M1} \frac{\pi_0^M}{\pi_0^{M1}},$$

and

$$\pi_{S_2}^M = \pi_{S2}^{M2} \frac{\pi_0^M}{\pi_0^{M2}},$$

and finally

$$\pi_0^M = (\frac{1}{\pi_0^{M1}} + \frac{1}{\pi_0^{M2}} - 2)^{-1}.$$

*Proof* It is based on some decomposition and matrix formulation for discrete time Markov chains and censored Markov chains (see [25] for censored Markov chains). First we write the global balance equation for M at the block level:

$$\pi_0^M = \pi_0^M/2 + \pi_{S1}^M C1 + \pi_{S2}^M C2, \quad (7)$$
there is a one to one mapping between states $(0, y)$ in Markov chain $M_2$ and states $(\emptyset, y)$ in Markov chain $P$. Therefore we also denote as $S_2$ this set of states.

<figure><img src="image_8.png" /><figcaption>Fig. 7: Markov chain for $G'_1$ for $G_1 = K_2$ and Random discipline.</figcaption></figure>

**Proposition 7** $M_2$ has the following block decomposition associated with the partition of the states $((1, \emptyset)), \{E\}, S_2 \setminus \{E\})$.

$$M_2 = \begin{pmatrix} \frac{1/2}{c_2} & \frac{1/2}{C_2} & \frac{1/2}{P_2} \\ \frac{1/2}{c_2} & \frac{1/2}{L_2} & \frac{1/2}{P_2} \\ 0 & 0 & 0 \end{pmatrix},$$

where blocks $L_2, C_2$ and $P_2$ have already been obtained in the decomposition of matrix $M$ and $c_2 = \frac{\|\lambda\|_1}{\Lambda}$.

The proof of the above result is provided in Appendix C.1. We also consider a decomposition of the steady state distribution of $M_2$: $(\pi_1^{M_2}, \pi_0^{M_2}, \pi_{S_1}^{M_2})$.

We do a similar construction for $G'_1$ which is depicted in Fig. 8 by aggregation all the nodes of $G_2$ into a single node $s_2$ and adding a self loop on $s_2$, with similar definitions for $M_1$. For this case, we have a block decomposition for $M_1$ based on this partition:

$$M_1 = \begin{pmatrix} \frac{1/2}{c_1} & \frac{1/2}{L_1} & \frac{1/2}{P_1} \\ \frac{1/2}{c_1} & \frac{1/2}{L_1} & \frac{1/2}{P_1} \\ 0 & 0 & 0 \end{pmatrix},$$

with $c_1 = \frac{\|\mu\|_1}{\Lambda}$.

We can now show the relation between the steady-state distributions associated with these three models. Let $G$ be the JOIN of graph $G_1$ and $G_2$, and
and

$$ \pi_{S1}^{M} = \pi_{0}^{M} L1 + \pi_{S1}^{M} P1, \qquad (8) $$

and finally

$$ \pi_{S2}^{M} = \pi_{0}^{M} L2 + \pi_{S2}^{M} P2. \qquad (9) $$

We do the same for $M1$:

$$ \pi_{1}^{M1} = \pi_{0}^{M1} b + \pi_{1}^{M1} / 2, \qquad (10) $$

$$ \pi_{0}^{M1} = \pi_{1}^{M1} / 2 + \pi_{0}^{M1} / 2 + \pi_{S1}^{M1} C1, \qquad (11) $$

and finally,

$$ \pi_{S1}^{M1} = \pi_{0}^{M1} L1 + \pi_{S1}^{M1} P1 \qquad (12) $$

One can considered the censored Markov chain extracted from $M1$ with censored set $\{s2\}$. According to Lemma 6.6 in [25], $\sum_{i=0}^{\infty} P1^i$ converges and we obtain:

$$ \pi_{S1}^{M1} = \pi_{0}^{M1} L1 \sum_{i=0}^{\infty} P1^i, \qquad (13) $$

and as $\pi_{0}^{M1}$ is a scalar, we get:

$$ \frac{\pi_{S1}^{M1}}{\pi_{0}^{M1}} = L1 \sum_{i=0}^{\infty} P1^i. \qquad (14) $$

With the same argument, Eq. 8 gives:

$$ \frac{\pi_{S1}^{M}}{\pi_{0}^{M}} = L1 \sum_{i=0}^{\infty} P1^i. \qquad (15) $$

Taking info account Eq. 14 and Eq. 15 we obtain after substitution:

$$ \pi_{S1}^{M} = \frac{\pi_{0}^{M}}{\pi_{0}^{M1}} \pi_{S1}^{M1}. $$

With a similar approach we have for matrix $P2$:

$$ \frac{\pi_{S2}^{M2}}{\pi_{0}^{M2}} = L2(Id - P2)^{-1}, \qquad (16) $$

and

$$ \pi_{S2}^{M} = \frac{\pi_{0}^{M}}{\pi_{0}^{M2}} \pi_{S2}^{M2}. $$

The first two results of the theorem are now established. For the computation of $\pi_{0}^{M}$ it is not possible to use Eq. 7 because it is not independent. Therefore we use normalization.

$$ \pi_{0}^{M} + \|\pi_{S1}^{M}\|_{1} + \|\pi_{S2}^{M}\|_{1} = 1. $$

After substitution:

$$ \pi_{0}^{M} (1 + \frac{1}{\pi_{0}^{M1}} \|\pi_{S1}^{M1}\|_{1} + \frac{1}{\pi_{0}^{M2}} \|\pi_{S2}^{M2}\|_{1}) = 1. $$

Clearly, $\|\pi_{S1}^{M1}\|_{1} = 1 - \pi_{0}^{M1} - \pi_{1}^{M1}$ and $\|\pi_{S2}^{M2}\|_{1} = 1 - \pi_{0}^{M2} - \pi_{1}^{M2}$. Thus

$$ \pi_{0}^{M} = \left( 1 + \frac{1 - \pi_{0}^{M1}(1 + 2b)}{\pi_{0}^{M1}} + \frac{1 - \pi_{0}^{M2}(1 + 2a)}{\pi_{0}^{M2}} \right)^{-1}. $$

After simple algebraic manipulation, taking into account that $2(a+b) = 1$, we finally obtain the relation for $\pi_{0}^{M}$. And this concludes the proof. $\square$
<figure><img src="image_9.png" /><figcaption>Fig. 8: $G'_1$: New compatibility graph for the other sub-model.</figcaption></figure>

$M$ the discrete-time Markov chain associated with $G$ and arrival probabilities $(\alpha, \beta)$. These probabilities have been derived by uniformization of rates $(\lambda, \mu)$ by rate $\Lambda$. Assume that $M$, $M_1$ and $M_2$ are ergodic discrete-time Markov chains. Let $\pi_M$ be the steady state distribution of the chain associated with $M$. We decompose this distribution into three parts: the probability of the empty state, the probability of the states of $S_1$ and the probability of the states of $S_2$.

$$ \pi_M = (\pi_0^M, \pi_{S_1}^M, \pi_{S_2}^M), $$

where these elements are obtained through the steps detailed in the following. The steady-state distribution of $M_1$ is:

$$ \pi_{M_1} = (\pi_1^{M_1}, \pi_0^{M_1}, \pi_{S_1}^{M_1}), $$

with an abuse of notation here. Indeed $S_1$ is the set of states of $M$ (not of $M_1$) but there is a one to one mapping between the set of non zero states of $M_1$ and $S_1$. Therefore we use the same index for the decomposition of the probability vector. Similarly, we denote:

$$ \pi_{M_2} = (\pi_1^{M_2}, \pi_0^{M_2}, \pi_{S_2}^{M_2}). $$

**Theorem 3** Consider the former construction. We have:

$$ \pi_{S_1}^M = \pi_{S_1}^{M_1} \frac{\pi_0^M}{\pi_0^{M_1}}, $$

and

$$ \pi_{S_2}^M = \pi_{S_2}^{M_2} \frac{\pi_0^M}{\pi_0^{M_2}}, $$

and finally

$$ \pi_0^M = \left( \frac{1}{\pi_0^{M_1}} + \frac{1}{\pi_0^{M_2}} - 2 \right)^{-1}. $$

Furthermore, the expectation of the total number of items is:

$$ \mathbb{E}[M((G_1 \bowtie G_2), (\lambda, \mu), D)] = \frac{\pi_0^M}{\pi_0^{M_1}} \mathbb{E}[M(G'_1, \lambda, D_1)] + \frac{\pi_0^M}{\pi_0^{M_2}} \mathbb{E}[M(G'_2, \mu, D_2)] - 1, $$

where $D_1$ and $D_2$ are the disciplines derived from $D$.
**Corollary 3** We can compute the expectation of the total number items for the JOIN matching graphs from these expectations for the sub-models:

$$ \mathbb{E}[M((G1 \bowtie G2), (\vec{\lambda}, \vec{\mu}), D)] = \frac{\pi_0^M}{\pi_0^{M1}} \mathbb{E}[M(G'1, (\vec{\lambda}, )),] + \frac{\pi_0^M}{\pi_0^{M2}} \mathbb{E}[M(G'2, \vec{\mu})] - 1. $$

*Proof* $\pi(m1, m2)$ will be the steady-state probability of state $(m1, m2)$. We decompose the summation on the state space:

$$ \mathbb{E}[M(G1 \bowtie G2), (\vec{\lambda}, \vec{\mu}), D)] = \sum_{x \in S1} |x| \pi^M(x, \emptyset) + \sum_{y \in S2} |y| \pi^M(\emptyset, y). $$

And

$$ \mathbb{E}[M(G'1, \vec{\lambda}, D)] = \sum_{x \in S1} |x| \pi^{M1}(x, \emptyset) + \pi_1^{M1}, $$

with a similar relation for $\mathbb{E}[M(G'2, \vec{\mu}, D)]$. After substitution and factorization, we get:

$$ \mathbb{E}[M(G1 \bowtie G2), (\vec{\lambda}, \vec{\mu}), D)] = \frac{\pi_0^M}{\pi_0^{M1}} \sum_{x \in S1} |x| \pi^{M1}(x, \emptyset) + \frac{\pi_0^M}{\pi_0^{M2}} \sum_{y \in S2} |y| \pi^{M2}(\emptyset, y). $$

As $\pi_1^{M1} = 2b\pi_0^{M1}$, $\pi_1^{M2} = 2a\pi_0^{M2}$ and $2(a+b) = 1$, we get the results after simple algebraic manipulations. $\square$

It is important to remark that the Markov chain associated with $G'1$ is not a lumped version of the DTMC associated with $G$. In general this Markov chain is not lumpable due to the possible matching between the items of $G2$. In the next subsection we study a simpler case where we have a strong aggregation of the DTMC and this leads to a lifting theorem for paradox.

## 4.2 Matching graphs $IS_{n1} \bowtie K_{n2}$

We consider a matching graph $G = IS_{n1} \bowtie K_{n2}$ with $n1 \ge 1$ and $n2 \ge 2$, the JOIN of an independent set with size $n1$ and a complete graph with size $n2$. We assume that the matching discipline is greedy. Let us first mention some graph theoretical results.

**Proposition 9** If $n2 \ge 2$, then $G$ is not bipartite. Indeed the graph contains at least one triangle.

**Proposition 10** Clearly: $IS_1 \bowtie K_n = K_{n+1}$.

One can generalize this result to composition of quasi-complete graphs.

**Lemma 9** Remember that $K_n$ – $(a, b)$ is the complete graph with size $n$ without the edge between node a and b. We have: $IS_1 \bowtie (K_n – (a, b)) = K_{n+1} – (a, b)$.
The proof of the above result is provided in Appendix C.2. It is important to remark that the Markov chain associated with $G'_1$ is not a lumped version of the DTMC associated with $G$. In general this Markov chain is not lumpable due to the possible matching between the items of $G_2$. In the next subsection we study a simpler case where we have a strong aggregation of the DTMC and this leads to a lifting theorem for the paradox.

## 4.2 Compatibility Graphs $IN_{n1} \bowtie K_{n2}$

We consider a compatibility graph $G = IN_{n1} \bowtie K_{n2}$ with $n1 \ge 1$ and $n2 \ge 2$, the JOIN of a set of $n1$ isolated nodes and a complete graph with size $n2$. We assume that the matching discipline is greedy and consistent. Let us first mention some results from graph theory. First, we have that, if $n2 \ge 2$, then $G$ is not bipartite; indeed, the graph contains at least one triangle. Furthermore, we also have that

$$ IN_1 \bowtie K_n = K_{n+1}. \qquad (14) $$

One can easily show that the latter result also holds for quasi-complete graphs, i.e.,

$$ IN_1 \bowtie (K_n - (a, b)) = K_{n+1} - (a, b). \qquad (15) $$

We begin with a result even more general for the state space of $IN_{n1} \bowtie G_{n2}$ where $G_{n2}$ is an arbitrary graph with size $n2$.

**Theorem 4** Consider a compatibility graph $G = IN_{n1} \bowtie G_{n2}$, arrival rates of letters $(\lambda, \mu)$ and an arbitrary consistent and greedy discipline $D$ as defined in section 4. Assume that $n1 > 1$ and $K_2 \subset G_{n2}$. We have uniformized the continuous time Markov chain with rate $\Lambda > \|\lambda\|_1 + \|\mu\|_1$ to obtain a discrete time model. This DTMC is lumpable for the following partition:

1. State $E$ remains unchanged

2. States $(\emptyset, Y)$ remain unchanged.

3. States $(X, \emptyset)$ are aggregated into macro-state $(|X|, \emptyset)$.

We aggregate all the nodes of the independent set into one macro state which is the length of the word. Let $\alpha_y = \lambda_y/\Lambda$ be the probability of an arrival of letters $y$ for the letters in the set of isolated nodes. $z$ will denote the aggregated letters of this set. The arrival probability of letter $z$ is $\alpha_z = \sum_{y=1}^{n1} \alpha_y$. The lumped Markov chain is associated with the compatibility graph $IN_1 \bowtie G_{n2}$ and discipline $D'$ which is derived from $D$ as in Section 3.

*Proof* As states $E$ and $(\emptyset, Y)$ for every word $Y$ remain unchanged, we just have to consider the macro states which contain the states $(X, \emptyset)$. Consider two arbitrary states $(X_1, \emptyset)$ and $(X_2, \emptyset)$ such that $|X_1| = |X_2| = k$. They are members of the same macro state $(k, \emptyset)$. We have two cases: arrival of a letter in $V(IN_{n1})$ or in $V(G_2)$.

* Consider the arrival of an arbitrary letter in $V(IN_{n1})$. The letter does not match with $X_1$ or $X_2$ as this part of the compatibility graph does not contain any edges. Therefore it provokes a transition to a state which is aggregated
Proof both graphs have $n + 1$ vertices. $IS_1 \succcurlyeq (K_n - (a,b))$ has $n$ edges between the node in $IS_1$ and the nodes in $(K_n - (a,b))$ and $n(n-1)/2 - 1$ vertices inside $(K_n - (a,b))$. $K_{n+1} - (a,b)$ contains $n(n+1)/2 - 1$ edges and it is the only graph with $n + 1$ vertices and such a number of edges. As both graphs also have the same number of vertices, and as such a graph is unique, both graphs are equal. □

We begin with a result even more general for the state space of $IS_{n1} \succcurlyeq G_{n2}$ where $G_{n2}$ is an arbitrary graph with size $n2$.

**Theorem 4** Consider a matching graph $G = IS_{n1} \succcurlyeq G_{n2}$, arrival rates of letters $(\bar{\lambda}, \bar{\mu})$ and an arbitrary consistent and greedy discipline D. Assume that $n1 > 1$ and $K_2 \subset G_{n2}$. We have uniformized the continuous time Markov chain with rate $\Lambda > \|\bar{\lambda}\|_1 + \|\bar{\mu}\|_1$ to obtain a discrete time model. This DTMC is lumpable for the following partition:

1. State E remains unchanged

2. States $(\emptyset, Y)$ remains unchanged.

3. States $(X, \emptyset)$ are aggregated into macro-state $(|X|, \emptyset)$.

We aggregate all the nodes of the independent set into one macro state which is the length of the word. Let $\alpha_y = \lambda_y/\Lambda$ be the probability of an arrival of letters $y$ for the letters in the independent set. $z$ will denote the aggregated letters of the independent set. The arrival of letter $z$ is $\alpha_z = \sum_{y=1}^{n1} \alpha_y$. The lumped Markov chain is associated with the matching graph $IS_1 \succcurlyeq G_{n2}$.

*Proof* As states $E$ and $(\emptyset, Y)$ for all word $Y$ remain unchanged, we just have to consider the macro states which contains the states $(X, \emptyset)$. Consider two arbitrary states $(X1, \emptyset)$ and $(X2, \emptyset)$ such that $|X1| = |X2| = k$. They are member of the same macro state $(k, \emptyset)$. We have two cases: arrival of a letter in $V(G1)$ or in $V(G2)$.

* Consider the arrival of an arbitrary letter in $V(G1)$. The letter does not match with $X1$ or $X2$ as this part of the matching graph is an independent set. Therefore it provokes a transition to a state which is aggregated into macro-state $(k+1, \emptyset)$ and the matching discipline is irelevent here as no matching occurs.

* Assume now an arrival of an arbitrary letter in $V(G2)$. A matching takes place and as the discipline is greedy and consistent, exactly one letter is deleted among the letters of $X1$ or $X2$. Therefore both states belong to macro state $(k-1, \emptyset)$.

Thus the lumpability conditions hold. □

As usual, both chains gives the same expectation.

**Corollary 4** Consider an arbitrary greedy and consistent discipline D. We have the same expectation for the total number of items for model $IS_1 \succcurlyeq G_{n2}$ and model
into macro-state $(k+1, \emptyset)$ and the matching discipline is irrelevant here as no matching occurs.

* Assume now an arrival of an arbitrary letter in $V(G_2)$. A matching takes place and as the discipline is greedy and consistent, exactly one letter is deleted among the letters of $X_1$ or $X_2$. Therefore both states belong to macro state $(k-1, \emptyset)$.

Thus the lumpability conditions hold.

As usual, both chains give the same expectation for the total number of letters.

**Corollary 1** Consider an arbitrary greedy and consistent discipline $D$. We have the same expectation for the total number of items for model $IN_1 \bowtie G_{n2}$ and model $IN_{n1} \bowtie G_{n2}$ assuming that $\beta_z = \sum_y \alpha_y$ for the arrivals of letters $z$ in $IN_1$ and $\beta_y = \alpha_y$ for $y$ in $G_{n2}$ for a discipline $D'$ derived from $D$.

$$ \mathbb{E}[M(IN_{n1} \bowtie G_{n2}, \alpha, D)] = \mathbb{E}[M((IN_1 \bowtie G_{n2}, \beta, D'))]. $$

In general, we are not able to analyze chain $M((IN_1 \bowtie G_{n2}, \beta, D'))$. However, we focus on some simple cases. First, we consider $G_2 = K_{n2}$, using Corollary 1 and (14), we obtain the following result.

**Corollary 2** Using the same transformation of arrival rates and matching disciplines, we get:

$$ \mathbb{E}[M(IN_{n1} \bowtie K_{n2}, \alpha, D)] = \mathbb{E}[M(K_{n2+1}, \beta, D')]. $$

We now consider $G_2 = K_{n2}$, using Corollary 1 and (15), we obtain:

**Corollary 3** We use the same transformation of arrival rates and matching disciplines and we obtain the same expectation for the total number of items for model $K_{n2+1} - (a, b)$ and model $IN_{n1} \bowtie (K_{n2} - (a, b))$.

$$ \mathbb{E}[M(IN_{n1} \bowtie K_{n2} - (a, b), \alpha, D)] = \mathbb{E}[M(K_{n2+1} - (a, b), \beta, D')]. $$

And the existence of a paradox follows:

**Theorem 5** If there exists a paradox between compatibility graph $K_{n2+1}$ and $K_{n2+1} - (a, b)$ for a greedy and consistent discipline, the same (i.e. we keep the same arrival rates for letters in $K_{n2}$) paradox exists between $IN_{n1} \bowtie K_{n2}$ and $IN_{n1} \bowtie (K_{n2} - (a, b))$.

*Proof* Corollary 2 proves that $K_{n2+1}$ and $IN_{n1} \bowtie K_{n2}$ have the same expectation for total number of items, while Corollary 3 establishes the same relation for chains
26 Performance Paradox of Dynamic Matching Models under Greedy Policies

$IS_{n1} \bowtie G_{n2}$ assuming that $\beta_z = \sum_y \alpha_y$ for the arrivals of letters $z$ in $IS_1$ and $\beta_y = \alpha_y$ for $y$ in $G_{n2}$.

$$ \mathbb{E}[M((IS_{n1} \bowtie G_{n2}, \vec{\alpha}, D))] = \mathbb{E}[M((IS_1 \bowtie G_{n2}, \vec{\beta}, D))] $$

In general, we are not able to analyze chain $M((IS_1 \bowtie G_{n2}, \vec{\beta}, D))$. However in some simple cases, the results of the previous sections may help for the next two corollaries:

**Corollary 5** Consider an arbitrary greedy and consistent discipline D. We have the same expectation for the total number of items for model $K_{n2+1}$ and model $IS_{n1} \bowtie K_{n2}$ assuming that $\alpha_x = \sum_y \alpha_y$ for the arrivals of letters initially in $IS_{n1}$.

$$ \mathbb{E}[M((IS_{n1} \bowtie K_{n2}, \vec{\alpha}, D))] = \mathbb{E}[M(K_{n2+1}, \vec{\beta}, D)]. $$

*Proof* Taking $G_2 = K_2$ in Theorem 4 and Corollary 4 and using finally Lemma 11. $\square$

<figure><img src="image_16.png" /></figure>

**Corollary 6** Consider an arbitrary greedy and consistent discipline D. We have the same expectation for the total number of items for model $K_{n2+1} - (a, b)$ and model $IS_{n1} \bowtie (K_{n2} - (a, b))$ assuming that $\alpha_z = \sum_y \alpha_y$ for the arrivals of letters initially in $IS_{n1}$.

$$ \mathbb{E}[M((IS_{n1} \bowtie K_{n2}, \vec{\alpha}, D))] = \mathbb{E}[M(K_{n2+1}, \vec{\beta}, D)]. $$

*Proof* First we use Theorem 4 with $G_2 = (K_{n2} - (a, b))$ to prove the lumpability and Corollary 4 to prove that the models associated with $IS_{n1} \bowtie (K_{n2} - (a, b))$ and $IS_1 \bowtie (K_{n2} - (a, b))$ have the same expectation of total number of items for any greedy discipline. Then we use Lemma 9 to complete the proof. $\square$

<figure><img src="image_17.png" /></figure>

And the existence of a paradox follows:

**Theorem 5** If there exists a paradox between matching graph $K_{n2+1}$ and $K_{n2+1} - (a, b)$ for a greedy and consistent discipline, the same (i.e. we keep the same arrival rates for letters in $K_{n2}$) paradox exists between $IS_{n1} \bowtie K_{n2}$ and $IS_{n1} \bowtie (K_{n2} - (a, b))$ for the same discipline.

*Proof* based on the corollaries. Corollary 5 proves that $K_{n2+1}$ and $IS_{n1} \bowtie K_{n2}$ have the same expectation for total number of items, while Corollary 6 establish the same relation for chains associated with matching graphs $K_{n2+1} - (a, b)$ and $IS_{n1} \bowtie (K_{n2} - (a, b))$. Thus if a paradox exists between $K_{n2+1}$ and $K_{n2+1} - (a, b)$, it also exists between $K_{n2+1} - (a, b)$ and $IS_{n1} \bowtie (K_{n2} - (a, b))$. $\square$

<figure><img src="image_18.png" /></figure>

**Corollary 7** For all $n \ge 4$, there exist some matching graph with size $n$ which exhibits a paradox for any discipline D.
26 Performance Paradox of Dynamic Matching Models under Greedy Policies

associated with compatibility graphs $K_{n2+1} - (a, b)$ and $IN_{n1} \bowtie (K_{n2} - (a, b))$. Thus if a paradox exists between $K_{n2+1}$ and $K_{n2+1} - (a, b)$, it also exists between $K_{n2+1} - (a, b)$ and $IN_{n1} \bowtie (K_{n2} - (a, b))$. $\square$

**Corollary 4** For all $n \ge 4$, there exists a compatibility graph with size $n$ which exhibits a paradox for any discipline D.

*Proof* For $n = 4$, we give the example for FCFM discipline for compatibility graph $K_4 - (3, 4)$ in Section 2.2 and we generalize to in Section 3 to any discipline D. For larger $n$, we consider compatibility graph $IN_{n-4} \bowtie (K_4 - (3, 4))$ and Theorem 5 proves the claim with the previous results on $K_4 - (3, 4)$. $\square$

**Remark 10** Note that the number of edges in graph $K_{n1} \bowtie (K_4 - (3, 4))$ is only $4n_1 + 5$. With $n = n_1 + 4$, we have a compatibility graph for all $n$ with a graph with $n > 3$ nodes and $4n - 11$ edges. Thus the average degree is asymptotically 4.

**Lemma 5** If compatibility graph G with discipline FCFM satisfies the assumption of Theorem 1, then matching graph G $\bowtie IN_1$ with discipline FCFM also satisfies the same assumptions when the arrival probability of the letter in $IN_1$ is sufficiently small. Therefore compatibility graph G $\bowtie IN_1$ also exhibits a performance paradox.

*Proof* Let $x$ be the letter of $IN_1$. And $\alpha^\delta$ the arrival probabilities for graph G. We have to prove that the assumptions of Theorem 1 on the saturated independent sets are still valid for $G \bowtie \{x\}$. First, the independent sets of $G \bowtie IN_1$ are the independent sets of G and $\{x\}$. Let us consider the following arrival probabilities for graph $G \bowtie \{x\}$:

$$ \beta_0^\delta = \alpha_0^\delta(1 - \delta), \quad \beta_x^\delta = \alpha_0^\delta\delta, \quad \beta_y^\delta = \alpha_y^\delta \quad \forall y \in V(G). $$

As $\alpha^\delta$ is a probability distribution, $\beta^\delta$ is also a probability distribution when $\delta < 1$. Now we have to compute the stability gap for all independent sets of $G \bowtie \{x\}$. We slightly change the notation about the stability gap as follows: $\Delta_G(\mathcal{I})$ will denote the stability gap of independent set $\mathcal{I}$ in graph G. Let us begin with $\{x\}$. All the nodes of G are neighbors of $x$. Thus:

$$ \Delta_{\{x\}}^{G \bowtie \{x\}} = \sum_{y \in V(G)} \beta_y - \beta_x = \sum_{y \in V(G)} \alpha_y - \alpha_0\delta = 1 - \alpha_0 - \alpha_0\delta. $$

Therefore, $\{x\}$ is not a saturated independent set. Now consider any independent set $\mathcal{I}$ of $G \bowtie \{x\}$ which is also an independent set of G. $\mathcal{I}$ does not contain $x$, unlike $\Gamma(\mathcal{I})$. Therefore, due to the arrival probabilities we considered:

$$ \Delta_{\mathcal{I}}^{G \bowtie \{x\}} = \Delta_{\mathcal{I}}^{G} + \alpha_0\delta. $$

Clearly, as the transformation of the gaps keep unchanged the saturated independent set and if we have only one saturated independent set in G, we have only one saturated independent set in $G \bowtie \{x\}$. Therefore the assumptions of Theorem 1 are still valid for the graph we have designed. $\square$
**Proof** For $n = 4$, we give the example for FCFM discipline for matching graph $K_4 - (3, 4)$ in section 2.2 and we generalize to in Section 3 to any discipline $D$. For larger $n$, we consider matching graph $IS_{n-4} \bowtie (K_4 - (3, 4))$ and Theorem 5 proves the claim with the previous results on $K_4 - (3, 4)$. $\square$

**Lemma 10** If matching graph $G$ with discipline FCFM satisfies the assumption of Theorem 1, then matching graph $G \bowtie IS_1$ with discipline FCFM also satisfies the same assumptions when the arrival probability of the letter in $IS_1$ is sufficiently small. Therefore matching graph $G \bowtie IS_1$ also exhibits a performance paradox.

**Proof** Let $x$ be the letter of $IS_1$. And $\alpha^\delta$ the arrival probabilities for graph $G$. We have to prove that the assumptions of Theorem 1 on the saturated independent sets are still valid for $G \bowtie \{x\}$. First, the independent sets of $G \bowtie IS_1$ are the independent sets of $G$ and $\{x\}$. Let us consider the following arrival probabilities for graph $G \bowtie \{x\}$:

$$ \beta_0^\delta = \alpha_0^\delta(1-\delta), \quad \beta_x^\delta = \alpha_0^\delta\delta, \quad \beta_y^\delta = \alpha_y^\delta \quad \forall y \in V(G). $$

As $\alpha^\delta$ is a probability distribution, $\beta^\delta$ is also a probability distribution when $\delta < 1$. Now we have to compute the stability gap for all independent sets of $G \bowtie \{x\}$. We slightly change the notation about the stability graph to add the graph as we build the graph. $\Delta_G(\mathcal{I})$ will denote the stability gap of independent set $\mathcal{I}$ in graph $G$. Let us begin with $\{x\}$. All the nodes of $G$ are neighbors of $x$. Thus:

$$ \Delta_{\{x\}}^{G \bowtie \{x\}} = \sum_{y \in V(G)} \beta_y - \beta_x = \sum_{y \in V(G)} \alpha_y - \alpha_0\delta = 1 - \alpha_0 - \alpha_0\delta. $$

Therefore, $\{x\}$ is not a saturated independent set. Now consider any independent set $\mathcal{I}$ of $G \bowtie \{x\}$ which is also an independent set of $G$. $\mathcal{I}$ does not contain $x$, unlike $\Gamma(\mathcal{I})$. Therefore, due to the arrival probabilities we considered:

$$ \Delta_{\mathcal{I}}^{G \bowtie \{x\}} = \Delta_{\mathcal{I}}^{G} + \alpha_0\delta. $$

Clearly, as the transformation of the gaps keep unchanged the saturated independent set and if we have only one saturated independent set in $G$, we have only one saturated independent set in $G \bowtie \{x\}$. Therefore the assumptions of Theorem 1 are still valid for the graph we have designed. $\square$

## 4.3 Matching graph $IS_{n1} \bowtie (G2 \cup G1)$

Assume now the following decomposition for the matching graph into three subgraphs:

$$ G = IS_{n1} \bowtie (G1 \cup G2), $$

where $G1$ and $G2$ are non empty. We now establish that $G$ may have some paradox if one of the sub-models exhibits performance paradox.

**Proposition 11** Consider an arbitrary greedy matching discipline $D$. Assume that the matching graph $G$ is the UNION of $G1$ and $G2$. Let $\bar{\lambda}$ and $\bar{\mu}$ be respectively
**Corollary 5** Using existence of a paradox for discipline FCFM and compatibility graph $K_4-(3, 4)$, Lemma 5 implies that a performance paradox exists for compatibility graph $K_n - (n-1, n)$ and discipline FCFM for any $n$.

*Proof* The proof is an induction on $n$ based on Lemma 5 and Eq. 14 and 15 to build the graphs adding one node at each step of the induction. □

Then combining this last corollary with Theorem 2, we prove that a performance paradox exists for compatibility graph $K_n - (n-1, n)$ for all greedy disciplines and size $n$.

**Corollary 6** If a discipline does not exhibit such a paradox for graph $K_n-(n-1,n)$, for some $\lambda$, then this discipline is not greedy.

## 4.3 Compatibility Graph $IN_{n1} \bowtie (G_2 \cup G_1)$

Assume now the following decomposition for the compatibility graph into three subgraphs:

$$G = IN_{n1} \bowtie (G_1 \cup G_2),$$

where $G_1$ and $G_2$ are distinct and non empty. We now establish that $G$ may have some paradox if one of the sub-models exhibits a performance paradox. Again we assume that all the Markov chains considered in this section are ergodic.

<figure><img src="image_10.png" /><figcaption>**Fig. 9:** Graph $G = IN_1 \bowtie (K_2 \cup IN_3)$, $IN_1$ contains node 4. We note that $G$ is connected while the subgraphs $IN_1$ and $IN_3$ are not.</figcaption></figure>

**Proposition 8** Consider an arbitrary greedy and consistent matching discipline D. Assume that the compatibility graph G is the UNION of $G_1$ and $G_2$. Let $\lambda$ and $\mu$ be respectively the arrival rates associated with $G_1$ and $G_2$. Then:

$$M(G_1 \cup G_2, (\lambda, \mu), D) = M(G_1, \lambda, D) \oplus M(G_2, \mu, D),$$

where $\oplus$ is the tensor (or Kronecker sum).
<figure><img src="image_19.png" /><figcaption>**Fig. 10** Graph $G = IS_1 \bowtie (K_2 \cup IS_3)$, $IS_1$ contains node 4. Remark that $G$ is connected while the subgraphs $IS_1$ and $IS_3$ are not.</figcaption></figure>

the arrival rates of times associated with G1 and G2. Assume that Markov chains $M(G1, \vec{\lambda}, D)$ and $M(G2, \vec{\mu}, D)$ are ergodic. Then:

$$M(G1 \cup G2, (\vec{\lambda}, \vec{\mu}), D) = M(G1, \vec{\lambda}, D) \oplus M(G2, \vec{\mu}, D),$$

where $\oplus$ is the tensor (or Kronecker sum).

*Proof* As the items in G1 and G2 does not interact, we have built two independent continuous-time Markov chains. And it is well known (see for instance the literature on Stochastic Automata Networks (see for example [21] and references therein) that the resulting Markov chains is the Kronecker sum of the components. $\square$

**Corollary 8** Because of independence of the Markov chains associated with G1 and G2, we clearly have:

$$\mathbb{E}[(G1 \cup G2)), (\vec{\lambda}, \vec{\mu}), D)] = \mathbb{E}[M(G1, \vec{\lambda}, D)] \times \mathbb{E}[M(G2, \vec{\mu}, D)].$$

Therefore if a paradox exist for matching graph G1 and discipline D, it also exists for matching graph $G1 \cup G2$ and discipline D.

**Lemma 11** Assume that G1 with FCFM matching discipline satisfies the assumptions of Theorem 1 for vector of arrival rates $\vec{\mu}$. Assume also that G2 with vector of arrival rates $\vec{\nu}$ does not contain any saturated independent set for FCFM matching discipline. Then $G1 \cup G2$ with FCFM discipline and vector of arrivals $(\vec{\mu}, \vec{\nu})$ satisfies the assumptions of Theorem 1.

*Proof* The independent sets of $G1 \cup G2$ are:

* the independent sets of $G1$,

* the independent sets of $G2$,

* all the sets which are the union of an independent set of $G1$ and an independent set of $G2$.

Therefore the saturated independent set of $G1$ is also a saturated independent set of $G1 \cup G2$. We now have to check that $G1 \cup G2$ contains only one saturated independent set. As $G2$ does not have a saturated independent set, there exists $\Delta > 0$ such that all the stability gap of independent sets of $G2$ are larger than $\Delta$. Let $\mathcal{I}1$ be
28 Performance Paradox of Dynamic Matching Models under Greedy Policies

Proof As the items in $G_1$ and $G_2$ do not interact, we have built two independent continuous-time Markov chains. And it is well known (see for instance the literature on Stochastic Automata Networks, for example [25] and references therein) that the resulting Markov chains is the Kronecker sum of the components. □

**Corollary 7** Because of the independence of the Markov chains associated with $G_1$ and $G_2$, we clearly have:

$$ \mathbb{E}[M(G_1 \cup G_2), (\lambda, \mu), D)] = \mathbb{E}[M(G_1, \lambda, D)] + \mathbb{E}[M(G_2, \mu, D)]. $$

Therefore if a paradox exist for compatibility graph $G_1$ and discipline $D$, it also exists for compatibility graph $G_1 \cup G_2$ and discipline $D$.

**Lemma 6** Assume that $G_1$ with FCFM matching discipline satisfies the assumptions of Theorem 1 for vector of arrival rates $\mu$. Assume also that $G_2$ with vector of arrival rates $\lambda$ does not contain any saturated independent set for FCFM matching discipline. Then $G_1 \cup G_2$ with FCFM discipline and vector of arrivals $(\mu, \lambda)$ satisfies the assumptions of Theorem 1.

**Proof** The independent sets of $G_1 \cup G_2$ are:

* the independent sets of $G_1$,

* the independent sets of $G_2$,

* all the sets which are the union of an independent set of $G_1$ and an independent set of $G_2$.

Therefore the saturated independent set of $G_1$ is also a saturated independent set of $G_1 \cup G_2$. We now have to check that $G_1 \cup G_2$ contains only one saturated independent set. As $G_2$ does not have a saturated independent set, there exists $\Delta > 0$ such that all the stability gaps of independent sets of $G_2$ are larger than $\Delta$. Let $\mathcal{I}_1$ be an independent set of $G_1$ and $\mathcal{I}_2$ an independent set of $G_2$. $\mathcal{I}_2$ is not saturated by assumption and clearly, due to the UNION operation:

$$ \Delta_{\mathcal{I}_1 \cup \mathcal{I}_2}^{G_1 \bowtie G_2} = \Delta_{\mathcal{I}_1}^{G_1} + \Delta_{\mathcal{I}_2}^{G_2}. $$

Therefore as $\Delta_{\mathcal{I}_2}^{G_2} \ge \Delta$, $\mathcal{I}_1 \cup \mathcal{I}_2$ cannot be saturated. Thus the saturated independent set of $G_1$ is the saturated independent set of $G_1 \cup G_2$. □

Remember that $G_1 \cup G_2$ is not connected. However we can build connected compatibility graphs with UNION and JOIN operations. The following result is a simple corollary of Remark 8.

**Lemma 7** (State Space) Let $G_3 \bowtie (G_1 \cup G_2)$, then the states of the Markov chain associated with $G$ are

* State $E$,

* states $(X, \emptyset, \emptyset)$ where $X$ is a state of the chain associated with $G_3$,

* states $(\emptyset, Y, Z)$ where $Y$ (resp. $Z$) is a state of the chain associated with $G_1$ (resp. $G_2$),
an independent set of $G1$ and $I2$ an independent set of $G2$. $I2$ is not saturated by assumption and clearly, due to the UNION operation:

$$ \Delta_{I1 \cup I2}^{G1 \times G2} = \Delta_{I1}^{G1} + \Delta_{I2}^{G2}. $$

Therefore as $\Delta_{I2}^{G2} \ge \Delta$, $I1 \cup I2$ cannot be saturated. Thus the saturated independent set of $G1$ is the saturated independent set of $G1 \cup G2$. $\square$

Remember that $G1 \cup G2$ is not connected. However we can build connected matching graphs with UNION and JOIN operations. The following result is a simple corollary of Lemma 7.

**Lemma 12 (State Space)** Let $G3 \bowtie (G1 \cup G2)$, then the states of the Markov chain associated with $G$ are

* State $E$,

* states $(\vec{X}, \vec{0}, \vec{0})$ where $\vec{X}$ is a state of the chain associated with $G2$,

* states $(\vec{0}, \vec{Y}, \vec{Z})$ where $\vec{Y}$ (resp. $\vec{Z}$) is a state of the chain associated with $G1$ (resp. $G2$),

**Theorem 6** We assume FCFM matching discipline and that matching graph $G1$ satisfies the assumptions of Theorem 1. Let $\vec{\mu}$ the arrival rates associated with this paradox for $G1$. Then, we also have a performance paradox for matching graph $IS_{n1} \bowtie (G1 \cup G2)$ associated with arrival rate vectors $(\vec{\lambda}, \vec{\mu}, \vec{\nu})$ and FCFM discipline.

*Proof* We first aggregate all the nodes of $IS_{n1}$ into one single node because the associated chain is lumpable. According to Theorem 4, using discipline FCFM

$$ \mathbb{E}[M((IS_{n1} \bowtie (G1 \cup G2)), (\vec{\lambda}, \vec{\mu}, \vec{\nu}), \text{FCFM})] = \mathbb{E}[M((IS_1 \bowtie (G1 \cup G2)), \vec{\beta}, \text{FCFM})], $$
with $\vec{\beta} = (\sum \lambda, \vec{\mu}, \vec{\nu})$. Lemma 11 shows that as soon as the assumptions of Theorem 1 hold for $G1$, $G1 \cup G2$ also satisfies the same assumptions and the matching graph $IS_1 \bowtie (G1 \cup G2)$ also exhibits a paradox for FCFM discipline according to Lemma 10. $\square$

# 5 Conclusions

We consider the dynamic matching model with a non-bipartite matching graph and we analyze the existence of a performance degradation when the flexibility increases, i.e., when we add an edge to the matching graph. This analysis can be seen as an analogous to the Braess paradox in matching models. We first focus on the FCFM discipline and an arbitrary matching graph. For this case, we provide sufficient conditions on the existence of a performance paradox. Then, the performance paradox existence study is extended to greedy disciplines, which is a large family of matching disciplines that includes, not only FCFM, but also other popular disciplines such as Match the Longest and Random. For this instance, we provide conditions on the matching graph for the existence of a performance paradox.
**Theorem 6** We assume the FCFM matching discipline and that compatibility graph $G_1$ satisfies the assumptions of Theorem 1. Let $\mu$ be the vector of arrival rates associated with this paradox for $G_1$. Then, we also have a performance paradox for compatibility graph $IN_{n1} \bowtie (G_1 \cup G_2)$ associated with arrival rate vector $(\lambda, \mu, \nu)$ and FCFM discipline.

*Proof* We first aggregate all the nodes of $IN_{n1}$ into one single node because the associated chain is lumpable. According to Theorem 4, using discipline FCFM

$$ \mathbb{E}[M((IN_{n1} \bowtie (G_1 \cup G_2)), (\lambda, \mu, \nu), \text{FCFM})] = \mathbb{E}[M((IN_1 \bowtie (G_1 \cup G_2)), \beta, \text{FCFM})], $$
with $\beta = (\lambda, \mu, \nu)$. Lemma 6 shows that as soon as the assumptions of Theorem 1 hold for $G_1, G_1 \cup G_2$ also satisfies the same assumptions and the compatibility graph $IN_1 \bowtie (G_1 \cup G_2)$ also exhibits a paradox for FCFM discipline according to Lemma 5. $\square$

# 5 Conclusions

We consider the dynamic matching model with a non-bipartite matching graph and we analyze the existence of a performance degradation when the flexibility increases, i.e., when we add an edge to the matching graph. This analysis can be seen as analogous to the Braess paradox. In our previous work, we focused on the FCFM discipline and an arbitrary matching graph and we provided sufficient conditions on the existence of a performance paradox. In this work, the performance paradox existence study is extended to greedy disciplines, which is a large family of matching disciplines that includes, not only FCFM, but also other popular disciplines such as Match the Longest and Random. We provide constructions for families of graphs with performance paradox.

As future work, we are interested in exploring the existence of a performance paradox for other compatibility graphs. We also plan to study the existence of a performance paradox for greedy policies for the related bipartite stochastic matching model.

# Appendix A Appendix of Section 2.3

## A.1 Computations for the Example

We first note that, because $\alpha_1^\delta = 0.5 - \frac{\delta}{2}$, $\alpha_2^\delta = 0.1 + \frac{\delta}{10}$ and $\alpha_3^\delta = \alpha_4^\delta = 0.2 + \frac{\delta}{5}$, we obtain from (5) that the mean number of items of the complete graph under any greedy policy is

$$ \mathbb{E}[M(K_4, \alpha^\delta, \text{FCFM})] = \frac{2 \frac{(0.8 - \frac{\delta}{5})(0.2 + \frac{\delta}{5})}{(0.6 - \frac{2\delta}{5})^2} + \frac{(0.5 + \frac{\delta}{2})(0.5 - \frac{\delta}{2})}{\delta^2} + \frac{(0.9 - \frac{\delta}{10})(0.1 + \frac{\delta}{10})}{(0.8 - \frac{\delta}{5})^2}}{1 + 2 \frac{0.2 + \frac{\delta}{5}}{0.6 - \frac{2\delta}{5}} + \frac{0.5 - \frac{\delta}{2}}{\delta} + \frac{0.1 + \frac{\delta}{10}}{0.8 - \frac{\delta}{5}}}. $$
30 Performance Paradox of Dynamic Matching Models under Greedy Policies

As future work, we are interested in studying the existence of a perfor-
mance paradox for a broader family of matching disciplines than the greedy
disciplines. We are also interested in exploring the existence of a perfor-
mance paradox in matching graphs with less number of edges. Finally, another
interesting extension of this work consists of analyzing the existence of a
performance paradox when the matching in bipartite in a general setting.

Appendix A Computations for the example

We first note that, using that $\alpha_1^\delta = 0.5 - \frac{\delta}{2}$, $\alpha_2^\delta = 0.1 + \frac{\delta}{10}$ and $\alpha_3^\delta = \alpha_4^\delta = 0.2 + \frac{\delta}{5}$, we obtain from (5) that the mean number of items of the complete graph under any greedy policy is

$$
\mathbb{E}[M(K_4, \alpha^\delta, FCFM)] = \frac{2 \frac{(0.8 - \frac{\delta}{5})(0.2 + \frac{\delta}{5})}{(0.6 - \frac{2\delta}{5})^2} + \frac{(0.5 + \frac{\delta}{2})(0.5 - \frac{\delta}{2})}{\delta^2} + \frac{(0.9 - \frac{\delta}{10})(0.1 + \frac{\delta}{10})}{(0.8 - \frac{\delta}{5})^2}}{1 + 2 \frac{0.2 + \frac{\delta}{5}}{0.6 - \frac{2\delta}{5}} + \frac{0.5 - \frac{\delta}{2}}{\delta} + \frac{0.1 + \frac{\delta}{10}}{0.8 - \frac{\delta}{5}}}
$$

And using (6), we get that the mean number of items of the quasi complete
graph under any greedy policy is

$$
\mathbb{E}[M(K_4 - (3,4), \alpha^{\delta}, FCFM)] = \frac{\frac{(0.6 - \frac{2\delta}{5})(0.4 + \frac{2\delta}{5})}{(0.2 - \frac{4\delta}{5})^2} + \frac{(0.5 + \frac{\delta}{2})(0.5 - \frac{\delta}{2})}{\delta^2} + \frac{(0.9 - \frac{\delta}{10})(0.1 + \frac{\delta}{10})}{(0.8 - \frac{\delta}{5})^2}}{1 + \frac{0.4 + \frac{2\delta}{5}}{0.2 - \frac{4\delta}{5}} + \frac{0.5 - \frac{\delta}{2}}{\delta} + \frac{0.1 + \frac{\delta}{10}}{0.8 - \frac{\delta}{5}}}
$$

We study the sign of $\mathbb{E}[M(K_4, \alpha^\delta, FCFM)] - \mathbb{E}[M(K_4 - (3,4), \alpha^\delta, FCFM)]$,
which is the same as the sign of

$$
\begin{aligned}
& \left( 2 \frac{(0.8 - \frac{\delta}{5})(0.2 + \frac{\delta}{5})}{(0.6 - \frac{2\delta}{5})^2} + \frac{(0.5 + \frac{\delta}{2})(0.5 - \frac{\delta}{2})}{\delta^2} + \frac{(0.9 - \frac{\delta}{10})(0.1 + \frac{\delta}{10})}{(0.8 - \frac{\delta}{5})^2} \right) \\
& \left( 1 + \frac{0.4 + \frac{2\delta}{5}}{0.2 - \frac{4\delta}{5}} + \frac{0.5 - \frac{\delta}{2}}{\delta} + \frac{0.1 + \frac{\delta}{10}}{0.8 - \frac{\delta}{5}} \right) \\
& - \left( \frac{(0.6 - \frac{2\delta}{5})(0.4 + \frac{2\delta}{5})}{(0.2 - \frac{4\delta}{5})^2} + \frac{(0.5 + \frac{\delta}{2})(0.5 - \frac{\delta}{2})}{\delta^2} + \frac{(0.9 - \frac{\delta}{10})(0.1 + \frac{\delta}{10})}{(0.8 - \frac{\delta}{5})^2} \right) \\
& \left( 1 + 2 \frac{0.2 + \frac{\delta}{5}}{0.6 - \frac{2\delta}{5}} + \frac{0.5 - \frac{\delta}{2}}{\delta} + \frac{0.1 + \frac{\delta}{10}}{0.8 - \frac{\delta}{5}} \right).
\end{aligned}
$$

Simplifying this expression using Wolfram Mathematica, we obtain the
following:

$$
\frac{1}{\delta^3 (-4 + \delta)^3 (0.375 - 1.75\delta + \delta^2)^2}
$$
And using (10), we get that the mean number of items of the quasi complete graph under any greedy policy is

$$ \mathbb{E}[M(K_4-(3,4), \alpha^{\delta}, FCFM)] = \frac{\frac{(0.6-\frac{2\delta}{5})(0.4+\frac{2\delta}{5})}{(0.2-\frac{4\delta}{5})^2} + \frac{(0.5+\frac{\delta}{2})(0.5-\frac{\delta}{2})}{\delta^2} + \frac{(0.9-\frac{\delta}{10})(0.1+\frac{\delta}{10})}{(0.8-\frac{\delta}{5})^2}}{1 + \frac{0.4+\frac{2\delta}{5}}{0.2-\frac{4\delta}{5}} + \frac{0.5-\frac{\delta}{2}}{\delta} + \frac{0.1+\frac{\delta}{10}}{0.8-\frac{\delta}{5}}}. $$

We study the sign of $\mathbb{E}[M(K_4, \alpha^{\delta}, FCFM)] - \mathbb{E}[M(K_4 - (3,4), \alpha^{\delta}, FCFM)]$, which is the same as the sign of

$$ \left( 2 \frac{(0.8 - \frac{\delta}{5})(0.2 + \frac{\delta}{5})}{(0.6 - \frac{2\delta}{5})^2} + \frac{(0.5 + \frac{\delta}{2})(0.5 - \frac{\delta}{2})}{\delta^2} + \frac{(0.9 - \frac{\delta}{10})(0.1 + \frac{\delta}{10})}{(0.8 - \frac{\delta}{5})^2} \right) \left( 1 + \frac{0.4 + \frac{2\delta}{5}}{0.2 - \frac{4\delta}{5}} + \frac{0.5 - \frac{\delta}{2}}{\delta} + \frac{0.1 + \frac{\delta}{10}}{0.8 - \frac{\delta}{5}} \right) - \left( \frac{(0.6 - \frac{2\delta}{5})(0.4 + \frac{2\delta}{5})}{(0.2 - \frac{4\delta}{5})^2} + \frac{(0.5 + \frac{\delta}{2})(0.5 - \frac{\delta}{2})}{\delta^2} + \frac{(0.9 - \frac{\delta}{10})(0.1 + \frac{\delta}{10})}{(0.8 - \frac{\delta}{5})^2} \right) \left( 1 + 2 \frac{0.2 + \frac{\delta}{5}}{0.6 - \frac{2\delta}{5}} + \frac{0.5 - \frac{\delta}{2}}{\delta} + \frac{0.1 + \frac{\delta}{10}}{0.8 - \frac{\delta}{5}} \right). $$

Simplifying this expression using Wolfram Mathematica, we obtain the following:

$$ \frac{1}{\delta^3(-4 + \delta)^3(0.375 - 1.75\delta + \delta^2)^2} \times (-2.22045 \cdot 10^{-16} - 3\delta + 33.25\delta^2 + 45.25\delta^3 - 41.0937\delta^4 - 38.0625\delta^5 + 27\delta^6 + 1.6875\delta^7 - 9.90625\delta^8 + 3.125\delta^9 - 0.25\delta^{10}). $$

We note that $(0.375 - 1.75\delta + \delta^2)^2 > 0$ when $0 < \delta \le 0.1$. Thus, since

$$ \frac{1}{\delta^3(-4 + \delta)^3(0.375 - 1.75\delta + \delta^2)^2} < 0 $$

when $0 < \delta \le 0.1$, the sign of $\mathbb{E}[M(K_4, \alpha^{\delta}, FCFM)] - \mathbb{E}[M(K_4 - (3,4), \alpha^{\delta}, FCFM)]$ is the opposite of the sign of the polynomial of degree 10:

$$ -2.22045 \cdot 10^{-16} - 3\delta + 33.25\delta^2 + 45.25\delta^3 - 41.0937\delta^4 - 38.0625\delta^5 + 27\delta^6 + 1.6875\delta^7 - 9.90625\delta^8 + 3.125\delta^9 - 0.25\delta^{10}. $$

Using Wolfram Mathematica, we know that this polynomial has one real root between 0 and 0.1, which is 0.0818369. Also, if $0 < \delta \le 0.0818369$, the polynomial is negative and positive otherwise. Therefore, the desired result follows.
$$ \times (-2.22045 \cdot 10^{-16} - 3\delta + 33.25\delta^2 + 45.25\delta^3 - 41.0937\delta^4 - 38.0625\delta^5 + 27\delta^6 + 1.6875\delta^7 - 9.90625\delta^8 + 3.125\delta^9 - 0.25\delta^{10}). $$

We note that $(0.375 - 1.75\delta + \delta^2)^2 > 0$ when $0 < \delta \le 0.1$. Thus, since

$$ \frac{1}{\delta^3(-4 + \delta)^3(0.375 - 1.75\delta + \delta^2)^2} $$

is negative when $0 < \delta \le 0.1$, the sign of $\mathbb{E}[M(K_4, \alpha^\delta, FCFM)] - \mathbb{E}[M(K_4 - (3, 4), \alpha^\delta, FCFM)]$ is the opposite of the sign of the polynomial of degree 10:

$$ -2.22045 \cdot 10^{-16} - 3\delta + 33.25\delta^2 + 45.25\delta^3 - 41.0937\delta^4 - 38.0625\delta^5 + 27\delta^6 + 1.6875\delta^7 - 9.90625\delta^8 + 3.125\delta^9 - 0.25\delta^{10} $$

Using Wolfram Mathematica, we know that this polynomial has one real root between 0 and 0.1, which is 0.0818369. Besides, if $0 < \delta \le 0.0818369$, the polynomial is negative and positive otherwise. Therefore, the desired result follows.

## Appendix B Proof of Proposition 2

Using (5), we obtain from the definition of $\alpha^\delta$ that the mean number of items of the complete graph under any greedy policy is

$$ \mathbb{E}[M(K_4 - (3, 4), \alpha^\delta, FCFM)] = \frac{\frac{(0.5-2\delta)(0.5+2\delta)}{(4\delta)^2} + \frac{(0.5-\delta)(0.5+\delta)}{(2\delta)^2} + \frac{3\delta(1-3\delta)}{(1-6\delta)^2}}{1 + \frac{0.5-2\delta}{4\delta} + \frac{0.5-\delta}{2\delta} + \frac{3\delta}{1-6\delta}} $$

Likewise, using (6) and the definition $\alpha^\delta$, it results

$$ \mathbb{E}[M(K_4, \alpha^\delta, FCFM)] = \frac{2\frac{(0.25-\delta)(0.75+\delta)}{(0.5+2\delta)^2} + \frac{(0.5-\delta)(0.5+\delta)}{(2\delta)^2} + \frac{3\delta(1-3\delta)}{(1-6\delta)^2}}{1 + 2\frac{0.25-\delta}{0.5+2\delta} + \frac{0.5-\delta}{2\delta} + \frac{3\delta}{1-6\delta}} $$

We now study the sign of $\mathbb{E}[M(K_4 - (3, 4), \alpha^\delta, FCFM)] - \mathbb{E}[M(K_4, \alpha^\delta, FCFM)]$, which is the same as the sign of

$$ \left( \frac{(0.5 - 2\delta)(0.5 + 2\delta)}{(4\delta)^2} + \frac{(0.5 - \delta)(0.5 + \delta)}{(2\delta)^2} + \frac{3\delta(1 - 3\delta)}{(1 - 6\delta)^2} \right) \left( 1 + 2\frac{0.25 - \delta}{(0.5 + 2\delta)} + \frac{0.5 - \delta}{2\delta} + \frac{3\delta}{1 - 6\delta} \right) - \left( 2\frac{(0.25 - \delta)(0.75 + \delta)}{(0.5 + 2\delta)^2} + \frac{(0.5 - \delta)(0.5 + \delta)}{(2\delta)^2} + \frac{3\delta(1 - 3\delta)}{(1 - 6\delta)^2} \right) \left( 1 + \frac{0.5 - 2\delta}{4\delta} + \frac{0.5 - \delta}{2\delta} + \frac{3\delta}{1 - 6\delta} \right). \quad (B1) $$
## A.2 Representation of the Expected Number of Items as a Function of $\delta$

In Fig. A1, we plot the mean number of items for $K_4$ and $K_4 - (3, 4)$ for the arrivals under consideration, when $\delta \in (0.03, 0.1)$.

<figure><img src="image_11.png" /><figcaption>Fig. A1: Evolution of the expected number of items over $\delta$.</figcaption></figure>

# Appendix B Proofs of Section 2.4

## B.1 Proof of Proposition 1

Using (5), we obtain from the definition of $\alpha^\delta$ that the mean number of items of the complete graph under any greedy policy is

$$ \mathbb{E}[M(K_4 - (1,2), \alpha^\delta, FCFM)] = \frac{\frac{(0.5-2\delta)(0.5+2\delta)}{(4\delta)^2} + \frac{(0.5-\delta)(0.5+\delta)}{(2\delta)^2} + \frac{3\delta(1-3\delta)}{(1-6\delta)^2}}{1 + \frac{0.5-2\delta}{4\delta} + \frac{0.5-\delta}{2\delta} + \frac{3\delta}{1-6\delta}} $$

Likewise, using (10) and the definition $\alpha^\delta$, it results

$$ \mathbb{E}[M(K_4, \alpha^\delta, FCFM)] = \frac{2\frac{(0.25-\delta)(0.75+\delta)}{(0.5+2\delta)^2} + \frac{(0.5-\delta)(0.5+\delta)}{(2\delta)^2} + \frac{3\delta(1-3\delta)}{(1-6\delta)^2}}{1 + 2\frac{0.25-\delta}{0.5+2\delta} + \frac{0.5-\delta}{2\delta} + \frac{3\delta}{1-6\delta}} $$

We now study the sign of $\mathbb{E}[M(K_4 - (1,2), \alpha^\delta, FCFM)] - \mathbb{E}[M(K_4, \alpha^\delta, FCFM)]$, which is the same as the sign of

$$ \left( \frac{(0.5 - 2\delta)(0.5 + 2\delta)}{(4\delta)^2} + \frac{(0.5 - \delta)(0.5 + \delta)}{(2\delta)^2} + \frac{3\delta(1 - 3\delta)}{(1 - 6\delta)^2} \right) $$
32 Performance Paradox of Dynamic Matching Models under Greedy Policies

Simplifying this expression using Wolfram Mathematica, we obtain the
following equivalent one:

$$
\frac{54}{\delta^3(0.25 + \delta)^2(-1 + 6\delta)^3} \times \\
\left( 4.52112 \cdot 10^{-6} - 0.0001808\delta + 0.0026222\delta^2 - 0.0180845\delta^3 \right. \\
\left. + 0.0640914\delta^4 - 0.133102\delta^5 + 0.30556\delta^6 - 0.8333\delta^7 + \delta^8 \right)
$$

We note that $-1 + 6\delta < 0$ when $0 < \delta \le 0.1$. Thus, since

$$
\frac{54}{\delta^3(0.25 + \delta)^2(-1 + 6\delta)^3}
$$

is negative when $0 < \delta \le 0.1$, the sign of $\mathbb{E}[M(K_4 - (3,4), \alpha^\delta, FCFM)] - \mathbb{E}[M(K_4, \alpha^\delta, FCFM)]$ is the opposite of the sign of the polynomial of degree 8:

$$
4.52112 \cdot 10^{-6} - 0.0001808\delta + 0.0026222\delta^2 - 0.0180845\delta^3 + 0.0640914\delta^4 \\ - 0.133102\delta^5 + 0.30556\delta^6 - 0.8333\delta^7 + \delta^8.
$$

Using Wolfram Mathematica, we know that this polynomial has one real root between 0 and 0.1, which is 0.0563. Besides, if 0 < δ ≤ 0.0563, the polynomial is positive and negative otherwise. Therefore, the desired result follows.

**Appendix C Proof of Proposition 3**

$$
\mathbb{E}[M(K_4 - (3,4), \alpha^\delta, FCFM)] - \mathbb{E}[M(K_4, \alpha^\delta, FCFM)]
$$

In Appendix B, we show that, for this matching model, we have that

$$
\mathbb{E}[M(K_4 - (3,4), \alpha^\delta, FCFM)] = \frac{\frac{(0.5-2\delta)(0.5+2\delta)}{(4\delta)^2} + \frac{(0.5-\delta)(0.5+\delta)}{(2\delta)^2} + \frac{3\delta(1-3\delta)}{(1-6\delta)^2}}{1 + \frac{0.5-2\delta}{4\delta} + \frac{0.5-\delta}{2\delta} + \frac{3\delta}{1-6\delta}}
$$

and

$$
\mathbb{E}[M(K_4, \alpha^\delta, FCFM)] = \frac{2 \frac{(0.25-\delta)(0.75+\delta)}{(0.5+2\delta)^2} + \frac{(0.5-\delta)(0.5+\delta)}{(2\delta)^2} + \frac{3\delta(1-3\delta)}{(1-6\delta)^2}}{1 + 2 \frac{0.25-\delta}{0.5+2\delta} + \frac{0.5-\delta}{2\delta} + \frac{3\delta}{1-6\delta}}.
$$

The desired result follows if we show that

$$
(a) \delta^2 \left( \frac{(0.5-2\delta)(0.5+2\delta)}{(4\delta)^2} + \frac{(0.5-\delta)(0.5+\delta)}{(2\delta)^2} + \frac{3\delta(1-3\delta)}{(1-6\delta)^2} \right) \text{tends to } 5 \cdot 0.5^6 \text{ when } \delta \to 0,
$$

$$
(b) \delta^2 \left( 2 \frac{(0.25-\delta)(0.75+\delta)}{(0.5+2\delta)^2} + \frac{(0.5-\delta)(0.5+\delta)}{(2\delta)^2} + \frac{3\delta(1-3\delta)}{(1-6\delta)^2} \right) \text{tends to } 0.5^4 \text{ when } \delta \to 0,
$$

$$
(c) \frac{1}{\delta} \left( 1 + \frac{0.5-2\delta}{4\delta} + \frac{0.5-\delta}{2\delta} + \frac{3\delta}{1-6\delta} \right)^{-1} \text{ tends to } \frac{8}{3} \text{ when } \delta \to 0,
$$
$$ \left(1 + 2\frac{0.25 - \delta}{(0.5 + 2\delta)} + \frac{0.5 - \delta}{2\delta} + \frac{3\delta}{1 - 6\delta}\right) - \left(2\frac{(0.25 - \delta)(0.75 + \delta)}{(0.5 + 2\delta)^2} + \frac{(0.5 - \delta)(0.5 + \delta)}{(2\delta)^2} + \frac{3\delta(1 - 3\delta)}{(1 - 6\delta)^2}\right) \left(1 + \frac{0.5 - 2\delta}{4\delta} + \frac{0.5 - \delta}{2\delta} + \frac{3\delta}{1 - 6\delta}\right). \quad (B1) $$

Simplifying this expression using Wolfram Mathematica, we obtain the following equivalent one:

$$ \frac{54}{\delta^3(0.25 + \delta)^2(-1 + 6\delta)^3} \times (4.52112 \cdot 10^{-6} - 0.0001808\delta + 0.0026222\delta^2 - 0.0180845\delta^3 + 0.0640914\delta^4 - 0.133102\delta^5 + 0.30556\delta^6 - 0.8333\delta^7 + \delta^8). $$

We note that $-1 + 6\delta < 0$ when $0 < \delta \le 0.1$. Thus, since

$$ \frac{54}{\delta^3(0.25 + \delta)^2(-1 + 6\delta)^3} < 0 $$

when $0 < \delta \le 0.1$, the sign of $\mathbb{E}[M(K_4 - (1,2), \alpha^\delta, FCFM)] - \mathbb{E}[M(K_4, \alpha^\delta, FCFM)]$ is the opposite of the sign of the polynomial of degree 8:

$$ 4.52112 \cdot 10^{-6} - 0.0001808\delta + 0.0026222\delta^2 - 0.0180845\delta^3 + 0.0640914\delta^4 - 0.133102\delta^5 + 0.30556\delta^6 - 0.8333\delta^7 + \delta^8. $$

Using Wolfram Mathematica, we know that this polynomial has one real root between 0 and 0.1, which is 0.0563. Besides, if $0 < \delta \le 0.0563$, the polynomial is positive and negative otherwise. Therefore, the desired result follows.

## B.2 Representation of the expected number of items as a function of $\delta$

In Fig. B2, we plot the mean number of items for $K_4$ and $K_4 - (1,2)$ for the arrivals under consideration, when $\delta \in (0.03, 0.1)$.

## B.3 Proof of Proposition 2

In Appendix B.1, we show that, for this matching model, we have that

$$ \mathbb{E}[M(K_4 - (1,2), \alpha^\delta, FCFM)] = \frac{\frac{(0.5-2\delta)(0.5+2\delta)}{(4\delta)^2} + \frac{(0.5-\delta)(0.5+\delta)}{(2\delta)^2} + \frac{3\delta(1-3\delta)}{(1-6\delta)^2}}{1 + \frac{0.5-2\delta}{4\delta} + \frac{0.5-\delta}{2\delta} + \frac{3\delta}{1-6\delta}} $$
$$
\begin{array}{l}
(d) \frac{1}{\delta} \left( 1 + 2^{\frac{0.25-\delta}{0.5+2\delta}} + \frac{0.5-\delta}{2\delta} + \frac{3\delta}{1-6\delta} \right)^{-1} \text{ tends to } 4 \text{ when } \delta \to 0, \\
\text{since when } \delta \to 0,
\end{array}
$$

$$
\delta \left( \mathbb{E}[M(K_4 - (3,4), \alpha^\delta, FCFM)] - \mathbb{E}[M(K_4, \alpha^\delta, FCFM)] \right) \to 0.5^4 \cdot 4 - 5 \cdot 0.5^6 \cdot \frac{8}{3} = \frac{1}{24}.
$$

We first show (a).

$$
\begin{aligned}
& \delta^2 \left( \frac{(0.5 - 2\delta)(0.5 + 2\delta)}{(4\delta)^2} + \frac{(0.5 - \delta)(0.5 + \delta)}{(2\delta)^2} + \frac{3\delta(1 - 3\delta)}{(1 - 6\delta)^2} \right) \\
& = \frac{(0.5 - \delta)(0.5 + 2\delta)}{16} + \frac{(0.5 - \delta)(0.5 + \delta)}{4} + \frac{3\delta^3(1 - 3\delta)}{(1 - 6\delta)^2},
\end{aligned}
$$

and the first and second terms tend, respectively, to 0.5⁶ and 0.5⁴ = 4 · 0.5⁶
when $\delta \to 0$, whereas the third one tends to zero.
We now show (b).

$$
\begin{aligned}
& \delta^2 \left( 2 \frac{(0.25 - \delta)(0.75 + \delta)}{(0.5 + 2\delta)^2} + \frac{(0.5 - \delta)(0.5 + \delta)}{(2\delta)^2} + \frac{3\delta(1 - 3\delta)}{(1 - 6\delta)^2} \right) \\
& = 2\delta^2 \frac{(0.25 - \delta)(0.75 + \delta)}{(0.5 + 2\delta)^2} + \frac{(0.5 - \delta)(0.5 + \delta)}{4} + \frac{3\delta^3(1 - 3\delta)}{(1 - 6\delta)^2},
\end{aligned}
$$

and the first and third terms tend to zero when $\delta \to 0$, whereas the second one tends to 0.5$^4$.
We also show (c).

$$
\frac{1}{\delta} \left( 1 + \frac{0.5 - 2\delta}{4\delta} + \frac{(0.5 - \delta)}{2\delta} + \frac{3\delta}{1 - 6\delta} \right)^{-1} = \left( \delta + \frac{(0.5 - 2\delta)}{4} + \frac{(0.5 - \delta)}{2} + \frac{3\delta^2}{1 - 6\delta} \right)^{-1},
$$

and when $\delta \to 0$, the last expression tends to $(\frac{1}{8} + \frac{1}{4})^{-1}$, which equals $\frac{8}{3}$.
Finally, we show (d).

$$
\frac{1}{\delta} \left( 1 + 2 \frac{(0.25 - \delta)}{0.5 + 2\delta} + \frac{(0.5 - \delta)}{2\delta} + \frac{3\delta}{1 - 6\delta} \right)^{-1} = \left( \delta + 2\delta \frac{(0.25 - \delta)}{(0.5 + 2\delta)} + \frac{(0.5 - \delta)}{2} + \frac{3\delta^2}{1 - 6\delta} \right)^{-1},
$$

where all the terms tend to zero when $\delta \to 0$, except for $\frac{0.5-\delta}{2}$, which tends to
0.25.
<figure><img src="image_12.png" /><figcaption>Fig. B2: Evolution of the expected number of items over $\delta$.</figcaption></figure>

and

$$ \mathbb{E}[M(K_4, \alpha^{\delta}, FCFM)] = \frac{2 \frac{(0.25-\delta)(0.75+\delta)}{(0.5+2\delta)^2} + \frac{(0.5-\delta)(0.5+\delta)}{(2\delta)^2} + \frac{3\delta(1-3\delta)}{(1-6\delta)^2}}{1 + 2 \frac{0.25-\delta}{0.5+2\delta} + \frac{0.5-\delta}{2\delta} + \frac{3\delta}{1-6\delta}} $$

The desired result follows if we show that

(a) $\delta^2 \left( \frac{(0.5-2\delta)(0.5+2\delta)}{(4\delta)^2} + \frac{(0.5-\delta)(0.5+\delta)}{(2\delta)^2} + \frac{3\delta(1-3\delta)}{(1-6\delta)^2} \right)$ tends to $5 \cdot 0.5^6$ when $\delta \to 0$,

(b) $\delta^2 \left( 2 \frac{(0.25-\delta)(0.75+\delta)}{(0.5+2\delta)^2} + \frac{(0.5-\delta)(0.5+\delta)}{(2\delta)^2} + \frac{3\delta(1-3\delta)}{(1-6\delta)^2} \right)$ tends to $0.5^4$ when $\delta \to 0$,

(c) $\frac{1}{\delta} \left( 1 + \frac{0.5-2\delta}{4\delta} + \frac{0.5-\delta}{2\delta} + \frac{3\delta}{1-6\delta} \right)^{-1}$ tends to $\frac{8}{3}$ when $\delta \to 0$,

(d) $\frac{1}{\delta} \left( 1 + 2 \frac{0.25-\delta}{0.5+2\delta} + \frac{0.5-\delta}{2\delta} + \frac{3\delta}{1-6\delta} \right)^{-1}$ tends to 4 when $\delta \to 0$,

since when $\delta \to 0$,

$$ \delta \left( \mathbb{E}[M(K_4 - (1,2), \alpha^{\delta}, FCFM)] - \mathbb{E}[M(K_4, \alpha^{\delta}, FCFM)] \right) \to 0.5^4 \cdot 4 - 5 \cdot 0.5^6 \cdot \frac{8}{3} = \frac{1}{24}. $$

We first show (a).

$$ \delta^2 \left( \frac{(0.5 - 2\delta)(0.5 + 2\delta)}{(4\delta)^2} + \frac{(0.5 - \delta)(0.5 + \delta)}{(2\delta)^2} + \frac{3\delta(1 - 3\delta)}{(1 - 6\delta)^2} \right) = \frac{(0.5 - \delta)(0.5 + 2\delta)}{16} + \frac{(0.5 - \delta)(0.5 + \delta)}{4} + \frac{3\delta^3(1 - 3\delta)}{(1 - 6\delta)^2}, $$

and the first and second terms tend, respectively, to $0.5^6$ and $0.5^4 = 4 \cdot 0.5^6$ when $\delta \to 0$, whereas the third one tends to zero.
References

[1] Cadas, A., Doncel, J., Fourneau, J.-M., Busic, A.: Flexibility can hurt dynamic matching system performance. ACM SIGMETRICS Performance Evaluation Review **49**(3), 37–42 (2022)

[2] Braess, D.: Über ein paradoxon aus der verkehrsplanung. Unternehmensforschung **12**(1), 258–268 (1968)

[3] Bean, N.G., Kelly, F.P., Taylor, P.G.: Braess’s paradox in a loss network. Journal of Applied Probability **34**(1), 155–159 (1997)

[4] Calvert, B., Solomon, W., Ziedins, I.: Braess’s paradox in a queueing network with state-dependent routing. Journal of Applied Probability **34**(1), 134–154 (1997). https://doi.org/10.2307/3215182

[5] Cohen, J.E., Jeffries, C.: Congestion resulting from increased capacity in single-server queueing networks. IEEE/ACM transactions on networking **5**(2), 305–310 (1997)

[6] Cohen, J.E., Kelly, F.P.: A paradox of congestion in a queuing network. Journal of Applied Probability **27**(3), 730–734 (1990)

[7] Kameda, H.: How harmful the paradox can be in the Braess/Cohen-Kelly-Jeffries networks. In: Proceedings. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 1, pp. 437–445 (2002). IEEE

[8] Busic, A., Meyn, S.: Approximate optimality with bounded regret in dynamic matching models. SIGMETRICS Perform. Eval. Rev. **43**(2), 75–77 (2015). ArXiv preprint: http://arxiv.org/abs/1411.1044

[9] Cadas, A., Busic, A., Doncel, J.: Optimal control of dynamic bipartite matching models. In: Proceedings of the 12th EAI International Conference on Performance Evaluation Methodologies and Tools. VAL-UETOOLS 2019, pp. 39–46. Association for Computing Machinery, New York, NY, USA (2019). https://doi.org/10.1145/3306309.3306317

[10] Mairesse, J., Moyal, P.: Stability of the stochastic matching model. Journal of Applied Probability **53**(4), 1064–1077 (2016). https://doi.org/10.1017/jpr.2016.65

[11] Moyal, P., Bušić, A., Mairesse, J.: A product form for the general stochastic matching model. Journal of Applied Probability **58**(3), 449–468 (2021)
34 Performance Paradox of Dynamic Matching Models under Greedy Policies

We now show (b).

$$
\begin{aligned}
& \delta^2 \left( 2 \frac{(0.25 - \delta)(0.75 + \delta)}{(0.5 + 2\delta)^2} + \frac{(0.5 - \delta)(0.5 + \delta)}{(2\delta)^2} + \frac{3\delta(1 - 3\delta)}{(1 - 6\delta)^2} \right) \\
& = 2\delta^2 \frac{(0.25 - \delta)(0.75 + \delta)}{(0.5 + 2\delta)^2} + \frac{(0.5 - \delta)(0.5 + \delta)}{4} + \frac{3\delta^3(1 - 3\delta)}{(1 - 6\delta)^2},
\end{aligned}
$$

and the first and third terms tend to zero when $\delta \to 0$, whereas the second one tends to $0.5^4$.

We also show (c).

$$
\frac{1}{\delta} \left( 1 + \frac{0.5 - 2\delta}{4\delta} + \frac{(0.5 - \delta)}{2\delta} + \frac{3\delta}{1 - 6\delta} \right)^{-1} = \left( \delta + \frac{(0.5 - 2\delta)}{4} + \frac{(0.5 - \delta)}{2} + \frac{3\delta^2}{1 - 6\delta} \right)^{-1},
$$

and when $\delta \to 0$, the last expression tends to $(\frac{1}{8} + \frac{1}{4})^{-1}$, which equals $\frac{8}{3}$.
Finally, we show (d).

$$
\frac{1}{\delta} \left( 1 + 2 \frac{(0.25 - \delta)}{0.5 + 2\delta} + \frac{(0.5 - \delta)}{2\delta} + \frac{3\delta}{1 - 6\delta} \right)^{-1} = \left( \delta + 2\delta \frac{(0.25 - \delta)}{0.5 + 2\delta} + \frac{(0.5 - \delta)}{2} + \frac{3\delta^2}{1 - 6\delta} \right)^{-1},
$$

where all the terms tend to zero when $\delta \to 0$, except for $\frac{0.5-\delta}{2}$, which tends to 0.25.

**Appendix C Proofs of Section 4**

C.1 Proof of Proposition 7

We have to prove that the blocks $L_2$, $C_2$ and $P_2$ are the same as in block
decomposition of matrix $M$ and give the value of $c_2$.

* From state (1, ∅) all the arrivals match letter $s_1$ and the transitions leads to (0, ∅). Thus due to the uniformization rate, this transition has probability 1/2 and there is a loop on state (1, ∅) with probability 1/2.

* The transition from (0, ∅) leads to (1, ∅) for an arrival of letter $s_1$ (i.e. with a probability equal to $\frac{\|\lambda\|_1}{\Lambda}$). Therefore $c_2 = \frac{\|\lambda\|_1}{\Lambda}$ and there is a loop with probability 1/2 on this state.

* The transition from (0, ∅) to a state in $S_2$ for an arrival of a letter of $G_2$ (i.e. block $L_2$). This is the same transition probability as in Matrix $M$ as it is based on the same arrival rates, the same uniformization rate and the same discipline.
[12] Comte, C.: Stochastic non-bipartite matching models and order-independent loss queues. Stochastic Models **38**(1), 1–36 (2022). https://doi.org/10.1080/15326349.2021.1962352

[13] Begeot, J., Marcovici, I., Moyal, P., Rahme, Y.: A general stochastic matching model on multigraphs. ALEA Lat. Am. J. Probab. Math. Stat., 1325–1351 (2021)

[14] Kaplan, E.H.: Managing the demand for public housing. PhD thesis, Massachusetts Institute of Technology (1984)

[15] Caldentey, R., Kaplan, E.H., Weiss, G.: FCFS infinite bipartite matching of servers and customers. Advances in Applied Probability **41**(3), 695–730 (2009)

[16] Adan, I., Weiss, G.: Exact FCFS matching rates for two infinite multitype sequences. Operations Research **60**(2), 475–489 (2012). https://doi.org/10.1287/opre.1110.1027

[17] Bušić, A., Gupta, V., Mairesse, J.: Stability of the bipartite matching model. Advances in Applied Probability **45**(2), 351–378 (2013)

[18] Weiss, G.: Directed FCFS infinite bipartite matching. Queueing Syst. Theory Appl. **96**(3-4), 387–418 (2020). https://doi.org/10.1007/s11134-020-09676-6

[19] Gardner, K., Zbarsky, S., Doroudi, S., Harchol-Balter, M., Hyytiä, E., Scheller-Wolf, A.: Queueing with redundant requests: exact analysis. Queueing Systems **83**(3-4), 227–259 (2016)

[20] Adan, I., Kleiner, I., Righter, R., Weiss, G.: FCFS parallel service systems and matching models. Performance Evaluation **127-128**, 253–272 (2018). https://doi.org/10.1016/j.peva.2018.10.005

[21] Plateau, B., Stewart, W.J.: Stochastic automata networks. Computational Probability, 113–151 (2000)

[22] Kemeny, J.G., Snell, J.L.: Finite Markov Chains. Van Nostrand, New York (1960)

[23] Rubino, G., Sericola, B.: Markov Chains and Dependability Theory. Cambridge University Press, Cambridge (2014)

[24] Busic, A., Cadas, A., Doncel, J., Fourneau, J.-M.: Product form solution for the steady-state distribution of a markov chain associated with a general matching model with self-loops. In: Computer Performance Engineering: 18th European Workshop, EPEW 2022, Santa Pola, Spain,
• The transition from a state in $S_2$ to state $(0, \emptyset)$ for an arrival of a letter of $G_1$ or $G_2$ (i.e. block $C_2$). All letters of $G_1$ has the same effect as item $s_1$ due to a consistent discipline and all letters of $G_2$ have the same effect in $M$ and in $M_2$. The uniformization rate is the same in both models. Therefore both matrices have the same block $C_2$ to model these transitions.

## C.2 Proof of Theorem 3

The proof is based on some decomposition and matrix formulation for discrete time Markov chains and censored Markov chains (see [27] for censored Markov chains). First we write the global balance equation for $M$ at the block level:

$$ \pi_0^M = \pi_0^M/2 + \pi_{S_1}^M C_1 + \pi_{S_2}^M C_2, \quad (C2) $$

and

$$ \pi_{S_1}^M = \pi_0^M L_1 + \pi_{S_1}^M P_1, \quad (C3) $$

and finally

$$ \pi_{S_2}^M = \pi_0^M L_2 + \pi_{S_2}^M P_2. \quad (C4) $$

We do the same for $M_1$:

$$ \pi_1^{M_1} = \pi_0^{M_1} c_1 + \pi_1^{M_1}/2, \quad (C5) $$

$$ \pi_0^{M_1} = \pi_1^{M_1}/2 + \pi_0^{M_1}/2 + \pi_{S_1}^{M_1} C_1, \quad (C6) $$

and finally,

$$ \pi_{S_1}^{M_1} = \pi_0^{M_1} L_1 + \pi_{S_1}^{M_1} P_1 \quad (C7) $$

One can considered the censored Markov chain extracted from $M_1$ with censored set $\{s_2\}$. According to Lemma 6.6 in [27], $\sum_{i=0}^{\infty} P_1^i$ converges and we obtain:

$$ \pi_{S_1}^{M_1} = \pi_0^{M_1} L_1 \sum_{i=0}^{\infty} P_1^i, \quad (C8) $$

and as $\pi_0^{M_1}$ is a scalar, we get:

$$ \frac{\pi_{S_1}^{M_1}}{\pi_0^{M_1}} = L_1 \sum_{i=0}^{\infty} P_1^i. \quad (C9) $$

With the same argument, Eq. C3 gives:

$$ \frac{\pi_{S_1}^M}{\pi_0^M} = L_1 \sum_{i=0}^{\infty} P_1^i. \quad (C10) $$

Taking into account Eq. C9 and Eq. C10 we obtain after substitution:

$$ \pi_{S_1}^M = \frac{\pi_0^M}{\pi_{S_1}^{M_1}} \pi_{S_1}^{M_1}. $$
With a similar approach we have for matrix $P_2$:

$$ \frac{\pi_{S_2}^{M_2}}{\pi_0^{M_2}} = L_2 \sum_{i=0}^{\infty} P_2^i, \qquad (C11) $$

and

$$ \pi_{S_2}^{M} = \frac{\pi_{0}^{M}}{\pi_{0}^{M_2}} \pi_{S_2}^{M_2}. $$

The first two results of the theorem are now established. For the computation of $\pi_0^M$ it is not possible to use Eq. C2 because it is not independent. Therefore we use normalization.

$$ \pi_0^M + \|\pi_{S_1}^M\|_1 + \|\pi_{S_2}^M\|_1 = 1. $$

After substitution:

$$ \pi_0^M \left( 1 + \frac{1}{\pi_0^{M_1}} \|\pi_{S_1}^M\|_1 + \frac{1}{\pi_0^{M_2}} \|\pi_{S_2}^M\|_1 \right) = 1. $$

Clearly, $\|\pi_{S_1}^M\|_1 = 1 - \pi_0^{M_1} - \pi_1^{M_1}$ and $\|\pi_{S_2}^M\|_1 = 1 - \pi_0^{M_2} - \pi_1^{M_2}$. Thus

$$ \pi_0^M = \left( 1 + \frac{1 - \pi_0^{M_1}(1 + 2c_1)}{\pi_0^{M_1}} + \frac{1 - \pi_0^{M_2}(1 + 2c_2)}{\pi_0^{M_2}} \right)^{-1}. $$

After simple algebraic manipulation, taking into account that $2(c_1 + c_2) = 1$, we finally obtain the relation for $\pi_0^M$.

Let us now consider the expectation of the number of letters. The discipline D is based on discipline $D_1$ for $G_1$ and $D_2$ for $G_2$ as explained in Section 4. Let $\pi(m_1, m_2)$ be the steady-state probability of state $(m_1, m_2)$. We decompose the summation on the state space:

$$ \mathbb{E}[M(G_1 \bowtie G_2), (\lambda, \mu), D)] = \sum_{x \in S_1} |x| \pi^M(x, \emptyset) + \sum_{y \in S_2} |y| \pi^M(\emptyset, y). $$

And

$$ \mathbb{E}[M(G'_1, \lambda, D_1)] = \sum_{x \in S_1} |x| \pi^{M_1}(x, \emptyset) + \pi_1^{M_1}, $$

with a similar relation for $\mathbb{E}[M(G'_2, \mu, D_2)]$. After substitution and factorization, we get:

$$ \mathbb{E}[M(G_1 \bowtie G_2), (\lambda, \mu), D)] = \frac{\pi_0^M}{\pi_0^{M_1}} \sum_{x \in S_1} |x| \pi^{M_1}(x, \emptyset) + \frac{\pi_0^M}{\pi_0^{M_2}} \sum_{y \in S_2} |y| \pi^{M_2}(\emptyset, y). $$

As $\pi_1^{M_1} = 2c_1\pi_0^{M_1}$, $\pi_1^{M_2} = 2c_2\pi_0^{M_2}$ and $2(c_1 + c_2) = 1$, we get the results after simple algebraic manipulations.
References

[1] Braess, D.: Über ein paradoxon aus der verkehrsplanung. Unternehmensforschung **12**(1), 258–268 (1968)

[2] Bean, N.G., Kelly, F.P., Taylor, P.G.: Braess's paradox in a loss network. Journal of Applied Probability **34**(1), 155–159 (1997)

[3] Calvert, B., Solomon, W., Ziedins, I.: Braess's paradox in a queueing network with state-dependent routing. Journal of Applied Probability **34**(1), 134–154 (1997). https://doi.org/10.2307/3215182

[4] Cohen, J.E., Jeffries, C.: Congestion resulting from increased capacity in single-server queueing networks. IEEE/ACM transactions on networking **5**(2), 305–310 (1997)

[5] Cohen, J.E., Kelly, F.P.: A paradox of congestion in a queuing network. Journal of Applied Probability **27**(3), 730–734 (1990)

[6] Kameda, H.: How harmful the paradox can be in the Braess/Cohen-Kelly-Jeffries networks. In: Proceedings. Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, vol. 1, pp. 437–445 (2002). IEEE

[7] Cadas, A., Doncel, J., Fourneau, J.-M., Busic, A.: Flexibility can hurt dynamic matching system performance. ACM SIGMETRICS Performance Evaluation Review **49**(3), 37–42 (2022)

[8] Busic, A., Meyn, S.: Approximate optimality with bounded regret in dynamic matching models. SIGMETRICS Perform. Eval. Rev. **43**(2), 75–77 (2015). ArXiv preprint: http://arxiv.org/abs/1411.1044

[9] Cadas, A., Busic, A., Doncel, J.: Optimal control of dynamic bipartite matching models. In: Proceedings of the 12th EAI International Conference on Performance Evaluation Methodologies and Tools. VAL-UETOOLS 2019, pp. 39–46. Association for Computing Machinery, New York, NY, USA (2019). https://doi.org/10.1145/3306309.3306317

[10] Mairesse, J., Moyal, P.: Stability of the stochastic matching model. Journal of Applied Probability **53**(4), 1064–1077 (2016). https://doi.org/10.1017/jpr.2016.65

[11] Moyal, P., Bušić, A., Mairesse, J.: A product form for the general stochastic matching model. Journal of Applied Probability **58**(3), 449–468 (2021)
[12] Comte, C.: Stochastic non-bipartite matching models and order-independent loss queues. Stochastic Models **38**(1), 1–36 (2022). https://doi.org/10.1080/15326349.2021.1962352

[13] Begeot, J., Marcovici, I., Moyal, P., Rahme, Y.: A general stochastic matching model on multigraphs. ALEA Lat. Am. J. Probab. Math. Stat., 1325–1351 (2021)

[14] Kaplan, E.H.: Managing the demand for public housing. PhD thesis, Massachusetts Institute of Technology (1984)

[15] Caldentey, R., Kaplan, E.H., Weiss, G.: FCFS infinite bipartite matching of servers and customers. Advances in Applied Probability **41**(3), 695–730 (2009)

[16] Bušić, A., Gupta, V., Mairesse, J.: Stability of the bipartite matching model. Advances in Applied Probability **45**(2), 351–378 (2013)

[17] Gardner, K., Righter, R.: Product forms for fcfs queueing models with arbitrary server-job compatibilities: an overview. Queueing Systems **96**(1-2), 3–51 (2020)

[18] Weiss, G.: Directed FCFS infinite bipartite matching. Queueing Syst. Theory Appl. **96**(3-4), 387–418 (2020). https://doi.org/10.1007/s11134-020-09676-6

[19] Adan, I., Weiss, G.: Exact FCFS matching rates for two infinite multitype sequences. Operations Research **60**(2), 475–489 (2012). https://doi.org/10.1287/opre.1110.1027

[20] Adan, I., Kleiner, I., Righter, R., Weiss, G.: FCFS parallel service systems and matching models. Performance Evaluation **127-128**, 253–272 (2018). https://doi.org/10.1016/j.peva.2018.10.005

[21] Gardner, K., Zbarsky, S., Doroudi, S., Harchol-Balter, M., Hyytiä, E., Scheller-Wolf, A.: Queueing with redundant requests: exact analysis. Queueing Systems **83**(3-4), 227–259 (2016)

[22] Gardner, K., Harchol-Balter, M., Hyytiä, E., Righter, R.: Scheduling for efficiency and fairness in systems with redundancy. Performance Evaluation **116**, 1–25 (2017). https://doi.org/10.1016/j.peva.2017.07.001

[23] Kemeny, J.G., Snell, J.L.: Finite Markov Chains. Van Nostrand, New York (1960)

[24] Rubino, G., Sericola, B.: Markov Chains and Dependability Theory. Cambridge University Press, Cambridge (2014)
[25] Plateau, B., Stewart, W.J.: Stochastic automata networks. Computational Probability, 113–151 (2000)

[26] Busic, A., Cadas, A., Doncel, J., Fourneau, J.-M.: Product form solution for the steady-state distribution of a markov chain associated with a general matching model with self-loops. In: Computer Performance Engineering: 18th European Workshop, EPEW 2022, Santa Pola, Spain, September 21–23, 2022, Proceedings, pp. 71–85 (2023). Springer

[27] Kemeny, J.G., Snell, J.L., Knapp, A.W.: Denumerable Markov Chains. Springer, New York (1969)