Keywords: maximal complete 3-partite subgraph Ǧ BM Bipartite Matching graph, CFTP Coupling From The Past, CTMC Continuous-Time Markov Chain, DTMC Discrete-Time Markov Chain

Motivated by a wide range of assemble-to-order systems and systems of the collaborative economy applications, we introduce a stochastic matching model on hypergraphs and multigraphs, extending the model introduced by Mairesse and Moyal 2016.

In this thesis, the stochastic matching model (S, Φ, µ) on general graph structures are defined as follows: given a compatibility general graph structure S = (V, S) which of a set of nodes denoted by V that represent the classes of items and by a set of edges denoted by S that allows matching between different classes of items. Items arrive at the system at a random time, by a sequence (assumed to be i.i.d.) that consists of different classes of V, and request to be matched due to their compatibility according to S. The compatibility by groups of two or more (hypergraphical cases) and by groups of two with possibilities of matching between the items of the same classes (multigraphical cases). The unmatched items are stored in the system and wait for a future compatible item and as soon as they are matched they leave it together. Upon arrival, an item may find several possible matches, the items that leave the system depend on a matching policy Φ to be specified.

We study the stability of the stochastic matching model on hypergraphs, for different hypergraphical topologies. Then, the stability of the stochastic matching model on multigraphs using the maximal subgraph and minimal blow-up to distinguish the zone of stability. v Résumé Motivé par des applications à large éventail des systèmes d'assemblage à la commande et des systèmes de l'économie collaborative, nous introduisons un modèle d'appariement aléatoire sur les hypergraphes et sur les multigraphes, étendant le modèle par Mairesse et Moyal 2016. Dans cette thèse, le modèle d'appariement aléatoire (S, Φ, µ) sur les structures graphiques générales est défini comme suit: étant donné une structure graphique générale de compatibilité S = (V, S) qui est constituée d'un ensemble de noeuds noté par V qui représentent les classes d'éléments et par un ensemble d'arêtes noté par S qui permettent d'apparier entre les différentes classes. Les éléments arrivent au système à un moment aléatoire, par une séquence (supposée être i.i.d.) constituée de différentes classes de V, et demandent d'être appariés selon leur compatibilité dans S. La compatibilité par groupe de deux ou plus (cas hypergraphique) et par groupe de deux avec les possibilités d'apparier entre les éléments de même classe (cas multigraphique). Les éléments, qui ne sont pas appariés, sont stockés dans le système et en attente d'un futur élément compatible et dès qu'ils sont appariés, ils quittent le système ensemble. À l'arrivée, un élément peut trouver plusieurs d'appariements possibles, les éléments qui quittent le système dépendent d'une politique d'appariement Φ à spécifier. Nous étudions la stabilité du modèle d'appariement aléatoire sur l'hypergraphe, pour des différentes topologies hypergraphiques puis, la stabilité du modèle d'appariement aléatoire sur les multigraphes en utilisant son sous-graphe maximal et sur-graphe minimal étendu pour distinguer la zone de stabilité. vii 1 4 . . . 5.1

Acknowledgment

My thesis is a result of a challenging journey to which many people have contributed and given their support. It is a pleasant task to express my thanks to all those people who made this thesis possible and unforgettable yet a life-changing experience for me.

First of all, I would like to express my gratitude to the French government for its generosity also for granting me the honor to study at the Compiègne University of Technologie (UTC) which is a founding member of Sorbonne University association, and one of the best Universities in France. Moreover, I would also like to thank the Lebanese government and the general directorate of the Lebanese internal security forces to support me seeking my goal and completing my Ph.D. I would like to sincerely thank the Laboratory of Applied Mathematics of Compiègne for allowing me to complete my thesis under the best conditions, also, I am grateful for the funding received through 'national research agency' ANR to support me.

My deep appreciation goes out to my director, Professor Pascal MOYAL who honored me by agreeing to guide and advise me throughout this work, for he has been a constant source of inspiration and the guide light for all my Endeavours. His expertise was invaluable, I appreciate his kindness, availability to listen and all the confidence he has instilled in me, thank you for everything you have done to help me reach where I am now. I equally address a greater thanks to Professor Zaher KHRAIBANI who accompanied and supported me throughout this thesis, I am deeply indebted and sincerely grateful to you for your never-failing guidance and encouragement.

I have always been blessed with magnificent friends in my life who kept me going by providing a stimulating and fun-filled environment. Words are short to express my gratitude towards my following friends, Hani EL HAJJAR for hosting me at his house and making me feel so welcomed, my colleagues at university Josephine MERHI BLEIK, Joanna AKROUCHE, and Samer TAOUM who helped me all in numerous ways during my stay in France, my colleagues at work in Lebanon who always provided me with moral support whenever the need arises required, either directly or indirectly.

The biggest support, motivation, and encouragement a man can receive is form his pari ents. My father has always given me the courage to dream and try to fulfill challenging dreams and my mother has always taught me the importance of being patient and humble in all stages of life. The expression "thank you" does not seem sufficient but it is said with appreciation and respect to my parents, Mr. Elias and Mrs. Mona for their unwavering support, care, love, motivation, understanding, and prayers. I would not have reached this stage in my life without your blessings and assistance. I would also like to extend a huge loving thanks to my brother Gabriel and my sister Galia who always had faith in my abilities and were always by my side.

The best outcome of these past years was finding my soul-mate, life partner, and lovely wife. I married the best girl out there for me! I feel fortunate to have her by my side and there are no words to convey how much I love her. I truly thank my wife Mrs. Saide BAHJA for giving me strength and patience in my hard times. I could not have completed this without having you and our little girl Tatiana by my side whom I will seek to make her proud.

Thank you all for making it possible for me to complete what I started, for making this dream come true, it has been three years already and I have learned many things and created great memories that will stay with me forever. Matching models have recently received a growing interest in the literature of queueing models in which compatibilities between the requests need to be taken into account. This is a natural enrichment of service systems in which the requests must be matched, or put in relation, rather than being served. Among other fields of applications, this is a natural representation of peer-to-peer networks, interfaces of the collaborative economy (such as car and ride-sharing, dating websites, and so on), assemble-to-order systems, job search applications, and healthcare systems (blood banks and organ transplant networks). All of these applications share the same common ground: elements/items/agents enter a system that is just an interface to put them in relation, and relations are possible only if the "properties"

List of Figures

(whatever this means) of the elements make them compatible.

In [START_REF] Caldentey | FCFS infinite bipartite matching of servers and customers[END_REF] (see also [1]), a variant of such skill-based systems was introduced, which are now commonly referred to as Bipartite Matching models (BM): couples customer/server enter the system at each time point, and customers and servers play symmetrical roles: exactly like customers, servers come and go into the system. Upon arrival, they wait for a compatible customer, and as soon as they find one, leave the system together with it. Otherwise, items remain in the system waiting for compatible arrivals (in particular, there are no service times). These settings are suitable to various fields of applications, among which, blood banks, organ transplants, housing allocation, job search, dating websites, and so on.

In both references, compatible customers and servers are matched according to the FCFS 'First Come, First Served' service discipline.

In [START_REF] Adan | Reversibility and further properties of the FCFM Bipartite matching model[END_REF], a subtle dynamic reversibility property is shown, entailing that the stationary state of such systems under FCFS, can be obtained in a product form. Moreover, a sub-additivity property is proved, allowing (under stability conditions) the construction of a unique stationary bi-infinite matching of the customers and servers, by a coupling-from-the-past (CFTP) 1 technique. Interestingly, the product form of the stationary state can then be adapted to various skill-based queueing models as well, and in particular, those applying (various declinations of) the so-called FCFS-ALIS (Assign the Longest Idling Server) service discipline -see e.g. [START_REF] Adan | A skill based parallel service system under FCFS-ALIS -steady state, overloads, and abandonments[END_REF], and various extensions of BM models in [START_REF] Adan | FCFS parallel service systems and matching models[END_REF][START_REF] Buke | Stabilizing Policies for Probabilistic Matching Systems[END_REF][START_REF] Buke | Fluid and diffusion approximations of probabilistic matching systems[END_REF].

In [START_REF] Bušić | Stability of the bipartite matching model[END_REF], the settings of [START_REF] Caldentey | FCFS infinite bipartite matching of servers and customers[END_REF]1] are generalized to more general service disciplines (termed 'matching policies' in this context), and necessary and sufficient conditions for the stability of the system are introduced. Moreover, the results in [START_REF] Bušić | Stability of the bipartite matching model[END_REF] do not assume the independence between the types of the entering customer and the entering server. The system is then called Extended Bipartite Matching model (EBM, for short), and suits applications in which independence between the classes of the customers and servers entering simultaneously cannot be assumed.

In [START_REF] Moyal | Loynes construction for the Extended bipartite matching[END_REF], a CFTP result is obtained, showing the existence of a unique bi-infinite matching in various cases for EBM models, and for a broader class of matching policies than FCFS, thereby generalizing the results of [START_REF] Adan | Reversibility and further properties of the FCFM Bipartite matching model[END_REF].

Problem statement

To model concrete systems, the need then arose to extend these different models. Indeed, in many applications, the assumption of pairwise arrivals may appear somewhat artificial, and it is more realistic to assume that arrivals are simple. Also, all the aforementioned references assume that the compatibility graph is bipartite, namely, there are easily identifiable classes of servers and classes of customers. For instance, in dating websites, it is a priori not possible to split items into two sets of classes (customers and servers) with no possible matches within those sets. In particular, if one considers blood types as a primary compatibility criterion, the compatibility graph between couples is naturally non-bipartite.

Motivated by these observations, a variant model was introduced in [START_REF] Mairesse | Stability of the stochastc matching model[END_REF], in which items arrive one by one and the compatibility graph in general, i.e., not necessarily bipartite: specifically, in this so-called General Matching model (GM for short), items enter one by one in discrete-time in a buffer, and belong to determinate classes in a finite set V. Upon each arrival, the class of the incoming item is drawn independently of everything else, from a distribution µ having full support V. A connected graph G whose set of nodes is precise V determines the compatibility among classes. Then, an incoming item is either immediately matched, if there is a compatible item in the line, or else stored in a buffer. It is the role of the matching policy Φ to determine the match of the incoming item in case of a multiple choice. Then, the two matched items immediately leave the system forever.

The stability region of the model, given G and Φ, is then defined as the set of measures µ such that the model is positive recurrent. A necessary condition for the stability NCOND of GM models are provided in [START_REF] Mairesse | Stability of the stochastc matching model[END_REF]. Also, is proven that the matching policy 'Match the Longest' has a maximal stability region, that is, the latter necessary condition NCOND is also sufficient (we then say that the latter policy is maximal). Further, the model with a complete p-partite (separable) graph is also stable for all matching policy Φ. However, the study of a particular model on a non-separable graph (see [START_REF] Mairesse | Stability of the stochastc matching model[END_REF], p.14) shows that NCOND is not sufficient in general for non-separable graphs. This raises the question of whether the sufficiency of NCOND is true only for separable graphs. In [START_REF] Moyal | On the instability of matching queues[END_REF] was proved that, except for a particular class of graphs, there always exists a matching policy rendering the stability region strictly smaller than the set of arrival intensities satisfying the necessary condition for stability NCOND.

Objectives and Contributions

The main purpose of this thesis is to study the long-run stability of stochastic matching models, in the sense defined above, on hypergraphical and mutligraphical compatibility matching structures, and to illustrate the potential applications of these results to concrete settings.

Hypergraphical compatibility matching structures

Two closest references to the stochastic matching model on hypergraphs are [START_REF] Gurvich | On the dynamic control of matching queues[END_REF] and [START_REF] Nazari | Optimal control of general dynamic matching systems[END_REF]: in both cases, a general matching model is addressed (in continuous time in the former, and discrete-time -allowing batches of arrivals -in the latter) on an hypergraphical matching structure (notice that [START_REF] Nazari | Optimal control of general dynamic matching systems[END_REF] also allows matchings including several items of the same class).

In [START_REF] Gurvich | On the dynamic control of matching queues[END_REF] a matching control is introduced, that asymptotically minimizes the holding cost of items in an unstable system. [START_REF] Nazari | Optimal control of general dynamic matching systems[END_REF] introduces an algorithm that is a variant of the "Primaldual algorithm", allowing to essentially optimize a given objective function provided that stability can be achieved. Then the objective function can incorporate stability (setting utility 0), in a way that stability is achieved by the essentially optimal algorithm, whenever it is achievable at all. Both references allow idling policies, i.e., scheduling algorithms allowing to perform no matching at all despite the presence of matchable items in the system, to wait for more profitable future matches. Allowing idling policy makes sense in applications such as assemble-to-order systems, advertisement, or operations scheduling, but is much less suitable to kidney transplant networks, in which case the practitioners always perform a transplant whenever one is possible. In this thesis, all the matching policies we consider are non-idling, i.e. entering items are always matched right away if this is possible at all. Thus, the model studied in the present thesis is a special case of the model studied in [START_REF] Nazari | Optimal control of general dynamic matching systems[END_REF],

for simple arrivals, no same-class matchings, and non-idling matching policies.

Our approach see [START_REF] Rahme | A stochastic matching models on hypergraphs[END_REF], is in fact, complementary to that in [START_REF] Nazari | Optimal control of general dynamic matching systems[END_REF] and [START_REF] Gurvich | On the dynamic control of matching queues[END_REF]: generalizing the approach of [START_REF] Mairesse | Stability of the stochastc matching model[END_REF] to hypergraphs instead of graphs, in this thesis we are mostly concerned with the structural properties of the underlying hypergraph of the matching model, and determine classes of hypergraph for which there does, or does not, exist non-idling policy that can stabilize the system. In a sense, the present work addresses an upstream problem to that of implementing a performant matching algorithm: we provide simple and comprehensive criteria, based only on the structural properties of the considered hypergraph for the (non)existence of a stabilizing non-idling policy.

We address the problem of the existence of a steady-state for the system: we formally define the stability region of the system as the set of measures on the set of nodes, rendering the natural Markov chain of the system positive recurrent, for a given compatibility hypergraph and a given matching policy. Also, we assess the form of the stability region of specific stochastic matching models, as a function of the geometry of the underlying hypergraphs. In a nutshell, we show that such systems are not easily stabilizable, by exhibiting wide classes of models having an empty stability region, whatever the non-idling matching policy is. Finally, we provide or give bounds for, the stability region of particular stabilizable systems.

Multigraphical compatibility matching structures

Motivated again by concrete applications, we present a further extension of the GM model. Indeed, in various contexts, among which dating websites and peer-to-peer interfaces, it is natural to assume that items of the same class can be matched together. Hence, the need to generalize the previous line of research to the case where the matching architecture is a multigraph (a graph admitting self-loops, that is, edges connecting nodes to themselves), rather than just a graph. This generalization is the core of Chapter 5 of the present thesis (see [START_REF] Begeot | A general stochastic matching model on multigraphs[END_REF]). We show how several stability results of [START_REF] Mairesse | Stability of the stochastc matching model[END_REF][START_REF] Moyal | A product form and a sub-additive theorem for the general stochastic matching model[END_REF][START_REF] Jonckheere | Generalized Max-Weight policies in stochastic matching[END_REF] can be generalized to the case of a multigraphical matching structure. As is easily seen, the buffer of a matching model on a multigraph is hybrid by essence: nodes admitting self-loops (if any) admit at most one item in the line, whereas nodes with no self-loops (if any) have unbounded queues. A matching model on a multigraph typically has a larger stability region than the corresponding model on a graph on which all self-loops are erased (the maximal subgraph of the latter -see Definition 1.13), but the interplay between self-looped nodes and their non-self-looped neighbors needs to be clearly understood: intuitively, the arrival flows to self-looped nodes appear as auxiliary flows helping their neighboring non-self-looped nodes to stabilize their queues -provided that the arrivals to self-looped nodes don't match too often with one another.

Thesis outline

This manuscript comprises two parts: the first lays prerequisites and background of the thesis while the second presents our main contributions. The hierarchy of the report is based on seven chapters as indicated in what follows.

Part I is devoted to present basic knowledge related to our subject, the basic notions, and the literature review.

Chapter 1 provides the scientific context for our work. Chapter 2 is devoted to present the dynamic of the stochastic matching model on general graph structures, matching policies, and Markov representation of the model. Chapter 3 presents the state of arts that is devoted to the related work to stochastic matching model. We end this chapter with the positioning of our work compared to others.

Part II is organized into four chapters, that consist of the contributions of this thesis and an application.

Chapter 4 provides the first contribution of this thesis, which is the study of the stochastic matching model on hypergraphs, provide necessary conditions of stability then we identify classes of hypergraphs that has an empty stability region. However, we show that stable matching models on hypergraphs exist. To show how stability can be shown in concrete examples, we provide two case studies of simple hypergraphs, that is, complete 3-uniform hypergraphs, and sub-hypergraphs of the latter where several hyperedges are erased. We finish with the discussion of the results of the chapter. Chapter 5 provides the second contribution of this thesis which is the study of the stochastic matching model on multigraph among which, the maximality and the explicit product form of the stationary probability for FCFM policy, and the maximality of Max-Weight policies. Also, we provide a few examples to illustrate our main results. We finish with the discussion of the results of the chapter.

Chapter 6 is devoted to developing the stability of particular cases for multigraph and hypergraph using the fluid limits techniques rather than the Lyapunov-Foster Theorem. Chapter 7 present an application that compare the models for organ transplantation concerned to compatibilities of blood types that illustrate the importance of studied the stability of the model for complete 3-uniform hypergraphs instead of studied the stability of the complete 3-partite graphs according to some distributions.

A general conclusion recapitulating the basic concepts and contributions of the thesis, as well as future work and perspectives, are given at last.

Part I

Background

Chapter 1

Definitions and Fundamental Concepts

In this chapter, we introduce the main definitions and fundamental concepts used in this work. First, we start with some preliminaries, we introduce the general graph structures.

Then, we present the definitions and specific properties of graph structures, hypergaph structures and multigraph structures.

In this introductory chapter, we provide an intuitive background to the material that will be used in the coming chapters.

Preliminaries

Classical notations

We adopt the usual R, Z, and N notation for the sets of real numbers, of integers and natural integers, respectively. We let R + and Z + be the non-negative real numbers and non-negative integers respectively. Also, we denote by R ++ and Z ++ (or N + ) the strictly positive real numbers and strictly positive integers, respectively. For y ∈ R, we denote by y is the integer part of y. Let A be a finite set. The cardinality of A is denoted by |A| and for any k ∈ Z ++ , A k denotes the set of k-dimensional vectors with components in A. For any i ∈ 1, q , let e i denote the vector of N q of components (e i ) j = δ ij , j ∈ 1, q . Let q ∈ N + . The null vector of N q is denoted by 0. The norm of any vector u ∈ N q is denoted by u = q i=1 u i . For any subset J ⊂ 1, k and x ∈ R k , we use the notation x J for the restriction of x to its coordinates corresponding to the indices of J.

PRELIMINARIES

Aphabet and words

An alphabet is a finite non-empty set denoted by A. A word form is writing the numerical/number as you would say it in words. We let A * denote the free monoid associated with A, i.e., the set of finite words over the alphabet A. The length of a word w ∈ A * is denoted by |w|. We write any word w ∈ A * as w = w(1)w(2)...w(|w|). As a convention, let us denote by 0 the empty word. We denote, for any a ∈ A, |w| a the number of occurrences of the letter a in the word w. Having set an ordering on A, and denoting by 1, 2, ..., |A| the elements of A in increasing order, the commutative image of a word w ∈ A is the N |A| -valued vector [w] defined by [w] = |w| 1 , ..., |w| |A| , i.e., the vector whose i-th coordinate is the number of occurrences of the letter i in the word w. The concatenation of k words w 1 , w 2 , . . . , w k of A * , that is, the word w in which appear successively from left to right, the words w 1 , w 2 , . . . , w k , is denoted by w = w 1 w 2 . . . w k . Also, for any w ∈ A * of length |w| = q, (w = w 1 w 2 • • • w q ), and any i, j, • • • , k ∈ 1, q , we denote by w [i,j,...,k] the word of length |w| -|{i, j, ..., k}| obtained from w by deleting its i-th, j-th, • • • , and k-th letters. For any integer q, the vectors of N q are denoted as x = (x(1), • • • , x(q)) , and denoted w = (w(1), . . . , w(q)). Define for any subset B of V, x(B) to be the class-content of elements of B as x(B) = i∈B x(i).

Probability

All the random variables (r.v.'s, for short) are defined on a common probability space (Ω, F, P). Given a finite set S, we denote by M (S) the set of probability measures on S having S as exact support. Denote by S the complement set of S (within a set of reference that is fixed by the context). In section 1.2 below, we present the specific properties of general graph structures.

General graph structures

We consider different types of general graph structures S defined as a couple of (V, S), where:

• The finite set V is the set of nodes (vertices) of S. We let q(S) be the cardinality of V, and the general graph structures are of order q(S).

• A finite set S := S 1 , ..., S m(S) of subsets of V such that m(S) i=1 S i = V, whose elements are called edges of S (in case of hypergraphical is called hyperedges).

Whenever no ambiguity is possible we denote the general graph structures by matching structures, and we often write q := q(S), m := m(S). The degree of a node i ∈ V is the number of edges i belongs to, i.e.,

d(i) = m(S) =1 1l S (i). If there exists a constant d such that d(i) = d for any i ∈ V, then S is said d-regular.
For any set A ⊂ V, we denote

S(A) = {S ∈ S : S ∩ A = ∅} , (1.1)
i.e., the set of edges that intersects with A. With some abuse, for any node i ∈ V, we write S(i) := S({i}).

Definition 1.1. We say that I ⊂ V is an independent set of S if I does not include any edge of S, i.e, for any S ∈ S, S ∩ Ī = ∅. We also let I(S) be the set of all independent sets of S.

An independent set is said maximal if it is not strictly included in another independent set.

Definition 1.2. A set T ⊂ V is a transversal of S if it meets all its edges, that is, T ∩ S = ∅, for any S ∈ S. The set of transversals of S is denoted by T (S). A transversal T is said minimal if it is of minimal cardinality among all transversals of S. The transversal number of the matching structures S is the cardinality of its minimal transversals. It is denoted τ (S).

Different kinds of matching structures such as a graph, hypergraph and multigraph in which each of them has specific properties (see Figure 1.1).

Graphs

In this section, we consider that S be a graph under the form G = (V, E). For easy reference, let us introduce the basics that will be used in this thesis. A (simple) graph G is defined as a couple (V, E). Two vertices u, v ∈ V are said to be adjacent, if there is an edge between u and v. We write u-v (or v-u) for {u, v} ∈ E and u -v (or v -u) else. The neighborhood of a vertex v is the subgraph of G induced by all vertices adjacent to v.

As the equation (1.1), and specifically for any graph G = (V, E) and any U ⊂ V, we denote E(U ) := {v ∈ V : ∃u ∈ U, u-v} , the neighborhood of U , and for u ∈ V, we write for short E(u) = E({u}). The degree of a vertex is the number of edges connecting it. A walks is a way of getting from one vertex to another, and consists of a sequence of edges, one following after another. A walk in which no vertex appears more than once is called a path. A cycle is a non-empty trail in which the only repeated vertices are the first and last vertices. For example, given the graph depicted in Figure 1.1 we have, 1 -> 2 -> 3 is a path of length 2 and 1 -> 2 -> 3 -> 4 -> 2 is a walk of length 4. A walk of the form 2 -> 3 -> 4 -> 2 is called a cycle.

A chain is a sequence of vertices from one vertex to another using the edges. A chain is closed if the first and last vertex are the same. A graph is called connected if there is a chain between every pair of vertices in the graph.

Throughout the presentation of this thesis all considered graphs are simple and connected.

Definition 1.3. A cycle or circular graph is a graph that consists of a single cycle, or in other words, a number of vertices (at least 3) connected in a closed chain. The cycle graph with q vertices is called C q . The number of vertices in C q equals the number of edges, and every vertex has a degree 2; that is, every vertex has exactly two edges incident with it.

A cycle with an even number of vertices is called an even cycle; a cycle with an odd number of vertices is called an odd cycle. For example, in Figure 1.2 the graph dedicated on the left is an odd cycle C 3 .

Definition 1.4. A graph, in which each pair of distinct vertices is adjacent, is a complete graph i.e., (∀i, j ∈ V, i-j). We denote the complete graph on q vertices by K q and it has q(q -1)/2 edges.

Definition 1.5. A k-partite graph is a graph whose vertices are or can be partitioned into k different independent sets. If k = 2, we say that the graph is a bipartite graph. A complete k-partite graph (also its called separable graph in [START_REF] Mairesse | Stability of the stochastc matching model[END_REF]) is a k-partite graph in which there is an edge between every pair of vertices from different independent sets. Example 1.1. The two graphs depicted in Figure 1.2 are complete 3-partite graphs. The graph on the left is K 3 (i.e., for any two vertices i, j we have i-j). The independent sets are I 1 = {1}, I 2 = {2} and I 3 = {3}. However, the graph on the right is not a complete graph.

The independent sets are I 1 = {1}, I 2 = {2, 4, 6} and I 3 = {3, 5}.

In the Figure 1.3, we present the famous types of bipartite graph, such as, 'N' graph, 'NN' graph and 'W' graph.

Hypergraphs

In this section we consider that S be a hypergraph under the form H = (V, H). For easy reference, let us first introduce the basics of hypergraph theory will be used in this thesis.

HYPERGRAPHS

A throughout presentation of the topic can be found e.g., in [START_REF] Berge | Hypergraphs : Combinatorics of Finite Sets[END_REF].

A hypergraph H is defined as a couple (V,H), where V is a finite set of nodes of H and H := H 1 , ..., H m(H) is a finite set whose elements are called hyperedges of H.

We say that the hypergraph is simple (or a Sperner family) if H i ⊂ H j implies i = j for all i, j ∈ 1, m(H) , i.e., no hyperedge is included in another one (if not, say that the hypergraph is multiple hypergraphs) see Figure 1.4. We assume hereafter that all hypergraphs are simple. A subhypergraph of H is a hypergraph H = (V, H ) such that H ⊂ H. Definition 1.6. Let H = (V, H) be a hypergraph. The rank of H is the largest size of a hyperedge, i.e., the integer r(H) = max j∈ 1,m(H) |H j |; the anti-rank of H is defined as a(H) = min j∈ 1,m(H) |H j |, i.e., the smallest size of a hyperedge. If there exists a constant r such that r(H) = a(H) = r, then H is said r-uniform.

Remark 1.1. As is easily seen, any 2-uniform hypergraph is a graph whose edges are the elements of H, and any simple, connected hypergraph contains no isolated node, i.e., has anti-rank at least 2.

H = (V, H) with V = {1, 2, 3, 4} and H = {{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}}.
The cardinal of V is equal to 4, then H is of order 4; it is simple because no hyperedges is included in another one; it is 3-uniform since all hyperedges are of cardinality 3, and 3regular, because all nodes are of degree 3 (they all belong to exactly 3 hyperedges). As all hyperedges of cardinality 3 appear in H, this hypergraph is said Complete 3-uniform of order 4.

partition V 1 , V 2 of V such that for any H ∈ H, |H ∩ V 1 | = 1 and |H ∩ V 2 | = r -1.
Remark 1.2. Notice, first, that in the case r = 2, H being 2-partite means exactly that it is bipartite. Second, any 2-uniform bipartite hypergraph cannot be 2-partite unless it is a bipartite graph.

Definition 1.9. A hypergraph H = (V, H) satisfies Hall's condition if |V 2 | ≥ |V 1 | for any disjoint subsets V 2 and V 1 of V satisfying |H ∩ V 2 | ≥ |H ∩ V 1 | for all hyperedges H ∈ H. Example 1.3. Consider a 4-uniform hypergraph H = (V, H) such that V = {1, 2, 3, 4, 5}
and H = {{1, 2, 4, 5}, {1, 3, 4, 5}, {2, 3, 4, 5}} . There exists a partition of V into two dis-

joint sets V 1 = {1, 2, 3} and V 2 = {4, 5} such that |V 2 | < |V 1 | and for any H ∈ H, we have |H ∩ V 2 | ≥ |H ∩ V 1 |. Then V 1 and V 2 violating Hall's condition. Definition 1.10. An r-uniform (r ≥ 2) hypergraph H is called an -(Hamiltonian) cycle (0 < < r), if there exists an ordering V = v 1 , v 2 , • • • , v q(H
) of the nodes of V such that: • Every hyperedge of H consists of r consecutive nodes modulo q(H);

• Any couple of consecutive hyperedges (in an obvious sense) intersects in exactly vertices.

In Figure 1.6 we have a 3-uniform 2-(hamiltonian) cycle of order 12 and a 3-uniform 2-cycle of order 6.

Definition 1.11. A 3-uniform hypergraph H = (V, H) is said to be complete k-partite, if there exists a partition of V into k independent sets I 1 , ..., I k such that H contains exactly all subsets of cardinality 3 of the form {v 1 , v 2 , v 3 }, where v 1 ∈ I i 1 , v 2 ∈ I i 2 , and v 3 ∈ I i 3 , for three distinct independent sets I i 1 , I i 2 , and

I i 3 . Example 1.4. Consider a 3-uniform hypergraph H = (V, H) such that V = {1, 2, 3, 4, 5}
and H = {{1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {2, 3, 4}, {2, 3, 5}} . There exists a partiton of V into four independent sets

I 1 = {1}, I 2 = {2}, I 3 = {3} and I 4 = {4, 5}.
Then H is complete 3-uniform 4-partite hypergraph.

Summaries: Consider a hypergraph H = (V, H). The rank (respectively anti-rank) of H is the largest (respectively smallest) size of hyperedge. If the rank and anti-rank are equal to k, we then say H is k-uniforme. A k-uniform hypergraph H = (V, H) of order q is said,

• complete k-uniform if all hyperedges of cardinality k appear in H. • k-uniform bipartite if there exists V 1 and V 2 a partition of V such that |H ∩ V 1 | = 1 and |H ∩ V 2 | = k -1. • k-uniform k-partite if there exists a partition V 1 , V 2 , • • • , V k of V such that for any H ∈ H and any i ≤ k, |H ∩ V i | = 1.
Throughout this thesis, all considered hypergraphs are connected and simple.

Multigraphs

In this section consider that S be a multigraph under the form G = (V, E). For easy reference, let us introduce the basics that we will be used in this thesis. Definition 1.12. A multigraph is a graph that given by a couple G = (V, E), where V is the (finite) set of nodes, and E is the set of edges, which is permitted to have multiple edges (also called parallel edges), else it is called simple edges and also a permitted to have self-loops, that is, an edge which starts and ends at the same nodes. Elements of the form {v} ∈ E, are called self-loops. We write u-v or v-u for {u, v} ∈ E, and u -v (or v -u) else.

As the equation (1.1), and specifically for any multigraph G = (V, E) and any U ⊂ V, we denote

E(U ) := {v ∈ V : ∃u ∈ U, u -v}, the set V can then be partitioned in V = V 1 ∪ V 2 , where V 1 := {u ∈ V : u-u} and V 2 := {u ∈ V : u -u}, i.e., V 1
contains all nodes from which a self-loop emanates, if any, and V 2 is the complement set of V 1 in V. Observe that, concerning the classical notion of multigraphs, we assume hereafter that all edges are simple.

A multigraph having no self-loop, that is, a couple G = (V, E) such that V 1 = ∅, is simply a graph. A multigraph is connected if for any u, v ∈ V, there exists a subset {v 0 = u, v 1 , v 2 , . . . , v p = v} ⊂ V such that v i -v i+1 , for any i ∈ 0, p -1 . For any multigraph G = (V = V 1 ∪ V 2 , E) and any U ⊂ V, the subgraph induced by U in G is the multigraph (U, E ∩ U ). Observe that ∀ I ∈ I(G), we get I ∩ V 1 = ∅, i.e., I ⊂ V 2 .
Remark 1.3. A multigraph is different from a hypergraph, which is a graph in which an hyperedge can connect any number of nodes, not just two.

Throughout this thesis, all considered multigraphs are connected and without the possibility of multiple edges.

MAIN USEFUL PROBABILISTIC RESULTS

Definition 1.13. Let G = (V, E) be a multigraph. The maximal subgraph of G is the graph Ǧ = (V, Ě) obtained by deleting all self-loops in G, that is

Ě = E \ {(i, i) : i ∈ V 1 } . (1.2)
See an example of a Figure 1.7. E) be a multigraph. The minimal blow-up graph of G is the graph Ĝ = ( V, Ê) defined as follows:

Definition 1.14. Let G = (V 1 ∪ V 2 ,
V = V ∪ V 1 and Ê = Ě ∪ E 1 , (1.3)
where V 1 is an independent copy of V 1 , Ě is defined by (1.2) and

E 1 = {(i, j) : (i, j) ∈ E, i ∈ V 1 , j ∈ V}.
In other words, Ĝ is obtained from G by duplicating each node having a self-loop by two nodes having the same neighborhood and replacing each self-loop by an edge between the node and its copy. See an example of a Figure 1.7.

The maximal subgraph Ǧ of G is then called reduced graph of Ĝ.

For any set A ⊂ V 1 , we denote by A the set of all copies of elements of A, that is

A = {i : i ∈ A} .

Main useful probabilistic results

In Chapter 2, we will define the stochastic matching model and the corresponding Markov chain representation, while in this Section we present two famous techniques (Lyapunov-Foster Theorem and Fluid limits) that help us to find the stability of the model (i.e., its Markov chain is positive recurrent).

Lyapunov-Foster Theorem

This section is taken from ([8], §5.1):

The following Theorem provides an ergodicity criterion for countable Markov chain valued in countable state space E, Theorem 1.1. Let the transition matrix P = {p ij } i,j∈E on the countable state space E be irreducible and suppose that there exists a function h :

E -→ R such that inf i h(i) > -∞ and k∈E p ik h(k) < ∞ for all i ∈ F, (1.4
)

k∈E p ik h(k) ≤ h(i) -ε for all i / ∈ F, (1.5)
for some finite set F and some ε > 0. Then the corresponding Markov chain is positive recurrent.

The stationary distribution criterion of positive recurrence of an irreducible chain requires solving the balance equation, a too-often hopeless enterprise except in a few textbook situations. The above sufficient condition is more tractable, and indeed quite powerful.

1.6.2 Classification of random walks in

(Z + ) 2
This section is taken from ( [START_REF] Fayolle | Topics in the Constructive Theory of Countable Markov Chains[END_REF], §3.3):

Consider a discrete time homogeneous irreducible and aperiodic Markov chain L = {E n ; n ≥ 0}. Its state space is the lattice in the positive quarter-plane (Z + ) 2 = {(i, j) : i, j ≥ 0, integers} and it satisfies the recursive equation

E n+1 = [E n + θ n+1 ] + ,
where the distribution of θ n+1 depends only on the position of E n in the following way (maximal space homogeneity):

p{θ n+1 = (i, j)/E n = (k, l)} =            p ij , for k, l ≥ 1, p ij , for k ≥ 1, l = 0, p ij , for k = 0, l ≥ 1, p 0 ij , for k, l = 0,
where p ij , p ij , p ij and p 0 ij are probabilities belong to the interval [0, 1]. Moreover, for the one-step transition probabilities, making the following assumptions:

1.6. MAIN USEFUL PROBABILISTIC RESULTS Condition A (Lower boundedness)      p ij = 0, if i < -1 or j < -1, p ij = 0, if i < -1 or j < 0, p ij = 0, if i < 0 or j < -1, Condition B (First moment condition) E [||θ n+1 ||/E n = (k, l)] ≤ C < ∞, ∀(k, l) ∈ (Z + ) 2 ,
where ||z||, z ∈ (Z + ) 2 , denotes the euclidean norm and C is an arbitrary but strictly positive number.

Notation: Using lower case greek letters α, β, • • • to denote arbitrary points of (Z + ) 2 , and then p αβ will mean the one-step transition probabilities of the Markov chain L, α > 0 means α x > 0, α y > 0, for α = (α x , α y ).

Also, from the homogeneity conditions, one can write

θ n+1 = (θ x , θ y ),
given that E n = (x, y).

Define the vector

M (α) = (M x (α), M y (α))
of the one-step mean jumps (drifts) from the point α. setting α = (α x , α y ), β = (β x , β y ),

we have M x (α) = β p αβ (β x -α x ), M y (α) = β p αβ (β y -α y ).
Condition B ensures the existence of M (α), for all α ∈ (Z + ) 2 . By the homogeneity condition A, only four drift vectors are different from zero:

M (α) =            M, for α x , α y > 0, M , for α = (α x , 0), α x > 0;
M , for α = (0, α y ), α y > 0;

M 0 , for α = (0, 0).

Remark 1.4. (i) All our results remain valid if a finite number of transition probabilities are arbitrarily modified.

(ii) Given E n = α, the components of θ n+1 might be taken bounded from below not by -1, but by some arbitrary number -K > -∞, provided that:

First, we keep the maximal homogeneity for the drift vectors M (α) introduced above (i.e., four of them only different);

Secondly, the second moments and the covariance of the one-step jumps inside (Z + ) 2 , i.e., from any point α > 0, are kept constant.

These last fact will emerge more clearly in the course of the study.

Theorem 1.2. Assume conditions A and B are satisfied.

(a) If M x < 0, M y < 0, then the Markov chain L is

(i) ergodic if M x M y -M y M x < 0, M y M x -M x M y < 0; (ii) non-ergodic if either M x M y -M y M x ≥ 0 or M y M x -M x M y ≥ 0. (b) If M x ≥ 0, M y < 0, then the Markov chain L is (i) ergodic if M x M y -M y M x < 0; (ii) transient if M x M y -M y M x > 0. (c) (Case symmetric to case (b)) If M y ≥ 0, M x < 0, then the Markov chain L is (i) ergodic if M y M x -M x M y < 0; (ii) transient if M y M x -M x M y > 0. (d) If M x ≥ 0, M y ≥ 0, M x + M y > 0, then the Markov chain is transient.
Consider the following real functions on (Z + ) 2 :

     Q(x, y) = ux 2 + vy 2 + ωxy, f (x, y) = Q 1/2 (x, y), ∆f (x, y) = Q 1/2 (x + θ x , y + θ y ) -Q 1/2 (x, y),
where (x, y) ∈ (Z + ) 2 and u, v, ω are unspecified constants, to be properly chosen later, but subject to the constraints u, v > 0, 4uv > ω 2 , so that the quadratic form Q is positive definite.

Lemma 1.1. We have

E [∆f (x, y)] = x[2uE [θ x ] + ωE [θ y ]] + y[ωE [θ x ] + 2vE [θ y ]] 2f (x, y) + o(1),
where o(1) → 0 as (x 2 + y 2 ) → ∞.

Proof of Theorem 1.2 : First, we shall prove ergodicity in the case (a(i)). Lemma 1.1 shows that, if there exists u, v > 0 and ω 2 < 4uv, such that, for somme ε 2 > 0 and all (x, y) ∈ (Z + ) 2 \A, where A in a finite set,

2uE [θ x ] + ωE [θ y ] < -ε 2 , ωE [θ x ] + 2vE [θ y ] < -ε 2 , (1.6)
then, for some D, there exists ε > 0 such that for all (x, y) with x 2 + y 2 > D 2 , we have

E [∆f (x, y)] < -ε. (1.7)
Therefore, when (1.7) holds, the random walk is ergodic, by using Lyapunov-Foster Theorem. Let us rewirte inequalities (1.7) in terms of the drifts on the axes and in the internal

part of (Z + ) 2 ,            2uM x + ωM y < -ε 2 , 2vM y + ωM x < -ε 2 , 2uM x + ωM y < -ε 2 , 2vM y + ωM x < -ε 2 . (1.8) It is easy to show that, if            M x < 0, M y < 0, M x M y -M y M x < 0, M y M x -M s M y < 0, (1.9)
then there exists u

= -M x /2, v = -M y /2 > 0 and max (M x ; M y ) < ω < min MyM x M y ; MxM y M x
then ω 2 < 4uv, such that (1.8) is satisfied for some ε 2 > 0, thus poving case a(i). The cases (b(i)) and (c(i)) are analogus to (a( i)). Indeed, if

     M x ≥ 0, M y < 0, M x M y -M y M x < 0, or      M x < 0, M y ≥ 0, M y M x -M x M y < 0,
we show that there exists u, v > 0 and ω 2 < 4uv, such that (1.8) holds, so that the chain is ergodic in both cases.

Now the prove of non-ergodicity in (a(ii)). Assume that

     M x < 0, M y < 0, M x M y -M y M x ≥ 0.
There exists a linear function f (x, y) = ax + by, such that, for all α = (x, y) with ax + by ≥ C, we have

f (α + M (α)) ≥ f (α) + ε, for some C, ε ≥ 0,
and the non-ergodicity is immediately deduced. The remain proof of the transience in (b(ii)), (c(ii)) and (d) is more difficult and can be found in ( [START_REF] Fayolle | Topics in the Constructive Theory of Countable Markov Chains[END_REF], §3.3).

Rescaled Markov processes and Fluid Limits

This section is taken from [44, Chapters 5 and 9] :

In this section, limit results consist in speeding up time and scaling appropriately the process itself with some parameter. The behavior of such rescaled stochastic processes is analyzed when the scaling parameter goes to infinity. In the limit one gets a sort of caricature of the initial stochastic process which is defined as a fluid limit. These ideas of rescaling stochastic processes has emerged in the analysis of stochastic networks, to study their ergodicity properties in particular, see [START_REF] Rybko | Ergodicity of stochastic processes describing the operations of open queueing networks[END_REF]. In statistical physics, these methods are quite classical, see [START_REF] Comets | Limites hydrodynamiques[END_REF].

In the following, (X(x, t)) denotes an irreducible 'RCLL' continuous-time Markov chain on a countable state space U starting from x ∈ U, i.e., such that X(x, 0) = x ∈ U. Denotes by N ε (ω, dx), ω ∈ Ω, a Poisson point process on R with parameter ε ∈ R + , all Poisson processes used are assume to be a priori independent. The topology on the space of probability distributions induced by the Skorokhod topology on the space of 'RCLL' functions

D [0, T ], R d is used.

Rescaled Markov Processes

Throughout this subsection, assumed that the state space U can be embedded in a subset of some normed space R d , . denotes the associated norm.

Definition 1.15. For x ∈ U, X(x, t) denotes the process (X(x, t)) renormalized so that for t ≥ 0, X(x, t) = 1 x X(x, x t).

MAIN USEFUL PROBABILISTIC RESULTS

Only continuous-time Markov processes are considered in this section. In discrete-time, if (X n ) n∈N is a Markov chain, the corresponding rescaled process can be also defined by

X(x, t) = X x t x ,
where X 0 = x ∈ U and t ∈ R + .

Fluid limits

Fluid limits are the results of a scaling of the number of customers of an M/M/1 queue. The scaling considered here consists in speeding up the time scale with the size of its initial state and in scaling the process with the same quantity. The procedure suppresses some random

fluctuations around what appears to be the main trajectory of the process. For the M/M/1 queue the behavior of the rescaled process is very simple.

Initially, there are x N customers in the queue and the sequence (x N ) is such that

lim N →+∞ x N N = x ∈ R + .
Suppose that L(t) is the number of customers of the queue at time t ≥ 0. Assumed that L(t)

be a stochastic process. The renormalized process LN (t) is defined by,

LN (t) = L(N t) N ,
notice that LN lives on a very rapid time t → N t, arrivals and services are sped up by a factor N. The scaling by 1/N compensates the acceleration of time. Consider the scaling depicted on Figure 1.8, the stochastic process (L(t)) is reduced to a deterministic drift (λ -µ)t.

If λ < µ, once the renormalized process hits 0, it remains at 0. This property is, in some sense, characteristic of ergodic Markov processes. Intuitively, it can be argued as follows:

Once the process (L(t)) hits 0, with the coupling argument of [START_REF] Robert | Stochastic networks and queues[END_REF]Proposition 5.8], it is approximately at equilibrium and it is mainly living in bounded neighborhood of 0. The time scale, linear with N , does not allow the visit of large values since an exponential time scale is necessary for this purpose, of the order (µ/λ) N y to reach the value N y. The scaling factor 1/N suppresses these small variations. This explains that the renormalized process is stuck at 0. Definition 1.16. A fluid limit associated with the Markov process (X(t)) is a stochastic process which is one of the limits of the process X(x, t) = X(x, x t) x when x goes to infinity.

Strictly speaking, if Q x is the distribution of X(x, t) on the space of 'RCLL' functions

D (R + , U) , a fluid limit is a probability distribution Q on D R + , R d such that Q = lim n Q x n
for some sequence (x n ) of U whose norm converges to infinity. By choosing an appropriate probability space, it can be represented as a 'RCLL' stochastic process (W (t)) whose distribution is Q. A fluid limit is thus an asymptotic description of sample paths of a Markov process with a large initial state.

Example 1.5. (Fluid limits of the M/M/1 queue). The arrival rate is λ and the service rate µ, L(t) is the number of customers of the queue at time t ≥ 0. The renormalized process ( LN (t)) converges to a deterministic function, piecewise linear, i.e., if P-almost surely, the convergence of processes associated with the uniform norm on compact sets holds

lim N →+∞ LN (t) = (x + (λ -µ)t) + .
In addition, for ε, δ > 0, there exists

N 0 ∈ N such that, if N ≥ N 0 then inf |x/N -x|<δ/2 P x sup 0≤x≤t | LN (s) -(x + (λ -µ)s) + | < δ ≥ 1 -ε.
(1.10)

The function (x + (λ -µ)t) + is therefore the unique fluid limit of this Markov process. If we assume that λ < µ, this implies in particular that the Markov process L(t) is ergodic.

Chapter 2

Stochastic matching model

Stochastic matching techniques aim to study the dynamic systems resulting from group matching of individuals or agents on a microscopic scale. Different applications of this technique, in economics or finance, provide tools for studying over-the-counter contracts, labor and housing markets, co-operative sites, peer-to-peer networks, and so on. These applications stimulate the introduction of dynamic probabilistic modeling, at a discrete or continuous-time representing the evolution of stochastic matching between agents. The discrete-time models, initially introduced for healthcare systems (blood banks, organ allocations) are also adapted with continuous-time to specific applications. For this class of models, it is possible to describe the restrictive behavior of the size of a subset that meets such or that criteria, as well as market price formations, approximating them through a reduced system of non-linear differential equations.

The objective of this chapter is to describe the stochastic matching model with the approach of the Markov chain in discrete and continuous-time. In Section 2.1 we present the stochastic matching model on matching structures. In Section 2.2 we present further information for matching policies. In Section 2.3 we formulate a Markov representation of the general model. In Section 2.4 we define the stability and the instability of the model.

Finally, in Section 2.5 we present the matching queue and the stability of the continuous model which we will be used in Chapter 6.

Stochastic model on matching structures

A (discrete-time, matching structure) stochastic matching model is specified by a triple (S, Φ, µ), such that:

• S = (V, S) is a connected matching structure which can be a non-bipartite graph, hypergraph or multigraph;

• Φ is a matching policy, which defines the new buffer-content given the pair formed by the old buffer-content and the arriving item, precisely defined in section 2.2 below;

• µ is an element of M (V), the common law of the independent and identically distributed (i.i.d.) classes of the arriving items.

The models

The matching model (S, Φ, µ) is then defined as follows. At each time point n ∈ N + ,

1. An item enters the system. Its class V n is drawn from the measure µ on V, independently of everything else. Thus the sequence of classes of incoming items

{V n ; n ∈ N} is i.i.d. of common distribution µ .
2. The incoming item then faces the following alternatives:

(i) If there exists in the buffer, at least one set of items whose respective set of classes forms, together with V n , an edge of S, then it is the role of the matching policy Φ to select one of these sets of classes, say {i 1 , ..., i m }, m ≥ 1 in the cases of graph and multigraph (m = 1), and for hypergraph (m ≥ 1) . Then the m + 1 items of respective classes i 1 , ..., i m , V n are matched together and leave the system right away. Denoting S j := {i 1 , ..., i m , V n } ∈ S, for j ∈ [ [1, |S|]] in the case of multigraph for the self-loop edges, we have the possibility of having i 1 and V n coincides , we then say that V n completes a matching of type S j at time n, and we denote S(n) = S j , the matching performed at n.

(ii) Else, the item is stored in the buffer of the system, waiting for a future match, and we write S(n) = ∅.

State spaces

We reproduce here the state description of the model introduced in [START_REF] Mairesse | Stability of the stochastc matching model[END_REF] for the stochastic model on general graphs, and then [START_REF] Moyal | Loynes construction for the Extended bipartite matching[END_REF] for the same model under the matching policy FCFM.

Fix a connected matching structure S = (V, S), in the sense specified above, until the end of this section. Fix an integer n 0 ≥ 1, a realization v 1 , . . . , v n 0 of V 1 , . . . , V n 0 , and define the

word z = v 1 . . . v n 0 ∈ V * .
Then, for any matching policy Φ, there exists a unique matching of the word z, that is, a matching structure having a set of nodes {v 1 , . . . , v n 0 } and whose edges represent the matches performed in the system until time n 0 , if the successive arrivals are given by z. This matching is denoted by M Φ (z). The state of the system is then defined as the word W Φ (z) ∈ V * , whose letters are the classes of the unmatched items at time n 0 , i.e., the isolated vertices in the matching M Φ (z), in their order of arrivals. The word W Φ (z) is called queue detail at time n 0 . Then, any admissible queue detail belongs to the set

W = w ∈ V * : ∀i = j = • • • = k s.t. {i, j, • • • , k} ∈ S, |w| i |w| j • • • |w| k = 0 . (2.1)
As will be seen below, depending on the service discipline Φ, we can also restrict the available information on the state of the system at time n 0 , to a vector only keeping track of the number of items of the various classes remaining unmatched at n 0 , that is, of the number of occurrences of the various letters of the alphabet V in the word W Φ (z). This restricted state thus equals the commutative image of W Φ (z) and is called class detail of the system.

It takes values in the set

X = x ∈ N |V| : ∀i = j = • • • = k s.t. {i, j, • • • , k} ∈ S, x(i)x(j) • • • x(k) = 0 = [w] : w ∈ W . (2.2)
Remark 2.1. Denote, in case that S = (V, S) be a multigraphs whose vertex divided into

two subsets V = V 1 ∪ V 2 such that V 1 = ∅,
we must add the following restrictions:

• In equation (2.1) we have ∀i ∈ V 1 , |w| i ≤ 1; • In equation (2.2) we have ∀i ∈ V 1 , x(i) ≤ 1.
Let us order the elements of V and identify them with 1, |V| , in a way that the |V 1 | first elements are those of V 1 and the remaining |V 2 | elements are those of V 2 . We index the elements of X accordingly: namely, for any x ∈ X and any i ∈ 1, |V| , x(i) is the queue size of node i. With these conventions, for instance, the coordinate x(|V 1 | + 3) corresponds to the queue size of the third node of V 2 .

Matching policies

In this section, we present and formally define the set of matching policies that can be taken into consideration.

Definition 2.1. A matching policy Φ is said admissible if the choice of the match of an incoming item depends solely on the queue detail upon the arrival (and possibly on an independent uniform draw, in case of a tie).

An admissible matching policy can be formally characterized by an action Φ of V on W, defined as follows: if w is the queue detail at a given time and the input is augmented by the arrival of v ∈ V at that time, then the new queue detail w and w satisfies the relation

w = w Φ v. (2.3)
Notice that the action Φ is possibly random.

Matching policies that depend on the arrival times

In 'First Come, First Matched' (FCFM), the oldest item in line is chosen, so the map FCFM is given, for all w ∈ W and all v ∈ V, by

w FCFM v =      wv if for any S ∈ S(v) there exists i = v ∈ S s.t |w| i = 0, w [Φ(w,v)] else, where Φ(w, v) = {i, j, • • • , k} such that i = min{ ∈ [[1; |w|]] : there exists S ∈ S(v) s.t w ∈ S},
where ties are broken from the minimum of the next term j as i whenever the above is nonunique.

In 'Last Come, First Matched' (LCFM), the updating map LCFM is analog to FCFM , for

Φ(w, v) = {i, j, • • • , k} such that i = max{ ∈ [[1; |w|]] : there exists S ∈ S(v) s.t w ∈ S}.

Class-admissible matching policies

A matching policy Φ is said to be class-admissible if it can be implemented upon the sole knowledge of the class detail of the system. Let us define, for any x ∈ X, and any v ∈ V,

P(x, v) = S ∈ S(v) : ∀i ∈ S\{v}, x (i) > 0 ,
the set of classes of available compatible items with the entering class v-item, if the class detail of the system is given by x. Then, a class-admissible policy Φ is fully characterized by a mapping p Φ , such that p Φ (x, v) denotes the class of the match chosen by the entering v-item under Φ, in a system of class detail x, such that P(x, v) is non-empty. Then, the arrival of v entails the following action on the class detail:

x Φ v = x + e v if P(x, v) = ∅, x -e p Φ (x,v) else.
(2.4)

Remark 2.2. As is easily seen, to any class-admissible policy Φ corresponds an admissible policy, if one makes precise the rule of choice of a match for the incoming items within the class that is chosen by Φ, in the case where more than one item of that class is present in the system. In this thesis, we always assume that within classes, the item chosen is always the oldest in the line, i.e., we always apply an FCFM policy within classes. Under this convention, any class-admissible policy Φ is admissible, that is, the mapping Φ from

X × V to X can be detailed into a map Φ from W × V to W, as in (2.
3), that is, such that for any queue detail w and any v,

[w Φ v] = [w] Φ v.
Fixed priority policies In the context of fixed priorities, each vertex i ∈ V is assigned a full ordering of the edges and chooses to be matched with the first matchable edge following this order. Formally, to each node i is associated a permutation σ i of the index set 1, d(i) , and if we denote S(i) = S i 1 , S i 2 , ..., S i d(i) , then at any time n,

p Φ (x, v) = S i σ i (j) , where j = min k ∈ 1, d(i) : S i σ i (k) ∈ P(x, v) > 0 . (2.5)
Random policies For this matching policy, the priority order defined above is not fixed and is drawn uniformly at random upon each arrival, i.e., for any v, p Φ (x, v) is defined as in equation (2.5), for a permutation σ i that is drawn, independently of everything else, uniformly at random among all permutations of 1, d(i) .

Max-Weight policies

The Max-Weight policies are an important class of class-admissible policies, in which matches are based upon the queue length and a fixed reward that is associated with each match. Formally, for any S ∈ S , we let w S be the reward associated to the match of the items of S together, and fix a real parameter β.

Then, in a system of class detail x, the match of the incoming v-item is given by

p Φ (x, v) = argmax {βx(S) + w S : S ∈ P(x, v)} ,
where ties are broken uniformly at random whenever the above is non-unique. In other words, S maximizes a linear combination of the queues-size and the rewards. Several particular cases are to be mentioned:

(i) If β > 0 and the rewards are constant (i.e., w S = w S , for any S, S ∈ S), then the matching policy is 'Match the Longest' (ML), i.e., the incoming v-item is matched upon the arrival with the items of the compatible classes having the longest queues size (ties being broken uniformly at random).

(ii) If β < 0 and the rewards are constant, then the matching policy is 'Match the Shortest' (MS), i.e., the incoming v-item is matched upon the arrival with the items of the compatible classes having the shortest queues size (ties being broken uniformly at random).

(iii) If β = 0 and w S = w S for any i ∈ V and any S = S ∈ S(i) (implying that there is a strict ordering of rewards for all possible matches of any given class), then the matching policy is of a priority type, defined above.

Primary Markov representations

The Markov representations of the model are similar to general matching models on graphs.

Denote, for all w ∈ W and all n ≥ 1, by W {w} n , the buffer-content at time n (i.e., just after the arrival of the item V n ) if the buffer-content at time 0 was set to w. In other words,

W {w} 0 = 0, W {w} n = W Φ (wV 1 . . . V n ) , n ∈ N + .
It readily follows from (2.3) that the buffer-content sequence W {w} n ; n ∈ N is a Markov chain. Indeed, for any w ∈ W, we have

W {w} n+1 = W {w} n Φ V n+1 , ∀n ∈ N.
Secondly, we deduce from (2.4) that for any class-admissible matching policy Φ (e.g., Φ = U, ML or MS) and any initial condition as above, the X-valued sequence {X n ; n ∈ N} of class details also is a Markov chain, as for any initial condition x ∈ X, we get

X {x} n+1 = X {x} n Φ V n+1 , ∀n ∈ N.
For a fixed initial condition and all n ∈ N, we denote, for all B ⊂ V, by W n (B), the number of items in the line of classes in B at time n, and by |W n |, the total number of items in the 2.4. STABILITY OF THE MATCHING MODEL system at time n. In other words,

       W n (B) = i∈B W n (i), |W n | = W n (V) = i∈V W n (i).

Stability of the matching model

We say that the matching model (S, Φ, µ) is stable if the Markov chain {W n ; n ∈ N} and thereby {X n ; n ∈ N} is positive recurrent.

Consider a matching structure S = (V, S) and a matching policy Φ, we define the stability region associated to S and Φ as the set of probability measures on V rendering the model

(S, Φ, µ) stable, i.e., STAB(S, Φ) = {µ ∈ M (V) : {W n ; n ∈ N} is positive recurrent} . Remark 2.3. If the matching structure S = (V, S) is a multigraph such that V = V 1 , i.e., all
nodes of the multigraph have a self-loop, we say, for obvious reasons, that the considered matching models are finite. Then any matching model on S is necessarily stable, that is, for any admissible Φ we have that

STAB(S, Φ) = M (V).
Indeed, the Markov chain {W n ; n ∈ N} is irreducible on the finite state space W, containing only words having a size less or equal to the cardinality of the largest independent set of S.

Definition 2.2. A connected matching structure S is said to be,

• stabilizable if STAB(S, Φ) is non-empty for some matching policy Φ,

• non-stabilizable if STAB(S, Φ) is empty.

Continuous-Time Markov chain processes

Now, we present a stochastic matching model in continuous-time where each class of items arrive at the system according to an independent Poisson process of intensity λ > 0.

A throughout presentation of this section can be found e.g. in [START_REF] Moyal | On the instability of matching queues[END_REF].

Matching Queues

The matching queue associated with a matching structure S = (V, S), an arrival-rate vector

λ := (λ 1 , • • • , λ |V| )
and the matching policy Φ, is defined as follows:

• Each node of V is associated with a class of items;

• Items of each class i ∈ V arrive to the system according to an independent Poisson process N i of intensity λ i > 0;

• A class-i items can be matched with class-j, • • • , class-k items if and only if there is

an edge S = {i, j, • • • , k} ∈ S;
• Upon arrival at time t, a class-i item is either matched exactly with the classes j,

• • • , k such that S(t) = {i, j, • • • , k}
, if any such items are available it leave the system immediately, or are placed in an infinite buffer.

Let us define the following summation λ:

λ := i∈V λ i λA := i∈A λ i , A ⊂ V. (2.6)
Remark 2.4. The Poisson process can be obtained by evaluating the following assumptions for arrivals during an infinitesimal short period of time δt :

• The probability that one arrival occurs between t and t + δt is t + o(t), independent of the time t, and independent of arrivals in earlier intervals.

• The number of arrivals in non-overlapping intervals are statistically independent.

• The probability of two or more arrivals happening during [t, t + δt] is negligible compared to the probability of zero or one arrival, i.e., it is of the order o(t).

System dynamics

Each vertex i associated to a buffer content called class-i queue, and denote the associated class-i queue process by

Q i := {Q i (t) : t ≥ 0}. More precisely, for all t ≥ 0, Q i (t) is
the number of the class-i items in the queue at time t. The |V|-dimensional queue process of the system denoted as follows:

Q = (Q 1 , • • • , Q V ). (2.7)
For t ≥ 0 and A ⊂ V, we let Q A (t) be the restriction of Q(t) to its coordinates in A. Upon arrival to the system, an element of the class-i can find several possible matches. A matching policy is a rule specifying how to match in such cases. We say that a matching policy Φ is admissible if matches always occur when possible, and decisions are made only on the value of the Q queue process at arrival times.

For a matching structure S, an arrival-rate vector λ and under the admissible matching policy Φ, the queue process Q is as follows:

• Its a Continuous-Time Markov Chain denoted by 'CTMC';

• The initial queue length Q(0);

• For all t ≥ 0, Q i (t)Q j (t) • • • Q k (t) = 0 where i, j, • • • , k ∈ V such that S(t) = {i, j, • • • k} ∈ S.
We thus characterize the system by the triple (S, Φ, λ) C (where we append the subscript C to denote a continuous-time model, as opposed to the one in discrete-time, which will omit the subscript C).

Example 2.2. In [START_REF] Nazari | Optimal control of general dynamic matching systems[END_REF] was shown an example of a matching system with 4 item types depicted on Figure 2.2. The items arrive as a random process, as individual items, or in batches.

The average arrival rate of type i items is α i . There exist three possible matchings; e.g., 1, 2 respectivily 2, 3 is a matching which matches one item of type 1 with one item of type 2 resp one item of type 2 with one item of type 3. 2, 3, 4 is another matching which matches one item of types 2, 3 and 4.

A matching can only be applied if all contributing items are present in the system; and if it is applied, the contributing items instantaneously leave the system.

Stability of a matching queue

The matching queue (S, Φ, λ) C is said to be stable if the corresponding CTMC Q is positive recurrent, and unstable otherwise.

Definition 2.3. The stability region corresponding to the connected matching structures S and the matching policy Φ is the set

STAB(S, Φ) = λ ∈ (R ++ ) |V| : (S, Φ, λ) C is stable .
We also say that node i ∈ V is stable if, for some initial condition, the mean time for its associated queue to empty is finite. Otherwise, the node is unstable. Indeed, the advantage of the fluid limit techniques in continuous-time is to facilitate stability analysis. Thus, as was shown in [37, Theorem 2], the stability region of a discretetime stochastic model can be studied by embedding it in an appropriate continuous-time mode. Then, the continuous-time counterparts of the results in [START_REF] Rahme | A stochastic matching models on hypergraphs[END_REF][START_REF] Mairesse | Stability of the stochastc matching model[END_REF][START_REF] Jonckheere | Generalized Max-Weight policies in stochastic matching[END_REF] hold for our matching queues and vice versa.

Chapter 3

Literature review

Nowadays, the matching model is considered one of the major challenges that are of interest in various sectors (healthcare systems, peer-to-peer networks, interfaces of the collaborative economy, assemble-to-order systems, job search applications, and so on). Other references address specific models for designated applications: [START_REF] Davis | Addressing US national geographic disparity in kidney transplantation by creating sharing partnerships[END_REF] on organ transplantation, [START_REF] Boxma | A new look at organ transplantation models and double matching queues[END_REF] on kidney transplants, [START_REF] Talreja | Fluid models for overloaded multiclass many-server queueing systems with first-come, first-served routing[END_REF] on housing allocations systems, or [START_REF] Özkan | Dynamic matching for real-time ridesharing[END_REF] on ride-sharing models.

A more recent application for the matching model results in modeling sharing-economy (collaborative consumption) platforms, with the most relevant examples being car-sharing platforms, such as Uber and Lyft, lodging services, such as Airbnb, and virtual call centers (namely call centers with home-based agents), as considered in, e.g., [START_REF] Gurvich | Operations in the on-demand economy: Staffing services with self-scheduling capacity[END_REF][START_REF] Ibrahim | Staffing a service system where capacity is random[END_REF]. Since a platform operating in a sharing-economy market must match supply and demand at every instance, possibly in a multi-region setting, matching queues can be used to model and optimize such platforms; see [START_REF] Siddhartha | Pricing in Ride-Share Platforms: A Queueing-Theoretic Approach[END_REF] for an application in the car-sharing setting. Before passing to part II which contains the main subject and the results of our contributions, in this chapter, we present some of the related work for the matching models.

In Section 3.1, we present the first natural representation of service systems in which customers and servers are of different classes called skill-based queueing systems. In Section 3.2 we start from [START_REF] Caldentey | FCFS infinite bipartite matching of servers and customers[END_REF] where they have introduced the matching model referred to the bipartite matching model and we present some of related works. In Section 3.3 we describe the extended bipartite matching model (EBM). In Section 3.4 we represent all dedicated studies for the general matching model (GM). In Section 3.5 we address a point of view of stochastic optimization of the matching models. In Section 3.6 we present other extensions of the matching model. Finally, in Section 3.7 we represent the related study with our contributions.

Skill-based service systems

Over the past decade, an increasing interest has been dedicated to stochastic systems in which incoming elements are matched according to specified compatibility rules. This is, first, a natural representation of service systems in which customers and servers are of different classes, and where designated classes of servers can serve designated classes of customers. For this general class of queueing models, termed skill-based queueing systems, it is then natural to investigate the conditions for the existence of a stationary state, and under these conditions, to design and control the model at best, for given performance metrics (end-to-end delay, matching rates, fairness, and so on.) Such models are classical queueing systems, in the sense that there is a dissymmetry between customers and servers: customers come and depart the system, whereas servers are part of the 'hardware', remain in the system, and switch to the service of another customer when they have completed one (with possible vacation times in-between services) see Figure 3.1 (a). In [START_REF] Aksin | The modern call-center, a multi-disciplinary perspective on operations management research[END_REF][START_REF] Garnett | An introduction to skills-based routing and its operational complexities[END_REF] various types of customers call are routed to various groups of skill-based servers.

Generally, these studies consist of analyzing the stability of the model under which matching policy is optimal and the probability measures that makes it stable. It should be noted that a lot of works have advanced research and have been developed within the framework of stochastic matching model.

Bipartite Matching model (BM)

In [START_REF] Caldentey | FCFS infinite bipartite matching of servers and customers[END_REF]1], a variant of such skill-based systems have introduced, which are now commonly referred to as 'Bipartite Matching models' (BM): couples customer/server enter the system at each time point, and customers and servers play symmetric roles: exactly like customers, servers come and go into the system see Figure 3.1 (b). Upon arrival, they wait for a compatible customer, and as soon as they find one, leave the system together with it. These settings are suitable to various fields of applications, among which, blood banks, organ transplants, housing allocation, job search, dating websites, and so on.

The mathematical setting is the following: in the two aforementioned references, it is assumed that the incoming customers are of various classes in the set

C = {1, 2, • • • , I},
and that server are of classes in the set S = {1, 2, • • • , J}. It is assumed that a server of type j ∈ S can serve a subset of customer types C(j) ⊂ C, and that a customer of type i ∈ C can be served by a subset of server types S(i) ⊂ S.

Caldentey & al. [START_REF] Caldentey | FCFS infinite bipartite matching of servers and customers[END_REF] have considered the types of customers and servers if the infinite sequences are random, independent identically distributed, and customers and servers are matched according to their order in the sequence, on a First Come, First Matched (FCFS)

basis. This service system can be represented by a bipartite graph G = (C + S, E).

Consider the sequences (c n ; s n ) n≥1 ∈ C ∞ ×S ∞ have probability distribution P((c n ; s n ) = (i, j)) = α i β j , for probability vectors, α = (α i ) ∈ (R + ) I and β = (β j ) ∈ (R + ) J .
Define matching rates, by counting for each n the number of (c i ; s j ) matches created be-

tween c 1 ; • • • ; c n and s 1 ; • • • ; s n ,
and divide by n to get r n c i ;s j . For a given G, α, β, the matching rates r c i ;s j = lim n→+∞ r n c i ;s j if these limits exist almost surely.

The construction of the matching is to add one pair (independent) of a server and a customer at a time and to match those to the earliest unmatched customer or server that they find, or leave them unmatched, waiting for subsequent pairs.

They have proposed two following simplifications: 1. First simplification which leads to their model is that there are no service times.

Second simplification to the considered model, by ignoring the arrival times.

They said that the system has a balanced infinite matching: if the fraction of customers of type i among the first n customers, which are matched by one of the first n servers, converge almost surely to α i , and the fraction of servers of type j which are matched by one of the first n customers, converge almost surely to β j as n -→ +∞.

They have found a necessary condition for the system to be balanced, that is:

α(C) ≤ β(S(C)), β(S) ≤ α(C(S)) ; C ⊆ C, S ⊆ S. (3.1)
Also, they provided the following conjecture that is, a sufficient condition for ergodicity (existence of matching rates),

α(C) < β(S(C)), β(S) < α(C(S)) ; C ⊂ C, C = C, S ⊂ S, S = S. (3.2)
They have studied specific models such as, 'N' model, (respectively 'W' model) (i.e., the structure of the model is of the form 'N' (respectively 'W') graph) and an almost complete graph case (in which each server type can be matched to all except at most one customer type and vice versa). For these, they proved the Conjecture (3.2) above, solved the balance equations and obtained the matching rates. However, they studied the ergodicity for the Adan and Weiss [1] have considered a bipartite matching model in which multi-type customer multi-type server models take into account the special needs of customers as well as the aptitudes and capabilities of the servers. Through the overlap of the client and server subsets, the main interest is in the ability of providing individually tailored service while still allowing for cooperation and pooling of the servers. The Markovian model suggested in [START_REF] Caldentey | FCFS infinite bipartite matching of servers and customers[END_REF] to describe the FCFS infinite matching turns out to be intractable in general, and could therefore not be used to prove the conjecture in general or to calculate the rates. Also, they have solved the balance conditions (3.1) by an explicit product form stationary distribution.

Further, they have given some examples and demonstrated the calculation of the matching rates for some special system graphs.

Adan & al. [START_REF] Adan | Reversibility and further properties of the FCFM Bipartite matching model[END_REF] have proved the fundamental structure of the model in the following three steps:

• Derive a Loynes' scheme, which enables to get to stationarity through sample path dynamics, and to prove the existence of a unique FCFS matching over Z and not solely for N.

• Define a pathwise transformation in which they interchanged the positions of the two items in a matched pair, and they proved the dynamic "reversibility" of the model under this transformation.

• Construct "primitive" Markov chains whose product form stationary distributions are obtained directly from the dynamic reversibility. Using these as building blocks, they have drived product form stationary distributions for multiple 'natural' Markov chains associated with the model, and they computed various non-trivial performance measures as a by-product.

They illustrated these results for the 'NN' model that was described in [START_REF] Caldentey | FCFS infinite bipartite matching of servers and customers[END_REF], and that couldn't be fully analyzed.

They used the following reversibility result: starting from two independent i.i.d. sequences over Z with FCFS matching between them, and performing the exchange transformation on all the links, they obtained two sequences of exchanged customers and servers and matching between them. It is then true that the sequences are again independent i.i.d., and the matching between them is FCFS in the reversed time direction.

Adan and Weiss [START_REF] Adan | A skill based parallel service system under FCFS-ALIS -steady state, overloads, and abandonments[END_REF] have considered a queueing system with J parallel servers S = {m 1 , • • • , m J } (fixed set of server), and with customer types C = {a, b, c, • • • }. A bipartite graph G describes which pairs of server-customer types are compatible. Further, they considered FCFS-ALIS policy: A server always picks the first, longest waiting compatible customer, and a customer is always assigned to the longest idle compatible server. ALIS is the best way to equalize the efforts of the servers, and thus it encourages diligent service.

Assume that arrivals are Poisson and service is exponential. Customers of type c arrive at the system in independent Poisson streams with rates λ c , c ∈ C. Service times of server m j are independent and exponentially distributed with rate µ m j , j ∈ S. Note that service durations of customers depend on the server providing the service, and not on the customer type. Also, they calculated fluid limits of the system under overload, to show that a local steady state exists. They distinguished the case of complete resource pooling when all the customers are served at the same rate by the pooled servers, and the case when the system has a unique decomposition into subsets of customer types, each of which is served at its rate by a pooled subset of the servers. Finally, they discussed the possible behavior of the system with generally distributed abandonments, under many server scaling.

Extended Bipartite Matching model (EBM)

In [START_REF] Bušić | Stability of the bipartite matching model[END_REF], the settings of [START_REF] Caldentey | FCFS infinite bipartite matching of servers and customers[END_REF]1] are generalized to more general service disciplines (termed 'matching policies' in this context), and necessary and sufficient conditions for the stability of the system are introduced, which are functions of the compatibility graph and of the matching policy. Define the following condition on µ, see conditions (3.2) :

µ C (U ) < µ S (S(U )), ∀ U ⊂ C µ S (V ) < µ C (C(V )), ∀ V ⊂ S. (3.3)
The above conditions are then shown necessary and sufficient for the stability of the system for various graph geometries and have a natural interpretation. Let µ C and µ S be the marginals of the arrival probability µ. Customers from U need to be matched with servers from S(U ). The first line in (3.3) asks for strictly more servers in average from S(U ) than customers from U . The second line has a dual interpretation.

In other words, the measure µ is not of the form µ C ⊗ µ S . Instead, the arrival scenario is characterized by a subset F ⊂ C × S representing the possible arrivals of couples, and a measure µ on C × S having support F . The system is then called the Extended Bipartite Matching model (EBM, for short), and suits applications in which independence between the classes of the customers and servers entering simultaneously cannot be assumed. In the applications to organ transplants and blood transfusions, this extension of the settings of the BM is justified by the possible correlations between the blood types of the arriving couples, who may be parents of one another. Also, in [START_REF] Bušić | Stability of the bipartite matching model[END_REF] the authors have proven the following results:

• Sufficient conditions are obtained, under which any admissible matching policy can make the system stable,

• For the 'NN' model, the MS policy and some priority policies do not have a maximal stability region -in the sense that the conditions (3.3) are not sufficient for stability.

• For any bipartite graph, the ML policy has a maximal stability region.

However, the maximality of FCFS is left as an open problem.

Moyal & al. [START_REF] Moyal | Loynes construction for the Extended bipartite matching[END_REF] have found an explicit construction of the stationary state of Extended Bipartite Matching (EBM) models as defined in [START_REF] Bušić | Stability of the bipartite matching model[END_REF]. They used a Loynes-type backward scheme allowing to show the existence and uniqueness of a bi-infinite perfect matching under various conditions, for a large class of matching policies and of bipartite matching structures.

General Matching model (GM)

To model concrete systems, the need then arose to extend these different above models. Indeed, in many applications, the assumption of pairwise arrivals may appear somewhat artificial, and it is more realistic to assume that arrivals are simple. Also, all the aforementioned references assume that the compatibility graph is bipartite, namely, there are easily identifiable classes of servers and classes of customers, whatever these mean: donors/receivers, houses/applicants, jobs/applicants, and so on. However, in many cases, the context requires that the compatibility graph take a general (i.e., not necessarily bipartite) form. For instance, in dating websites, it is a priori not possible to split items into two sets of classes (customers and servers) with no possible matches within those sets. Similarly, in kidney exchange programs, intra-incompatible couples donor/receiver enters the system, looking for a compatible couple to perform a 'crossed' transplant. Then, it is convenient to represent couples donor/receiver as single items, and compatibility between couples means that a kidney exchange can be performed between the two couples (the donor of the first couple can give to the receiver of the second, and the donor of the second can give to the receiver of the first). In particular, if one considers blood types as a primary compatibility criterion, the compatibility graph between couples is naturally non-bipartite.

Motivated by these above observations, a variant model was introduced in [START_REF] Mairesse | Stability of the stochastc matching model[END_REF], in which items arrive one by one and the compatibility graph is general, i.e., not necessarily bipartite: specifically, in this so-called General Matching model (GM for short), its a particular case of the extended matching model (EBM), it has a queueing model flavor, with the crucial specificity that items play the roles of both customers and servers. Then, an incoming item is either immediately matched, if there is a compatible item in the line, or else stored in a buffer. It is the role of the matching policy Φ to determine the match of the incoming item in case of a multiple choice. Then, the two matched items immediately leave the system forever. Indeed, consider a matching model with a graph (V, E) and sequence of arriving Given a connected graph G = (V, E), and a matching policy Φ. Let µ be a probability measure on V, they defined the following conditions on µ :

items (v n ) n . Let Ṽ be a disjoint
NCOND(G) : {µ ∈ M (V) ; µ(U ) < µ(E(U )), ∀ U ⊂ V} . (3.4)
positive recurrent.

Moyal and Perry [START_REF] Moyal | On the instability of matching queues[END_REF] have studied the interesting feature of the fluid limits that is to obtain their dynamics determined by the stationary distribution of a "fast" CTMC. Specifically, if the fluid queue associated with one of the nodes is positive, then the relevant time scale for this queue is slower than the time scale for the fluid queues that are null. In the limit, the effect of the "fast" (i.e., null) queues on the evolution of the positive fluid queues are averaged-out instantaneously, a phenomenon known as a stochastic averaging principle (AP) in the literature. See [START_REF] Perry | An ODE for an overloaded X model involving a stochastic averaging principle[END_REF][START_REF] Perry | A fluid limit for an overloaded X model via a stochastic averaging principle[END_REF] and the references therein, as well as [START_REF] Luo | Staffing and control of instant messaging contact centers[END_REF][START_REF] Wu | Management of a shared-spectrum network in wireless communications[END_REF] for recent examples of fast averaging in queueing networks.

Also, in [START_REF] Moyal | On the instability of matching queues[END_REF] was shown a necessary condition for stability of a matching queue: for any matching graph G,

NCOND C (G) := λ ∈ (R ++ ) |V| : λI < λE(I) for all I ∈ I(G) . (3.5)
That condition can be thought of as an analog to the usual traffic condition for traditional queueing networks see equation (3.4), and it is thus natural to study whether it is also sufficient.

Except for a particular class of graphs, there always exists a matching policy rendering the stability region strictly smaller than the set of arrival intensities satisfying NCOND C and they are showing explicitly, via fluid-limit arguments, that the stability regions of two basic models pendant graph and 5-cycle graph depicted in Figure 3.3 is strictly included in NCOND C . They generalized this result to any graph G that is not complete p-partite there always exists a policy of the strict priority type that does not have a maximal stability region, and that the 'Uniform' random policy (natural in the case where no information is available to the entering items on the state of the system) never has a maximal stability region. Definition 3.1. [START_REF] Moyal | On the instability of matching queues[END_REF] A connected matching structure S is said to be,

• matching-stable if NCOND C (S) is non-empty and all admissible matching policies on S are maximal;

• matching-utable nstable if the set NCOND C (S) is empty.

Let G 7 denote the set of all connected graphs inducing an odd cycle of size 7 or more, but no pendant graph and no 5-cycle, and let G c 7 denote its complement in the set of connected graphs. Also, a result was proven in [START_REF] Moyal | On the instability of matching queues[END_REF] that:

• the pendant and 5-cycle graphs depicted in Figure 3.3, it is shown that those graphs are matching-unstable, (i.e., never maximal).

• The only matching-stable graphs in G c 7 are separable of order 3 or more. Variants of the GM model to the case of graphical systems with reneging are investigated, respectively in [START_REF] Gurvich | On the dynamic control of matching queues[END_REF][START_REF] Nazari | Optimal control of general dynamic matching systems[END_REF][START_REF] Rahme | A stochastic matching models on hypergraphs[END_REF]] and [START_REF] Jonckheere | Generalized Max-Weight policies in stochastic matching[END_REF] (see also [START_REF] Boxma | A new look at organ transplantation models and double matching queues[END_REF]).

Optimizations of the matching model

In another line of research, such stochastic matching architectures are addressed from the point of view of stochastic optimization in [START_REF] Buke | Fluid and diffusion approximations of probabilistic matching systems[END_REF], [START_REF] Gurvich | On the dynamic control of matching queues[END_REF] and [START_REF] Nazari | Optimal control of general dynamic matching systems[END_REF], among others.

Buke and Chen [START_REF] Buke | Fluid and diffusion approximations of probabilistic matching systems[END_REF] have focused on the infinite-horizon average-cost optimal control problem. In which, they considered a control policy determines which are matched at each time by considering a discrete-time bipartite matching model with random arrivals of units of supply and demand that can wait in queues located at the nodes in the network. For a parameterized family of models in which the network load approaches capacity, a new matching policy for the relaxation admits a closed-form expression is shown to be approximately optimal, with bounded regret, even though the average cost grows without bound.

Gurvich and Ward [START_REF] Gurvich | On the dynamic control of matching queues[END_REF] have considered a model in which each item arrive in a dedicated queue, and wait to be matched with items that exist in other queues (possibly multiple). Once a decision has been made to match, the match itself is instantaneous and the corresponding items leave the system. Upon arrival, an item may find several possible matching, in this cases, an exsisting controller must decide which matchings to execute given multiple options. They considered the problem of minimizing finite-horizon cumulative holding costs.

In principle, the controller may choose to wait until some "inventory" of items builds up to facilitate more profitable matches in the future. Nazari and Stolyar [START_REF] Nazari | Optimal control of general dynamic matching systems[END_REF] have introduced an algorithm that is a variant of the "Primaldual algorithm", allowing to achieve stability if this is feasible at all, for a very large class of models. The proposed algorithm furthermore optimizes utility functions that are convex functions of the average matching rates. [START_REF] Gurvich | On the dynamic control of matching queues[END_REF] and [START_REF] Nazari | Optimal control of general dynamic matching systems[END_REF] allow idling policies, i.e., scheduling algorithms allowing to perform no matching at all despite the presence of matchable items in the system, to wait for more profitable future matches. Allowing idling policy makes sense in applications such as assemble-to-order systems, advertisement or operations scheduling, but is much less suitable to kidney transplant networks, in which case the practitioners always perform a transplant whenever one is possible.

Other extensions of matching models

Specific comparison results concerning single-server queueing systems with impatient customers are also provided in [START_REF]Comparison of service disciplines in real-time queues[END_REF] and [START_REF]On queues with impatience: stability, and the optimality of Earliest Deadline First[END_REF]. Moreover, it is well known since the seminal work of Propp and Wilson [START_REF] Propp | Exact sampling with coupled Markov chains and applications to stastical mechanics[END_REF], that coupling from the past algorithms, which mostly use backward coupling convergence, provides a powerful tool for simulating in many cases (monotonicity, stochastic bounds of Markov chains) the steady state of the system. Along these lines, the above is devoted to the explicit construction of a stationary queue with S r servers (S r ≥ 1) and impatient customers, by a scheme à la Loynes. Models with impatience (or abandonment, reneging) have been introduced in the queueing literature to represent a strong real-time constraint on the system: the requests have a due date, before which their treatment must be initiated, or completed. Specifically, assume hereafter that any incoming customer is either served if a server becomes available before its deadline or else eliminated forever once the deadline has elapsed. Observe that a loss system of S r systems (i.e., there is no waiting room, so the incoming customers are either served provided that a server is immediately available or immediately lost otherwise) is a particular case of the present model, for identically null patience. There are S r servers obeying the First Come, First Served (FCFS) rule to serve impatient customers, and the sequences of interarrival times, service times, and patience times of the customers are assumed stationary and ergodic, but not necessarily independent.

Buke and Chen [START_REF] Buke | Stabilizing Policies for Probabilistic Matching Systems[END_REF] have introduced a new queueing model, called probabilistic matching system, to model the traffic in web portals. This queueing model consists of two user classes, in which users wait in the system to match a candidate from the other class, instead of accessing a resource. They have stabilized four admissible matching policies for the probabilistic matching systems which are:

1-the simple threshold policy, 2-accept-the-shortest-queue policy, 3-functional threshold policy, 4-the one-sided threshold policy. This study of [START_REF] Buke | Stabilizing Policies for Probabilistic Matching Systems[END_REF] is followed by [START_REF] Buke | Fluid and diffusion approximations of probabilistic matching systems[END_REF] which have proposed approximation methods and analyzed its properties based on fluid and diffusion limits. They performed numerical experiments to gain insight into probabilistic matching systems. Also, they showed that some performance measures are insensitive to the matching probability, agreeing with the existing results.

Adan & al. [START_REF] Adan | FCFS parallel service systems and matching models[END_REF] have considered three parallel service models in which customers of several types are served by several types of servers subject to a bipartite graph, and the service policy is First Come, First Served. Two of the models have a fixed set of servers.

• The first is a queueing model in which arriving customers are assigned to the longest idling compatible server if available, or else queue up in a single queue, and servers that become available pick the longest waiting compatible customer as studied in [START_REF] Adan | A skill based parallel service system under FCFS-ALIS -steady state, overloads, and abandonments[END_REF].

• The second is a redundancy service model where arriving customers split into copies that queue up at all the compatible servers, and are served in each queue on FCFS basis, and leave the system when the first copy completes service.

• The third model is a matching queueing model with a random stream of arriving servers. Arriving customers queue in a single queue and arriving servers match with the first compatible customer and leave immediately with the customer, or they leave without a customer.

They studied the relations between these models, and showed that they are closely related to the FCFS infinite bipartite matching model, in which two infinite sequences of customers and servers of several types are matched FCFS according to a bipartite compatibility graph.

They also introduced a directed bipartite matching model in which they embed the queueing systems. This leads to a generalization of Burke's theorem to parallel service systems.

Problem statement and positioning

A stochastic matching model, as we said before, is a system of components and each of these components could have more than one state of functioning.

The main purpose of this thesis is devoted to three contexts: First, we study the long-run stability of stochastic matching models, in the sense defined above, on a hypergraphical compatibility matching structure generalizing the approach of [START_REF] Mairesse | Stability of the stochastc matching model[END_REF] to hypergraphs instead of graphs. By doing so, the two closest references to the present work are [START_REF] Gurvich | On the dynamic control of matching queues[END_REF] and [START_REF] Nazari | Optimal control of general dynamic matching systems[END_REF]: in both cases, a general matching model is addressed on a hypergraphical matching structure (notice that [START_REF] Nazari | Optimal control of general dynamic matching systems[END_REF] also allows matchings including several items of the same class). The first reference addresses continuous-time models; the second considers discrete-time models, however, most of the results therein can easily be extended to the continuous-time settings. In [START_REF] Gurvich | On the dynamic control of matching queues[END_REF] a matching control is introduced, that asymptotically minimizes the holding cost of items in an unstable system (we justify the instability of such systems under the assumptions of [START_REF] Gurvich | On the dynamic control of matching queues[END_REF] in Remark 4.3). In the present thesis all the matching policies we consider are non-idling, i.e., entering items are always matched right away if this is possible at all. Thus, the model studied in Chapter 4 is a special case of the model studied in [START_REF] Nazari | Optimal control of general dynamic matching systems[END_REF], for simple arrivals, no same-class matchings, and non-idling matching policies.

Secondly, we showed how several stability results of [START_REF] Mairesse | Stability of the stochastc matching model[END_REF][START_REF] Moyal | A product form and a sub-additive theorem for the general stochastic matching model[END_REF][START_REF] Jonckheere | Generalized Max-Weight policies in stochastic matching[END_REF] can be generalized to the case of a multigraphical matching structure which is motivated again by concrete applications, among which dating websites and peer-to-peer interfaces, it is natural to assume that items of the same class can be matched together. Hence, the need to generalize the previous line of research to the case where the matching architecture is a multigraph (a graph admitting self-loops, that is, edges connecting nodes to themselves), rather than just a graph.

On other hand, we study in continuous-time different examples of multigraph G = (V, E) and hypergraph H = (V, H) corresponding respectively matching queues (G, Φ, λ) C and (H, Φ, λ) C . We deduce the precise stability regions of the corresponding stochastic matching models using the fluid limit techniques.

Finally, we present an application for organ transplantation of a stochastic model on hypergraphs, in which we compare the behavior in the long-run stability of the model of complete 3-uniform hypergraphs matching (three-by-three) with the model of complete 3partite graph matching (two-by-two). Then, according to the distribution of the items, we deduce what is the best matching procedure between two-by-two and three-by-three matchings.

Introduction

In the Stochastic Matching model (introduced in the bipartite case by Caldentey and al. in [START_REF] Caldentey | FCFS infinite bipartite matching of servers and customers[END_REF] and generalized by Mairesse and Moyal in [START_REF] Mairesse | Stability of the stochastc matching model[END_REF]), items enter the system randomly and may be matched or not according to their classes. The compatibility between classes is given by a fixed matching structure. In this chapter, we study the long-run stability of stochastic matching models, in the sense defined above, on a hypergraphical compatibility matching structure.

Several applications should naturally incorporate the possibility of matching items by groups of more than two. Let us exemplify this on a concrete example: in organ transplants, (in)-compatibility between givers and receivers are given by a variety of factors, and mostly by blood types and immunological factors. In kidney exchange programs, items represent intra-incompatible couples (A, B) (e.g., a patient A waiting for a transplant and B a parent of his/hers, incompatible with A for a potential organ donation), entering a system to find another intra-incompatible couple (A , B ) that is compatible with it, in the sense that A can receive an organ from B and A can receive from B. Then the ability of such a system to accommodate all requests and to maximize the number of successful transplants and avoid congestion, is translated into the positive recurrence of a stochastic process representing the stochastic system over time. Then if we view the items as the couples, and translate the "cross-compatibility" (i.e., A can receive from B and A can receive from B) into the existence of an edge between node (A, B) and node (A , B ), such a system is a typical application of the GM introduced in [START_REF] Mairesse | Stability of the stochastc matching model[END_REF].

Let us now consider the case where such exchanges (A, B) ↔ (A , B ) and (A , B ) ↔ (A , B ) cannot be realized, but A can receive from B , A can receive from B and A can receive from B. Then it is natural to consider the possibility of executing the three transplants contemporarily, i.e., to match the triplet (A, B), (A , B ) and (A , B ) altogether. In several countries including the U.S., such "exchanges" by groups of 3 (or more) are allowed, which raises the issue of maximizing "matchings" that do not coincide with sets of edges, but of sets of subsets of nodes of cardinality 3 or more. Hence the need to consider matching models on compatibility matching structures that are hypergraphs rather than graphs, i.e., a set of nodes V equipped with a set of subsets of V of cardinality 3 or more.

The hypergraphical stochastic matching model addressed in this chapter is formally defined as follows: items enter the system by single arrivals and get matched by groups of 2 or more, following compatibilities that are represented by a given hypergraph. A matching policy determines the matchings to be executed in the case of a multiple-choice, and the unmatched items are stored in a buffer, waiting for a future match.

At the border between discrete mathematics and probability theory, the main scientific aim of this chapter is to study this widely applicable class of models. In the first step, addressing the crucial question of stability of the system will lead us to study the structural properties of hypergraphs (connectivity, independent sets, rank, anti-rank, degree, size of the transversals, existence of cycles, and so on.) In a second step, we will address the weak approximation of the natural Markov process of the model, to better apprehend its main characteristics in steady state, its long-run simulation, and possibly, the estimation of its parameters.

This chapter is organized as follows: we start in Section 4.1 by providing necessary conditions of stability for the present class of systems: as will be developed therein, and unlike the particular case of the GM on graphs (see [START_REF] Mairesse | Stability of the stochastc matching model[END_REF]), for which a natural necessary condition could be obtained, we introduce various necessary conditions that depend on distinct geometrical properties of the considered hypergraphs. We then deduce from this, classes of hypergraphs for which the corresponding matching model cannot be stable, see Section 4.2.

Finally, in Section 4.3, we provide the precise stability region in the particular cases where the compatibility hypergraph is complete 3-uniform, complete k-partite 3-uniform and then complete up to a partition of its hyperedges (see the precise definitions of these objects below). We conclude and discuss this chapter in Section 4.4.

Throughout this chapter, let us consider that the matching structure S be a hypergraph H = (V, H). Recall that V n is an item which enters the system from the measure µ on V at time n and H(k) is the realized matching at time k. and with some abuse, denote A n (i) = A n ({i}) and M n (H) = M n ({H}) for any i ∈ V and H ∈ H. Observe that the following key relation holds for all B ⊂ V,

Necessary conditions of stability

X n (B) = A n (B) - H∈H |H ∩ B| M n (H) ≥ 0, n ∈ N, (4.1)
since the number of items of classes in B at any time n is precisely the number of arrivals of such items up to time n, minus the number of these items that leave the system upon each matching of a hyperedge that intersects with B.

General conditions

We start by introducing several 'universal' stability conditions. Fix a hypergraph H = (V, H) throughout the section.

Definition 4.1. We say that I ⊂ V is an independent set of H if I does not include any hyperedge of H, i.e, for any H ∈ H, H ∩ Ī = ∅. We recall that I(H) be the set of all independent sets of H.

Let us define for any µ ∈ M (V), and any B ⊂ V, the set

L µ (B) = argmin {µ(j) : j ∈ B} , B ⊂ V. (4.2)
To clarify the exposition of the Lemma 4.1 (stated below), we need to introduce the following notion, Definition 4.2. For any µ ∈ M (V) we say that the independent set I ∈ I(H) is µ-minimal if the intersection of any hyperedge H ∈ H with I is either empty, or reduced to a singleton {v H } that is such that:

• v H is of degree 1, i.e., H is the only hyperedge v H belongs to;

• L µ (H) = {v H }, i.e., v H is the only minimum of µ over the set H.

An independent set I ∈ I(H) that is not µ-minimal is said non-µ-minimal. We let I µ (H) be the set of µ-minimal independent sets of H, and I µ (H) be the set of non-µ-minimal independent sets of H, that is, the complement set of I µ (H) in I(H).

In other words, a µ-minimal independent sets gathers nodes that are the only minimum of µ over the only hyperedge they belong to. Notice that the collection I µ (H) can be empty.

k j ∈ L µ (H j ) for all j, A n (I) = m j=1 |H j ∩ I|A n (k j ). (4.3)
Proof. First, it is clear that if I ∈ I µ (H), then m ≥ p and the mapping

ϕ : {j ∈ 1, m : I ∩ H j = ∅} -→ 1, p j -→ i : L µ (H j ) = H j ∩ I = {v i } (4.4)
is bijective. Thus we have a.s. for all n,

A n (I) = m j=1 A n (v ϕ(j) ) = j∈ 1,m : H j ∩I =∅ |H j ∩ I|A n (v ϕ(j) ) = m j=1 |H j ∩ I|A n (k j ).
Let us now assume that I ∈ I µ (H). Then,

• If for some hyperedge H j is such that |H j ∩ I| ≥ 2, then upon each arrival of an element of class k j , the right-hand side of (4.3) increases by |H j ∩ I| while the lefthand side increases by 1 if k j ∈ I, or 0 else;

• If for some hyperedge H j intersecting with I, there exists k j ∈ L µ (H j ) ∩ Ī, then upon each arrival of a class k j -item the right-hand-side of (4.3) increases while the left-hand side does not;

• Finally, if for all j ∈ 1, m , |H j ∩ I| ≤ 1 and for all j such that |H j ∩ I| = 1, L µ (H j ) = {v ϕ(j) } (defining again ϕ by (4.4)), then if ϕ(j) = ϕ(l) for some l = j, upon each arrival of a class v ϕ(j) -item, the right-hand side of (4.3) increases by 2 while the left-hand side increases by 1.

In all cases, (4.3) cannot hold for all n, which concludes the proof. Now define the following set of measures,

N 1 (H) = µ ∈ M (V) : for all I ∈ I µ (H), µ(I) < H∈H |H ∩ I| min k∈H µ(k) .
We have the following result, Proposition 4.1. For any connected hypergraph H and any admissible matching policy Φ,

STAB(H, Φ) ⊂ N 1 (H).
Proof. Fix H = (V, H) and an admissible policy Φ. Denote by H 1 , ..., H m the hyperedges of H. Suppose that µ ∈ M (V) is such that there exists an independent set

I ∈ I µ (H) such that µ(I) > H∈H |H ∩ I| min k∈H µ(k). (4.5)
For any i ∈ 1, m and any

k i ∈ L µ (H i ) we have that M n (H i ) ≤ min k∈H i A n (k) ≤ A n (k i ) , n ≥ 0.
Thus, from the equality in (4.1), for any k 1 , ..., k m such that k i ∈ L µ (H i ) for all i, we have that

X n (I) n ≥ A n (I) n - m i=1 |H i ∩ I| A n (k i ) n , n ≥ 1. (4.6)
Applying the SLLN to the right-hand side of (4.6) implies that for any such k 1 , ..., k m ,

lim sup n X n (I) n ≥ µ(I) - m i=1 |H i ∩ I| µ (k i ) = µ(I) - H∈H |H ∩ I| min k∈H µ (k) > 0,
implying that X n (I) goes a.s. to infinity and thereby (as

X n = [W n ] for all n), the transience of {W n ; n ∈ N}.
Assume now that µ is such that for some independent set I ∈ I µ (H), an equality holds in (4.5). Then, for any k 1 , ..., k m such that k j ∈ L µ (H j ) for all j, the Markov chain {Y n ; n ∈ N} defined as

Y n = A n (I) - m j=1 |H j ∩ B| A n (k j ) , n ∈ N,
is a random walk with drift 0 that is different from the identically null process, in view of Lemma 4.1. Hence {Y n ; n ∈ N} is null recurrent. Would the chain {W n ; n ∈ N} be positive recurrent, the sequence {X n ; n ∈ N} would visit the state 0 infinitely often, with inter-passage time at 0 of finite expectation. Thus from (4.6), the sequence {Y n ; n ∈ N} would be positive recurrent, an absurdity. This concludes the proof.

Define the following sets of measures,

N + 1 (H) = µ ∈ M (V) : ∀I ∈ I(H), µ(I) < H∈H |H ∩ I| min k∈H∩ Ī µ(k) ; N ++ 1 (H) = µ ∈ M (V) : ∀B ⊂ V, µ(B) ≤ H∈H |H ∩ B| min k∈H µ(k) .
We have the following result, Corollary 4.1. For any connected hypergraph H and any admissible matching policy Φ,

STAB(H, Φ) ⊂ N + 1 (H) ∩ N ++ 1 (H).
Proof. We just show that N 1 (H) is included in

N + 1 (H) ∩ N ++ 1 (H). Set again H = {H 1 , ..., H m } and fix µ ∈ N 1 (H).
To show that µ ∈ N + 1 (H), first observe that for any independent set I = {v 1 , ..., v p } ∈ I µ (H), for any hyperedge H j intersecting with I, we have that min k∈H j µ(k) = µ(v ϕ(j) ) < min k∈H j ∩ Ī µ(k). Therefore, To see this, it suffices to observe that for any independent set I ∈ I µ (H), recalling (4.4),

µ(I) = p i=1 µ(v i ) = m j=1 |H j ∩ I|µ(v ϕ(j) ) < H∈H |H ∩ I| min k∈H∩ Ī µ(k),
µ(I) = m j=1 µ(v ϕ(j) ) = j∈ 1,m : H j ∩I =∅ |H j ∩I|µ(v ϕ(j) ) = m j=1 |H j ∩I|µ(k j ) = H∈H |H ∩I| min k∈H µ(k),
hence (4.7). Now fix B, a subset of V that is not an independent set of H. Then, we construct by induction the family of sets B := B 0 ⊃ B 1 ⊃ B 2 ⊃ ... ⊃ B r , where r is properly defined below, as follows: for any i ≥ 0, if B i is not an independent set of I(H), then we take an arbitrary hyperedge H j i ∈ H such that H j i ⊂ B i , and set B i+1 = B i \ {k i }, for an arbitrary

k i ∈ L µ (H j i ).
Then, there exists an integer r ≤ |B| -1 such that B r is an independent set of I(H), and we stop the construction at this point. Observe that for any i ∈ 0, r -1 ,

µ(B i+1 ) ≤ H∈H |H ∩ B i+1 | min k∈H µ(k) =⇒ µ(B i ) ≤ H∈H |H ∩ B i | min k∈H µ(k). (4.8)
To see this, fix i and suppose that the left-hand side of the above holds true. Then, we have

µ(B i ) = µ(B i+1 ) + µ(k i ), (4.9)
and on the other hand,

H∈H |H ∩ B i | min k∈H µ(k) = H∈H(k i ) |H ∩ B i | min k∈H µ(k) + H∈H(k i ) |H ∩ B i | min k∈H µ(k) = H∈H(k i ) |H ∩ B i+1 | min k∈H µ(k) + H∈H(k i ) (|H ∩ B i+1 | + 1) min k∈H µ(k) = H∈H |H ∩ B i+1 | min k∈H µ(k) + H∈H(k i ) µ(k H ), (4.10)
where for any H ∈ H(k i ), k H is an arbitrary element of L µ (H). But µ(k i ) is less or equal than the second term of the latter sum because µ(k i ) = µ(k H i ), and we assumed that µ(B i+1 ) is less than the first term µ(B i+1 ) ≤ H∈H |H ∩ B i+1 | min k∈H µ(k) . This completes the proof of (4.8) in view of (4.10). To conclude, as B r ∈ I(H) and in view of This completes the proof. where the inequality above is an equality whenever each element of E(I) shares an edge with a single element of I, and else a strong inequality. Thus µ ∈ N ++ 1 (H). In fact, it is necessarily the case that NCOND(H) ⊂ N 1 (H) because if it was not true, there would exist in particular a µ ∈ N 1 (H) ∩ NCOND(H), making the system (H, ML, µ) unstable (in view of Proposition 4.1) despite the fact that µ ∈ NCOND(H), a contradiction to Theorem 2 in [START_REF] Mairesse | Stability of the stochastc matching model[END_REF]. Observe however that NCOND(H) = N 1 (H) in general. To see this, consider the case where H is the cycle of size 5, 1 -2 -3 -4 -5 -1. For a small enough > 0, set

           µ(1) = 1 2 -3 4 ; µ(2) = µ(5) = 1 4 -8 ; µ(3) = 4 5 ; µ(4) = 5 .
It is then easily checked that µ ∈ N 1 (H). However µ ∈ NCOND(H), since the independent set I = {1, 3} is such that

µ(I) = 1 2 + 20 > 1 2 - 20 = µ({2, 4, 5}) = µ(E(I)).
As a conclusion, if H is a graph the necessary condition "µ ∈ NCOND(H)" is stronger than the necessary condition "µ ∈ N 1 (H)".

Let us now define the following set of measures,

N 2 (H) = µ ∈ M (V) : ∀T ∈ T (H) , µ(T ) > 1 r(H) .
We also have that Proposition 4.2. For any connected hypergraph H and any admissible matching policy Φ,

STAB(H, Φ) ⊂ N 2 (H).
Proof. Suppose that there exists a transversal T ∈ T (H) such that µ(T ) ≤ 1 r(H) . As each match contains at least one element whose class is an element of T , at any time the overall number of completed matches cannot exceed the number of arrivals of elements whose class belongs to T , in other words M n (H) ≤ A n (T ) for all n. Thus, for all n we have that

X n (V) n ≥ 1 n (A n (V) -r(H)M n (H)) ≥ 1 n (A n (V) -r(H)A n (T )) .
Taking n to infinity in the above yields

lim sup n X n (V) n ≥ 1 -r(H)µ(T ),
and we conclude as in the previous proof.

Remark 4.2. As an immediate consequence of Proposition 4.2, if H = (V, H) is of order q, and such that τ (H) ≤ q r(H) , then STAB(H, Φ) does not contain the uniform measure µ U = (1/q, ..., 1/q) on V, in other words the model (H, Φ, µ U ) is unstable for any Φ. Indeed, for any minimal transversal T of H we have that

µ U (T ) = τ (H) q ≤ 1 r(H)
.

We now introduce two necessary conditions of stability based on the anti-rank of the considered hypergraph. We first introduce the following sets of measures,

N + 3 (H) = µ ∈ M (V) : ∀i ∈ V, µ(i) ≤ 1 a(H) ; (4.11)
N - 3 (H) = µ ∈ M (V) : ∀i ∈ V, µ(i) < 1 a(H) . (4.12)
We have the following, If the hypergraph H = (V, H) is r-uniform (i.e., a(H) = r(H) = r) we have that

STAB(H, Φ) ⊂ N - 3 (H). (4.14)
in other words the model (H, Φ, µ) cannot be stable unless µ(i) < 1/r for any i ∈ V.

Proof. To prove the first statement, we argue again by contradiction. Suppose that µ(i 0 ) > 1 a(H) for some node i 0 . As the function

   R + -→ R + x -→ r(H)-a(H)+x xa(H)
strictly decreases to 1 a , there exists x 0 > 0 such that

µ(i 0 ) > r(H) -a(H) + x 0 x 0 a(H) . (4.15)
Then, applying the inequality in (4.1) to B ≡ V \ {i 0 }, we readily obtain that a.s. for all n, r(H)

+ x 0 a(H) A n (V \ {i 0 }) ≥ r(H) + x 0 a(H)   H∈H(i 0 ) |H -1| M n (H) + H∈H(i 0 ) |H| M n (H)   ≥ r(H) + x 0 - r(H) + x 0 a(H) M n (H(i 0 )) + (r(H) + x 0 )M n H(i 0 ) . (4.16)
Likewise, applying the equality of (4.1) to {i 0 } and then V \ {i 0 } also yields to

X n (V \ {i 0 }) + x 0 + 1 - r(H) + x 0 a(H) X n (i 0 ) = A n (V \ {i 0 }) - H∈H(i 0 ) |H -1| M n (H) - H∈H(i 0 ) |H| M n (H) + x 0 + 1 - r(H) + x 0 a(H) (A n (i 0 ) -M n (H(i 0 ))) > A n (V \ {i 0 }) + x 0 + 1 - r(H) + x 0 a(H) A n (i 0 ) -r(H) + x 0 - r(H) + x 0 a(H) M n (H(i 0 )) -(r(H) + x 0 )M n H(i 0 ) .
Combining this with (4.16), implies that a.s. for all n,

X n (V) + x 0 - r(H) + x 0 a(H) X n (i 0 ) > 1 - r(H) + x 0 a(H) A n (V) + x 0 A n (i 0 ).
Therefore we have that lim sup It remains to check that in the case where the hypergraph is r-uniform, the model cannot be stable whenever µ(i 0 ) ≥ 1 a(H) = 1 r for some i 0 ∈ V. For this, notice that, as r(H) = a(H) = r a weak inequality holds true in (4.15) for any x 0 > 0. Then, it readily follows from (4.17) that for any x 0 , lim sup

n 1 n X n (V) + x 0 - r(H) + x 0 a(H) X n (i 0 ) ≥ 1 - r(H) + x 0 a(H) + x 0 µ(i 0 ), (4.17
n 1 n X n (V) + x 0 - r(H) + x 0 a(H) X n (i 0 ) ≥ 0,
and we conclude, as in the proof of Proposition 4.1, that the chain {W n ; n ∈ N} is at best null recurrent. Proof. Let µ ∈ N + 1 (H). Then, considering successively the sets {i} and {j}, as j ∈ H∩ { i} and i ∈ H ∩ { j} we obtain that µ(i) < µ(j) and µ(i) > µ(j), an absurdity.

Non-stabilizable hypergraphs

Stars

First recall that, as for any bipartite graph (see Theorem 2 in [START_REF] Mairesse | Stability of the stochastc matching model[END_REF]), graphical matching models on trees are always unstable. This is true in particular if the matching graph is a "star", i.e., a connected graph in which all but one vertices are of degree one. The following two results can be seen as generalizations of this fact to hypergraphical models, Proposition 4.5. If an r-uniform hypergraph H = (V, H) has transversal number τ (H) = 1, then it is non-stabilizable.

Proof. Fix Φ and µ in STAB(H, Φ). Let T be a transversal of cardinality 1, i.e., T = {i 0 }, where the vertex i 0 belongs to all hyperedges in H. Then from Proposition 4.3, we have that µ(i 0 ) < 1/a(H) = 1/r. However, Proposition 4.2 implies that µ(i 0 ) > 1/r(H) = 1/r, an absurdity.

In other words, any uniform hypergraph whose hyperedges all contain the same node i 0 cannot make the corresponding system stable. Moreover, Proposition 4.6. Suppose that there exists a subset B ⊂ V in the hypergraph H = (V, H) such that:

• all hyperedges of H(B) contain at least one node of degree 1;

• at least one of these nodes of degree 1 lies outside of B.

Then H is non-stabilizable.

Proof. Let k = |H(B)|, i.e., the number of hyperedges intersecting with B. Denote by H 1 , ..., H k these intersecting hyperedges, and for any l ∈ 1, k , by i l ∈ V, a node of degree one belonging to H l . Observe that the nodes i 1 , ..., i k are not necessarily distinct. On the one hand, for any l ∈ 1, k we have that

X n (i l ) = A n (i l ) -M n (H l ).
Thus, applying again the inequality in (4.1) we get that for all n,

A n (B) ≥ k l=1 |H l ∩ B|M n (H l ) = k l=1 |H l ∩ B|(A n (i l ) -X n (i l )). This entails that if µ ∈ N ++ 1 (H), lim sup n→∞ 1 n k l=1 |H l ∩ B|X n (i l ) ≥ k l=1 |H l ∩ B|µ(i l ) -µ(B) ≥ 0.
If the above inequality is strong, then the chain {W n ; n ∈ N} is transient. If the inequality is weak, then as above we can stochastically lower-bound the chain by a zero-drift chain Ỹn ; n ∈ N , defined by

Ỹn = A n (B) - k l=1 |H l ∩ B|A n (i l ) , n ∈ N,
which is not identically null from the assumption that at least one of the nodes i l , l = 1, ..., k

is not an element of B, which concludes the proof.

Example 4.1. Any hypergraph H = (V, H) such that there exist two hyperedges H 1 and

H 2 with H 1 ∩ H 2 = ∅ and two nodes i 1 ∈ H 1 ∩ H 2 , i 2 ∈ H 2 ∩ H 1 and d (i 1 ) = d (i 2 ) = 1 is
non-stabilizable (see Figure 4.2). To see this, take B = H 1 ∩ H 2 in Proposition 4.6.

Remark 4.3 (About the DI condition in [START_REF] Gurvich | On the dynamic control of matching queues[END_REF]). Most results of [START_REF] Gurvich | On the dynamic control of matching queues[END_REF] hold under the Assumption 1 therein, stating that the Dedicated Item DI condition is satisfied; namely, each hyperedge contains an isolated node. The above example shows that any matching model (H, Φ, µ) on a hypergraph H satisfying the DI condition, is unstable for any admissible Φ (the case where H contains a single hyperedge H is trivial).

i 1 i 2 H 2 H 1

r-partite hypergraphs

We now turn to hypergraphical generalizations of bipartite graphs.

Proposition 4.7. Any r-uniform bipartite hypergraph H = (V, H) is non-stabilizable.

Proof. Applying (4.1) successively to V 1 and V 2 readily implies that for all n,

X n (V 1 ) = A n (V 1 ) -M n (H) ≥ 0 and X n (V 2 ) = A n (V 2 ) -(r -1)M n (H) ≥ 0,
and thus

X n (V 1 ) ≥ A n (V 1 ) - 1 r -1 A n (V 2 ).
Then, the usual SLLN-based argument implies that the model cannot be stable unless µ(V 2 ) Example 4.2. The so-called Fano plane is a well-known object in discrete geometry. It is the smallest projective plane, namely, the smallest set of points and lines such that any two points share a line, any two lines intersect at a single point, and on every line lies the same number of points. In the settings of hypergraphs (points being nodes and lines being hyperedges), the Fano plane is thus the smallest uniform hypergraph H in which each pair of nodes belongs to a single hyperedge, and each pair of hyperedges intersects at a single node. It can be checked that H = (V, H) is of order 7, for V = 1, 7 and e.g. H = {{1, 2, 4}, {1, 5, 6}, {1, 3, 7}, {2, 3, 5}, {4, 5, 7}, {4, 3, 6}, {6, 2, 7}} .

≥ (r -1)µ(V 1 ). But as µ(V 1 ) + µ(V 2 ) = 1 we have that µ(V 1 ) ≤ 1 r , hence µ ∈ N 2 (H) since V 1 is a transversal.
Supported by simulations, we conjecture that Fano planes are stabilizable. However, if H = (V, H ) is the subhypergraph defined by H = H\H, where H is an arbitrary hyperedge of H, then it is easily seen that H is a 3-uniform bipartite hypergraph with V 1 = H and V 2 = V\H. So we deduce from Proposition 4.7 that H is non-stabilizable. A Fano plane minus the hyperedge {4, 5, 7} is represented in Figure 4.3.

We know from Theorem 2 in [START_REF] Mairesse | Stability of the stochastc matching model[END_REF] that bipartite graphs are not stabilizable. The next result shows that this can be generalized to r-partite hypergraphs (which generalize bipartite graphs -see Remark 1.2), Proposition 4.8. Any r-partite hypergraph H is non-stabilizable.

Proof. As in the above proof we get that for any i = j and any n,

X n (V j ) = A n (V j ) -M n (H) ≥ 0 and X n (V i ) = A n (V i ) -M n (H) ≥ 0, implying that X n (V i ) ≥ A n (V i )-A n (V j )
, and in turn, that the model cannot be stable unless µ(V i ) ≤ µ(V j ). By symmetry, this implies that µ(V i ) = µ(V j ). As the V i 's are disjoint, we thus have that µ(V i ) = 1/r for all i. Thus, as any V i is a transversal of H, µ is not an element of N 2 (H).

It is well known (see [START_REF] Ph | On Representatives of Subsets[END_REF] for the particular case of graphs, and the general result in [START_REF] Haxell | A condition for matchability in hypergraphs[END_REF]) that Hall's condition is necessary and sufficient for the existence of a perfect matching on H, i.e., a spanning subhypergraph of H in which all nodes have degree 1, in the case where the hypergraph is balanced, i.e., it does not contain any odd strong cycle. It is intuitively clear that the construction of stable stochastic matching models on hypergraphs is somewhat reminiscent of that of perfect matchings on a growing hypergraph that replicates the matching hypergraph a large number of times in the long run (in the case of graphs, see the discussion in Section 7 of [START_REF] Moyal | On the instability of matching queues[END_REF]). This connexion has a simple illustration in the next Proposition, which provides a family of probability measures, naturally including the uniform measure on V, that cannot stabilize a matching model on the hypergraph H unless the latter satisfies Hall's condition. In what follows we denote for any H = (V, H) and any measure µ ∈ M (V), µ min = min {µ(i) : i ∈ V} and µ max = max {µ(i) : i ∈ V} .

(4.18) Proposition 4.9. For any hypergraph H = (V, H) that violates Hall's condition, any matching policy Φ and any µ ∈ M (V) such that

µ min µ max > q(H)+1 2 -1 q(H)+1 2 , (4.19)
the model (H, Φ, µ) is unstable. In particular, (H, Φ, µ U ) is unstable for µ U the uniform distribution on V.

Proof. Fix H, Φ, and a measure µ satisfying (4.19). We first show that µ is monotonic with respect to the counting measure on V, i.e.,

∀E, F ⊂ V, |E| < |F | =⇒ µ(E) < µ(F ). (4.20)
Let E and F be such that |E| < |F |, and let k = |F |. Let also α be a bijection from 1, q(H) to V such that

µ min = µ(α(1)) ≤ µ(α(2)) ≤ ... ≤ µ(α(q(H))) = µ max , (4.21)
in other words (µ(α(1)), µ(α(2)), ..., µ(α(q(H)))) is an ordered (in increasing order) version of the family {µ(i); i ∈ V}. As |E| ≤ k -1 we clearly have

µ(F ) -µ(E) ≥ k i=1 µ(α(i)) - q i=q-k+2 µ(α(i)). (4.22) First, if k ≤ q(H)+1 2 , (4.19) entails that kµ min > (k -1)µ max , whence k i=1 µ(α(i)) - q i=q-k+2 µ(α(i)) ≥ kµ min -(k -1)µ max > 0, (4.23) If k > q(H)+1 2
, then the index sets 1, k and q -k + 2, q intersect precisely on q -k + 2, k . Thus

k i=1 µ(α(i)) - q i=q-k+2 µ(α(i)) = q-k+1 i=1 µ(α(i)) - q i=k+1 µ(α(i)) ≥ (q -k + 1)µ min -(q -k)µ max > 0, (4.24)
where the last inequality follows, as in (4.23), from the fact that q -k + 1 ≤ q(H)+1

2

.

Gathering (4.22) with (4.23-4.24) concludes the proof of (4.20) in all cases.

STABLE SYSTEMS

Now fix V 2 and V 1 such that |H ∩ V 2 | ≥ |H ∩ V 1 | for any H ∈ H, and |V 2 | < |V 1 | which from (4.20), implies that µ(V 2 ) < µ(V 1 )
. Then, applying again (4.1) to V 2 and V 1 we get that

X n (V 2 ) + X n (V 1 ) ≥ A n (V 2 ) + A n (V 1 ) -2 H∈H |H ∩ V 2 | M n (H) ≥ A n (V 2 ) + A n (V 1 ) -2A n (V 2 ),
thus, from the usual argument, the model cannot be stable unless µ(V 2 ) ≥ µ(V 1 ), a contradiction.

Cycles

Proposition 4.10. Any r-uniform -cycle of order q such that r divides q, is non-stabilizable.

Proof.

The partition V 1 , V 2 , • • • , V r of V defined by V i = v i+(j-1)r ; j ∈ 1, q/r ,
satisfies Proposition 4.8.

Figure 1.6 shows a 3-uniform 2-cycle of order 12 and 3-uniform 2-cycle of order 6.

Stable systems

We show hereafter that stable matching models on hypergraphs exist. With a view to showing how stability can be shown in concrete examples, we provide hereafter two case studies of simple hypergraphs, on which a stable stochastic matching model can be defined: complete 3-uniform hypergraphs, and subhypergraphs of the latter where several hyperedges are erased.

Complete 3-uniform hypergraphs

We first consider the case of a complete 3-uniform hypergraph H, an example of which for q(H) = 4 is represented in Figure 1.4 (left). We show that, in this case, the necessary condition given in Proposition 4.3 is also sufficient, Theorem 4.1. Let H = (V, H) be a complete 3-uniform hypergraph of order q(H) ≥ 4.

Then, for any admissible policy Φ we have,

STAB(H, Φ) = N - 3 (H),
that is, the model (H, Φ, µ) is stable if and only if µ(i) < 1/3 for any i ∈ V.

Proof. Necessity of the condition being shown in Proposition 4.3, only the sufficiency remains to be proven. Suppose that µ(i) < 1/3 for any i ∈ V, and fix α such that max i∈V µ(i) < α < 1/3. Define the planar Markov chain {U α n ; n ∈ N} having the following transitions on N2 , Denote by ∆ = (∆ x , ∆ y ), ∆ = (∆ x , ∆ y ) and ∆ = (∆ x , ∆ y ), the mean (horizontal and vertical) drifts of the chain {U α n ; n ∈ N}, respectively on the interior, on the first and on the second axis, in a way that

                          
     First axis: ∆ x = α, ∆ y = 1 -α;
Second axis:

∆ x = 1 -α, ∆ y = α;
Interior:

∆ x = 3α -1, ∆ y = 3α -1.
Thus, ∆ x < 0 and ∆ y < 0. Also, we have that

∆ x ∆ y -∆ y ∆ x = ∆ x ∆ y -∆ y ∆ x = (3α -1)(1 -2α) < 0,
so we can apply Theorem 1.2, part (a), to claim that the Markov chain {U α n } is positive recurrent. Specifically, it can be checked that, setting u = 1-3α 3α -1 < w < (3α-1)α 1-α < 0 we have that

               2u∆ x + w∆ y < 0, 2u∆ y + w∆ x < 0, 2u∆ x + w∆ y < 0, 2u∆ y + w∆ x < 0. (4.25)
Second, as 4u 2 > w 2 the quadratic form Q : (x, y) → ux 2 + uy 2 + wxy is positive definite.

Then, in view of Lemma 1.1, it follows from (4.25) that, defining the mapping

L α :    N 2 -→ R + (x, y) -→ Q(x, y) = ux 2 + uy 2 + wxy,
we have that for some compact set

K α ⊂ N 2 , for any (x, y) ∈ K α , E L α U α n+1 -L α (U α n ) | U α n = (x, y) < 0. (4.26)
Now, as H is complete 3-uniform, the states of the Markov chain {X n ; n ∈ N} have at most two non-zero coordinates, in other words, its state space is E = x = (x 1 , ..., x q ) ∈ N q : x i x j x k = 0 for any distinct i, j, k ∈ 1, q .

Define the mapping L :

           E -→ R + x -→      0 if x = 0, L α ((x, 0)) if x = x.e i , for some x > 0, i ∈ V, L α ((x, y)) if x =
x.e i + y.e j , for some x, y > 0, i = j, where the above definition is unambiguous due to the fact that L α is a symmetric form on N 2 . Also define the compact set

K = {x := x.e i + y.e j ∈ E : (x, y) ∈ K α } .
Then, first, if x ∈ K ∩ E is such that x = x.e i + y.e j for some x, y > 0 and i, j ∈ V, i = j, we get that

E [L (X n+1 ) -L(X n ) | X n = x] = (1 -µ(i) -µ(j)) (L (x -e i -e j ) -L(x)) + µ(i) (L (x + e i ) -L(x)) + µ(j) (L (x + e j ) -L(x)) = (1 -µ(i) -µ(j)) (L α (x -1, y -1) -L α (x, y)) + µ(i) (L α (x + 1, y) -L α (x, y)) + µ(j) (L α (x, y + 1) -L α (x, y)) < (1 -2α) (L α (x -1, y -1) -L α (x, y)) + α (L α (x + 1, y) -L α (x, y)) + α (L α (x, y + 1) -L α (x, y)) = E L α U α n+1 -L α (U α n ) | U α n = (x, y) ,
where, in the inequality above, we used the facts that L α is non-decreasing in its first and second variables, and such that

L α (x -1, y -1) < L α (x, y). Likewise, if x ∈ K ∩ E is such that x =
x.e i for some x > 0 and i ∈ V, we have that

E [L (X n+1 ) -L(X n ) | X n = x] = j =i µ(j) (L (x + e j ) -L(x)) + µ(i) (L (x + e i ) -L(x)) = (1 -µ(i)) (L α (x, 1) -L α (x, 0)) + µ(i) (L α (x + 1, 0) -L α (x, 0)) < (1 -α) (L α (x, 1) -L α (x, 0)) + α (L α (x + 1, 0) -L α (x, 0)) = E L α U α n+1 -L α (U α n ) | U α n = (x, 0) ,
remarking that L α (x, 1)< L α (x, 0). Recalling that X n = [W n ] for all n, using (4.26) in both cases, we conclude using the Lyapunov-Foster Theorem 1.1 that the chain {W n ; n ∈ N} is positive recurrent.

The complete 3-uniform k-partite hypergraphs generalize the complete k-partite graphs introduced in p.4 of [START_REF] Moyal | A product form and a sub-additive theorem for the general stochastic matching model[END_REF], also called separable graphs in [START_REF] Mairesse | Stability of the stochastc matching model[END_REF] and [START_REF] Moyal | On the instability of matching queues[END_REF] -or blow-ups of the complete graph of order k in some other references. Roughly speaking, a complete 3uniform k-partite hypergraph is a version of the complete 3-uniform hypergraph of order k, in which the k nodes are replicated into several replicas, each of the k sets of replicas forming an independent set I i , such that all replicas of the same set do not share any hyperedge with each other, but all share hyperedges of size 3 with all other pairs of replicas belonging to two different other sets of replicas. Observe that in the particular case where all the sets I 1 , ..., I k are of cardinality 1 (i.e., there are no replica), the complete 3-uniform k-partite hypergraph is just the complete 3-uniform hypergraph of order k. We can then easily generalize the latter result, Corollary 4.2. For k ≥ 4, let H be a complete 3-uniform k-partite hypergraph, and let I 1 , ..., I k be the corresponding partition into independent sets. Then, for any admissible policy Φ, the model ( H, Φ, μ) is stable if and only if μ(I i ) < 1/3 for any i ∈ 1, k .

Proof. The system has macroscopically (i.e., if we do not distinguish between items of classes that belong to the same independent set of the partition I 1 , ..., I k ) the same behavior as the complete 3-uniform hypergraph. Specifically, let q be the order of the hypergraph H, and define the mapping

Ψ : N q -→ N k x = (x 1 , ..., xq ) -→ x = (x 1 , ..., x k ) : ∀i ∈ 1, k , x i = j∈ 1,q ; j∈I i xi .
In words, Ψ maps the detailed class content of the model, onto a class content where one puts altogether all the elements of classes belonging to the same independent set of the partition I 1 , ..., I k . Take L as the Lyapunov function introduced in the previous proof. Fix an admissible policy Φ and a probability measure μ ∈ M ( Ṽ), and let Xn ; n ∈ N be the class-content process of the model ( H, Φ, μ). On another hand, let {X n ; n ∈ N} be the class-content process of the model (H, Φ, µ) defined on H = (V, H) the complete 3-uniform hypergraph of order k, for an arbitrary matching policy Φ and a probability measure µ ∈ M (V) such that µ(i) = μ(I i ) for any i ∈ 1, k . Then, it is easily seen that Xn ; n ∈ N and {X n ; n ∈ N} are connected by the following relation: for all n and all x ∈ N q ,

E L • Ψ Xn+1 -L • Ψ( Xn ) | Xn = x = E [L (X n+1 ) -L(X n ) | X n = Ψ(x)] ,
and the argument in the proof of Theorem 4.1 shows that the Markov chain Xn ; n ∈ N is positive recurrent whenever μ(i) < 1/3, that is, µ(I i ) < 1/3, for all i ∈ 1, k . This concludes the proof.

Incomplete 3-uniform hypergraphs

As is shown in Theorem 4.1 and Corollary 4.2, complete 3-uniform hypergraphs and complete 3-uniform k-partite hypergraphs are stabilizable for all matching policy Φ, for a large class of measures. We show hereafter that incomplete hypergraphs (in the sense defined hereafter) can also be stabilizable for a matching policy ML, Theorem 4.2. Let H = (V, H) be a complete 3-uniform hypergraph of order q ≥ 5, and let H = (V, H ) be the (3-uniform) subhypergraph of H obtained by setting H = H\J , where J is a subset of H containing disjoint hyperedges. Let J be the union of the elements of J . Then the model (H , ML, µ) is stable for any µ in

S (H ) = µ ∈ M (V) : max i∈J λ i (µ) ∨ max i∈ J ν i (µ) < 0 ∩ N 2 (H ) ∩ N - 3 (H ),
where the λ i (µ) : i ∈ J and ν i (µ) : i ∈ J are defined respectively by (4.28) and (4.29).

Proof. Fix Φ = ML, and let µ ∈ S (H ). For such H the study of {Y n ; n ∈ N} does not boil down to that of a planar Markov chain. Instead, we study the embedded chain {Y n ; n ∈ N} = {X 4n ; n ∈ N}, and consider the following quadratic Lyapunov function,

Q : N q -→ R + x -→ q i=1 (x i ) 2 .
Fix n ∈ N. We have the following alternatives given the value of the embedded chain {Y n ; n ∈ N} at time n, (i) First, for any i ∈ J, and any integer x i ≥ 2. It follows that for any j = k = = m = i ∈ V, the chain {Y n ; n ∈ N} makes the transitions that we will present in Appendix (7.10) from state Y n = x i .e i , then we deduce that

∆ i := E [Q (Y n+1 ) -Q (Y n ) |Y n = x i .e i ] = (8x i + 16)µ(i) 4 + 4(6x i + 10)µ(i) 3 j µ(j) + 6(4x i + 8)µ(i) 2 j µ(j) 2 + 4(2x i + 10)µ(i) j µ(j) 3 + 16 j µ(j) 4 + 12(2x i + 1)µ(i) 2 j,k µ(j)µ(k) + 12µ(i) j,k µ(j) 2 µ(k) -10(4x i + 4) j,k, µ(j) 2 µ(k)µ( ) -2(2x i + 5) j,k, µ(j) 2 µ(k)µ( ) -6(4x i + 4) j,k µ(j) 2 µ(k) 2 -4(2x i + 5) j,k µ(j) 3 µ(k) + 24µ(i) j,k µ(j)µ(k)µ( ) -24(4x i + 4) j,k, ,m µ(j)µ(k)µ( )µ(m) = λ i (µ)x i + β i (µ), (4.27)
for some bounded β i (µ), and for

λ i (µ) = 8µ 4 (i) + 24µ 3 (i) j =i µ(j) + 24µ 2 (i) j =i µ 2 (j) + 8µ(i) j =i µ 3 (j) + 24µ 2 (i) j,k =i µ(j)µ(k) -44 j,k, =i µ 2 (j)µ(k)µ( ) -24 j,k =i µ 2 (j)µ 2 (k) -8 j,k =i µ(j)µ 3 (k) -96 j,k, ,m =i µ(j)µ(k)µ( )µ(m). (4.28)
Consequently, as the above is negative, there exists a * 1 such that ∆ i < 0 whenever x i ≥ a * 1 . (ii) For any i ∈ J, and any integer x i ≥ 2, the transitions of {Y n ; n ∈ N} from the state x i .e i can be retrieved in a similar fashion to (7.10). It follows that for any j = k = = m = p = s = i ∈ V. Set H = {i, j, k} ⊂ J, the transitions that will present in the Appendix (7.11), then we deduce that ∆ i = ν i (µ)x i + β i (µ) for some bounded β i (µ) (see Appendix (7.12)), and setting H = {i, j, k} as the only element of J such that i ∈ H, we obtain that Thus, there exists a * 2 such that ∆ i < 0 whenever x i ≥ a * 2 . (iii) For any i = j such that {i, j} is not included in a hyperedge of the family J , for any integers x i , x j > 0, we obtain that

ν i (µ) = 8µ 4 (i) + 24µ 3 (i) ∈V\{i} µ( ) + 24µ 2 (i) ∈V\{i} µ 2 ( ) + 8µ(i) ∈V\{i} µ 3 ( ) -8 ∈H µ(j)µ 3 ( ) -4 ∈H: ends with kk µ(j)µ 2 (k)µ( ) -20 ∈H: otherwise µ(j)µ 2 (k)µ( ) -48µ(j)µ(k) ∈H µ 2 ( ) -4 ∈H: ends with µ(j)µ 2 ( )µ(m) -40 ∈H: otherwise µ(j)µ 2 ( )µ(m) + 48µ 2 (i)µ(j)µ(k) -8µ(j)µ(k) ,m∈H: ends with jk µ( )µ(m) -80µ(j)µ(k) ,m∈H: otherwise µ( )µ(m) -96 ,m∈H µ(j)µ( )µ(m)µ(p)+24µ 2 (i) ∈H µ(j)µ( )+24µ 2 (i) ,m∈H µ( )µ(m) -24 ∈H µ 2 (j)µ 2 ( ) -4 ∈H: ends with jj µ 2 (j)µ( )µ(m) -40 ∈H: otherwise µ 2 (j)µ( )µ(m) -8 ∈H µ 3 (j)µ( ) + 24µ(i) j,k∈H µ(j)µ 2 (k) -8 ,m∈H µ 3 ( )µ(m) -24 ,m∈H µ 2 ( )µ 2 (m)
∆ ij := E [Q (X n+1 ) -Q (X n ) |X n = x i .e i + x j .e j ] = λ ij (µ)x i + λ ji (µ)x j + β ij (µ),
for a bounded β ij (µ), and for

λ ij (µ) = 2 µ(i) - ∈V\{i,j} µ( ) and λ ji (µ) = 2 µ(j) - ∈V\{i,j} µ( ) . (4.30)
Now observe that V\{i, j} ∈ T (H), so ∈V\{i,j}

µ( ) > 1 3
, then λ ij (µ) < 0 and λ ji (µ) < 0.

Thus there exists a * 3 such that ∆ ij < 0 whenever x i ∨ x j ≥ a * 3 . (iv) For any i, j such that i = j and {i, j} ⊂ H for some H ∈ J , for any integers x i , x j > 0, we obtain that

∆ ij := E [Q (X n+1 ) -Q (X n ) |X n = x i .e i + x j .e j ] = ν ij (µ)x i + ν ji (µ)x j + β ij (µ)
for a bounded β ij (µ) and

ν ij (µ) = 2 µ(i) - ∈H µ( ) and ν ji (µ) = 2 µ(j) - ∈H µ( ) . (4.31)
As H ∈ T (H), so

∈H µ( ) > 1 3
, then ν ij (µ) < 0 and ν ji (µ) < 0.

Again, there exists a * 4 such that ∆ ij < 0 whenever x i ∨ x j ≥ a * 4 . (v) We finally consider the case where X n = x i .e i + x j .e j + x k .e k for H = {i, j, k}, for some H ∈ J , and integers x i , x j and x k such that x i , x j ≥ x k > 0.

∆ H := E [Q (X n+1 ) -Q (X n ) |X n = x i .e i + x j .e j + x k .e k ] = α i (µ)x i + α j (µ)x j + α k (µ)x k + β H (µ),
for a bounded β H (µ), and for

α i (µ) = 2 µ(i) - ∈H µ( ) , α j (µ) = 2 µ(j) - ∈H µ( ) and α k (µ) = 2µ(k). (4.32)
As H ∈ T (H), so α i (µ) < 0 and α j (µ) < 0. From this, we deduce as above the existence of an integer a * 5 such that ∆ H < 0 whenever x i ∨ x j ≥ a * 5 . To conclude, if we let K be the finite set

K = x ∈ E : x i ≤ max a * 1 , ..., a * 5 , 2 ; i ∈ V ,
then if follows from the above arguments that for any x ∈ E ∩ K and any n ∈ N,

E [Q (Y n+1 ) -Q (Y n ) |Y n = x] < 0.
We deduce from Lyapunov-Foster Theorem 1.1 that the chain {Y n ; n ∈ N} is positive recurrent. This is the case in turn for the chain {X n ; n ∈ N}.

(x) = 2x 4 -9x 3 + 12x 2 -13x + 12 6x 2 + 10x + 24 1 4
.

and S 1 (H ) := A (H ) ∩ N 2 (H ) ∩ N - 3 (H ). Then the model (H , ML, µ) is stable for any µ ∈ S 1 (H ).
Proof. Recalling (4.28) and (4.29), a simple algebra shows that

A (H ) ⊂ µ ∈ M (V) : max i∈J λ i (µ) ∨ max i∈ J ν i (µ) < 0 , thus S 1 (H ) ⊂ S (H ).
Example 4.3. Observe that for any such H = (V, H ) satisfying the assumptions of Theorem 4.2, the model (H , ML, µ U ) is stable for µ U the uniform distribution on V. Indeed, we have µ U ∈ S 1 (H ). To see this, first observe that ∀q ≥ 5, 2q 4 -9q 3 +12q 2 -13q+12

6q 2 +10q+24 > 1, see Fig- ure 4.5. Moreover, it is immediate that µ U ∈ N - 3 (H ).
It remains to show that µ U ∈ N 2 (H ). We proceed in three steps. First, for q = 5 the only incomplete 3-uniform hypergraph in the sense of Theorem 4.2 is the complete hypergraph on 1, 5 minus one vertex, say {1, 2, 3}.

It is then easily seen that {4, 5} is the only minimal transversal of H . So τ (H ) = 2, in a way that for all

T ∈ T (H ), µ U (T ) ≥ 2/5 > 1/3, showing that µ U ∈ N 2 (H ).
Now, if q = 6 there are two incomplete 3-uniform hypergraph in the sense of Theorem 4.2: the complete 3-uniform hypergraph on 1, 6 minus one hyperedge, say {1, 2, 3}; and the complete 3-uniform hypergraph on 1, 6 minus two disjoint hyperedges, say {1, 2, 3} and {4, 5, 6}. In both cases, {4, 5, 6} is a minimal transversal of H , thus τ (H ) = 3, and so µ U (T ) ≥ 3/6 > 1/3, for all T ∈ T (H), proving again that µ U ∈ N 2 (H ).

We now address the case where q > 6. First observe that

q -2 - q 3 > q 3 . (4.33)
Then, let p = |J | (using the notation of Theorem 4.2), and denote J = {H 1 , ..., H p }. It is easily seen that a transversal of H can be constructed from any minimal transversal of H , by induction, as follows:

• Take a minimal transversal T of H , and set H 0 := H and T 0 := T .

• For any i = 1, ..., p, set

H i = H i-1 ∪ {H i } and set T i , a transversal of (V, H i ) of minimal size among those including T i-1 . (T i necessarily exists since T i-1 ∪ {H i } is
a transversal of (V, H i ), as easily seen by induction.)

• We obtain H = H p by construction, and T := T p is a transversal of H.

We claim that

|T | ≤ |T | + p. (4.34)
To see this, observe that for any i = 1, ..., p we have the following alternative: either H i ∩ T i-1 = ∅, in which case we can take T i of the form T i-1 ∪{k} for any k ∈ H i , or

H i ∩T i-1 = ∅, in which case T i = T i-1 .
In all cases we have that

|T i | ≤ |T i-1 | + 1, and (4.34)
follows by induction. Observing that |T | ≥ τ (H) = q -2, that, as the H i 's are disjoint, p ≤ q 3 , and using (4.33) and (4.34), we finally obtain that

µ U (T ) = |T | q ≥ |T | -p q > 1 3 , hence, once again µ U ∈ N 2 (H ).
To conclude, µ U is in all cases, an element of S 1 (H ), implying that the model (H , ML, µ U )

is stable for all such H .

Discussion of results and conclusion

In this chapter, we have studied a generalization of stochastic matching models on graphs, by allowing the matching structure to be a hypergraph. This class of models appears to have a wide range of applications in operations management, healthcare, and assemble-to-order systems. After formally introducing the model, we have proposed a simple Markovian representation, under IID assumptions. We have then addressed the general question of stochastic stability, viewed as the positive recurrence of the underlying Markov chain. For this class of systems, solving this elementary and central question turns out to be an intricate problem.

As the results of Sections 4.1 and 4.2 demonstrate, stochastic matching models on hypergraphs are in general, difficult to stabilize. Unlike the GM on graphs, the non-emptiness of the stability region with matching models on hypergraphs depends on a collection of conditions in the geometry of the compatibility hypergraph: rank, anti-rank, degree, size of the transversals, existence of cycles, and so on.

Nevertheless, we show in Section 4.3 that the "house" of stable systems is not empty, but shelters models on various uniform hypergraphs that are complete, or complete up to a partition of their nodes (which is a reasonable assumption regarding kidney exchange programs with 3-cycles, in which case, according to the compatibility of blood types and immunological characteristics, most but not all hyperedges of size 3 appear in the compatibility graph).

We provide the exact stability region of the system in the first case, and a lower bound in the second. For this, we resort to ad-hoc multi-dimensional Lyapunov techniques.

Introduction

In this chapter we provide a further extension of the previous chapter, we introduced a new stochastic matching model on hypergraph, that generalizes the GM model, then we provide the necessary conditions of stability for the present model, and we precise the stability region in particular cases of GM model. Such as among dating websites and peer-to-peer interfaces it is possible to assume that the items of the same class can be matched together. Hence the need to consider matching models on compatibility matching structures that are multigraph rather than just a graph or hypergraph, i.e., an architecture of graph admitting self-loops that is, edges with permission to connect to themself. En route, by showing results for stochastic matching models on multigraphs, we show various results that have their inner interest for GM models on graphs -see in particular Propositions 5.1 and 5.3.

This stochastic matching model addressed in this chapter is formally defined as follows: items enter the system by single arrivals, and get matched by groups of 2 or possibly matched to itself in case that there exists self-loops, following compatibilities that are represented by a given multigraph. A matching policy determines the matchings to be executed in the case of a multiple-choice, and the unmatched items are stored in a buffer, waiting for a future match.

This chapter is organized as follows: In Section 5.1, we present our main results for GM models on multigraphs, among which, the maximality and the explicit product form of the stationary probability for the FCFM policy, and the maximality of Max-Weight policies.

To illustrate these results, several examples are presented in Section 5.2. The proofs of our main results are then presented in Sections 5.3, 5.4 and 5.5.

Theorem 5.1. The matching policy 'First Come, First Matched' is maximal: for any connected multigraph G that is not a bipartite graph, we have that STAB(G, FCFM) = NCOND(G).

Moreover, for any µ ∈ NCOND(G) the unique stationary probability Π W of the chain (W n ) n∈N is defined by

     Π W (ε) = α; Π W (w) = α q l=1 µ(w l ) µ(E({w 1 , . . . , w l }))
, for all w = w 1 . . . w q ∈ W \ {ε}, where

α -1 = 1+ I∈I( Ǧ) σ∈S |I| |I| i=1 µ e σ(i) µ(E({e σ(1) , . . . , e σ(i) })) -µ({e σ(1) , . . . , e σ(i) } ∩ V 2 ) , (5.2)
and where we denote I = {e 1 , . . . , e |I| } for any I ∈ I Ǧ .

Theorem 5.1 is proven in section 5.4.

Remark 5.1. If the model is finite, i.e., all nodes of G have self-loops or in other words, V 2 = ∅, then it readily follows from Theorem 5.1 that the unique stationary probability on the finite state space W, is given by

       Π W (ε) = α; Π W e σ(1) • • • e σ(|I|) = α |I| i=1 µ e σ(i) µ(E({e σ(1) , . . . , e σ(i) }))
, for all I ∈ I( Ǧ), σ ∈ S |I| , with the normalizing constant

α =    1+ I∈I( Ǧ) σ∈S |I| |I| i=1 µ e σ(i) µ(E({e σ(1) , . . . , e σ(i) }))    -1
• On another hand, as is shown in Theorem 5.3 of [START_REF] Jonckheere | Generalized Max-Weight policies in stochastic matching[END_REF], all Max-Weight matching policies such that β > 0 are maximal whenever G is a graph. (In particular, the maximality of 'Match the Longest' (ML) for GM models was first proven in Theorem 2 of [START_REF] Mairesse | Stability of the stochastc matching model[END_REF], as a consequence of the corresponding result for EBM models, (see Theorem 7.1 of [START_REF] Bušić | Stability of the bipartite matching model[END_REF]). This result can also be generalized to multigraphs: Theorem 5.2. Any Max-Weight policy Φ such that β > 0 is maximal: for any multigraph G that is not a bipartite graph, we have that STAB(G, Φ) = NCOND(G).

Aside from FCFM and Max-Weight policies, we can determine, or lower-bound, the stability region of the model for particular classes of multigraphs. Given a multigraph G = (V 1 ∪ V 2 , E), let us define an important class of matching policy that is called V 2 -favorable policies and we will be taken in this chapter. Definition 5.2. We say that an admissible matching policy Φ on G is V 2 -favorable if any incoming item always prioritizes a match with a compatible item of class in V 2 over a compatible item of class in V 1 , whenever it has the choice. Formally, if the class detail is given by x ∈ X and the arrival is of class v, it never occurs that the incoming v-item is matched with a j-item, for some j ∈ V 1 , while P(x, v) ∩ V 2 = ∅. Definition 5.3. Let G be a connected multigraph. We say that G is complete p-partite, p ≥ 2, if its maximal subgraph Ǧ is complete p-partite. Then, the minimal blow-up graph Ĝ (see Definition 1.14) itself is called an extended complete p-partite graph.

Observe that an extended complete p-partite graph is not complete p-partite whenever the construction above is non-trivial, i.e., the multigraph in the above definition is not a graph, see an example in Figure 5.1. Right: Extended complete 3-partite graph Ĝ.

Theorem 5.3. Let G be a complete p-partite multigraph, p ≥ 2. Then,

(i) If p ≥ 3 or V 1 = ∅, then any V 2 -favorable matching policy Φ is maximal, that is, STAB(G, Φ) = NCOND(G).
(ii) If p ≥ 3, then NCOND Ǧ ⊂ STAB(G, Φ), for any admissible matching policy Φ.

With the above results in hands, we have the following panorama regarding the stability region of a matching model on a connected multigraph G:

(i) Any measure µ that does not belong to the set NCOND(G) makes the system unstable;

(ii) If G is a bipartite graph, then the model cannot be stable;

(iii) Otherwise, the region NCOND(G) is necessarily non-empty, and the models (G, FCFM, µ)

and (G, Φ, µ) for any Max-Weight policy Φ, are stable for any µ ∈ NCOND(G);

(iv) For any complete p-partite multigraph (p ≥ 2) that is not a bipartite graph and any µ ∈

NCOND (G), any model (G, Φ, µ) such that µ ∈ NCOND Ǧ or Φ is V 2 -favorable, is stable.
As a by-product of Theorem 5.3 we can determine, or lower-bound, the stability region of GM models on extended complete p-partite graphs.

Definition 5.4. For any measures µ ∈ M (V) and μ ∈ M ( V), we say that μ extends µ on Ĝ, and that µ reduces μ on G, if

μ(i) = µ(i), for all i ∈ V 2 ; μ(i) + μ(i) = µ(i), for all i ∈ V 1 .
(5.3) Definition 5.5. Let Φ and Φ be two admissible matching policies, respectively on G and Ĝ.

We say that Φ extends Φ on Ĝ if, for any µ ∈ M (V) and μ ∈ M ( V), whenever both systems (G, Φ, µ) and ( Ĝ, Φ, μ) are in the same state w ∈ W and welcome the same arrival, Φ and Φ induce the same choice of match, if any.

Proposition 5.3. Let Ĝ be an extended complete p-partite graph, p ≥ 2, and Ǧ be its reduced graph.

(i) If p ≥ 3 or V 1 = ∅, then for any matching policy Φ on Ĝ that extends a V 2 -favorable policy on G, STAB( Ĝ, Φ) = NCOND( Ĝ).

(ii) If p ≥ 3, then for any measure μ on Ĝ whose reduced measure µ is an element of NCOND( Ǧ), and any matching policy Φ on Ĝ, the model ( Ĝ, Φ, μ) is stable.

The proofs of Theorem 5.2, Theorem 5.3 and Proposition 5.3 are given in section 5.5.

A few examples

In this section, we illustrate our main results by different examples. Φ, we have that STAB(G, Φ) = M (V). Let us focus on the FCFM policy. The set of admissible queue details is given by W = {ε, 1, 2, 3, 4, 13, 24, 31, 42}, and as a consequence of Remark 5.1, we can compute explicitly Π W , obtaining the following values:

                 Π W (ε) = α Π W (1) = α µ(1) 1-µ(3) Π W (2) = α µ(2) 1-µ(4) Π W (3) = α µ(3) 1-µ(1) Π W (4) = α µ(4) 1-µ(2) Π W (13) = α µ(1) 1-µ(3) µ(3) Π W (24) = α µ(2) 1-µ(4) µ(4) Π W (31) = α µ(3) 1-µ(1) µ(1) Π W (42) = α µ(4) 1-µ(2) µ(2), with α = 1 + µ(1) 1 + µ(3) 1 -µ(3) + µ(2) 1 + µ(4) 1 -µ(4) + µ(3) 1 + µ(1) 1 -µ(1) + µ(4) 1 + µ(2) 1 -µ(2) -1
, using the fact that I Ǧ = {{1}, {2}, {3}, {4}, {1, 3}, {2, 4}}.

NCOND(G) = µ ∈ M (V) : µ(1) < µ(2), µ({1, 3}) ∨ µ({1, 4}) < 1 2 .
Second, recall that the maximal subgraph Ǧ is the pendant graph that studied in Lemma 3 of [START_REF] Mairesse | Stability of the stochastc matching model[END_REF]. For η > 0, there exists a linear Lyapunov function L η such that for any w ∈ W, the drift ∆Φ µ L η (w) < 0 then from Proposition 5.8, we have ∆Φ μ L η (w) < 0 and ∆ Φ µ L η (w) < 0. Then the model (G, Φ, µ) and Ĝ, Φ, μ are stable.

Example 5.3. Consider now a multigraph G whose maximal subgraph is a complete 2partite graph of order 3 (i.e., a string of 3 nodes), as represented in Figure 5.3, We easily obtain that

NCOND(G) = µ ∈ M (V) : µ(1) < µ(2) < 1 2 , NCOND( Ĝ) = μ ∈ M ( V) : μ(1) < μ(2), μ(2) ∨ μ({1, 3}) ∨ μ({1, 3}) < 1 2 .
In view of Theorems 5.1 and 5.2, the respective stability regions STAB(G, FCFM) and STAB(G, MW)

under First Come, First Matched, or any Max-Weight policy, coincide with NCOND(G).

Let us first focus on the FCFM policy. The set of admissible queue details is given by:

W = {ε} ∪ 1 k : k ≥ 1 ∪ 2 k : k ≥ 1 ∪ 1 r 31 k-r : k ≥ 0, 0 ≤ r ≤ k .
By Theorem 5.1, we have

         Π W (ε) = α Π W (1 k ) = α µ(1) µ(2) k Π W (2 k ) = α µ(2) 1-µ(2) k Π W 1 r 31 k-r = α µ(1) µ(2) r × µ(3) 1-µ(1) × µ(1) 1-µ(1) k-r
, and since I Ǧ = {{1}, {2}, {3}, {1, 3}}, we can express α as follows,

α = 1 + µ(1) µ(2) -µ(1) + µ(2) 1 -2µ(2) + µ(3) 1 -µ(1) + µ(1) µ(2) -µ(1) µ(3) 1 -2µ(1) + µ(3) 1 -µ(1) µ(1) 1 -2µ(1) -1 .
Second, consider a matching policy Φ such that a 2-item always prioritizes a 1-item over a 3 or a 3-item. Then Φ extends a V 2 -favorable policy Φ on Ĝ. Thus, from Proposition 5.3 (i), the stability region of the system is NCOND( Ĝ), in other words Φ is maximal on Ĝ. We thereby generalize with a very simple proof, the result of Lemma 3 of [START_REF] Mairesse | Stability of the stochastc matching model[END_REF] to the case where µ(3) = µ(3). Last , in view of Theorem 5.3 (i), any V 2 -favorable matching policy on G (i.e., such that 2 prioritizes 1 over 3) is maximal, that is, has the stability region NCOND(G).

where the second equality is due to the fact that Ê = E ∪ E 1 . The third follows from the fact that E = E 1 ∪E 2 . The fouth follows from the fact that the equations (5.3) and (5.4) holds true.

Let us prove now the opposite implication =⇒: Let us now fix µ ∈ NCOND(G) and Î ∈ I( Ĝ). Clearly, Î can be written as the union Î = J 2 ∪ J 1 ∪ I 1 , where

J 1 ∪ I 1 ⊂ V 1 ,
J 2 ⊂ V 2 and J 2 ∪J 1 ∪I 1 ∈ I Ǧ . First observe that J 1 and I 1 are necessarily disjoint, as any element i ∈ J 1 ∩ I 1 would be such that i-i in Ĝ, a contradiction to the fact that Î ∈ I( Ĝ). Thus, μ1/2 ( Î) = μ1/2 (J 2 ∪ J 1 ) + μ1/2 (I 1 ) = μ1/2 (J 2 ∪ J 1 ) + μ1/2 (I 1 )

(5.5)

= μ1/2 (J 2 ∪ J 1 ∪ I 1 ) ≤ µ(J 2 ∪ J 1 ∪ I 1 ). Now, observe that µ (E (J 2 ∪ J 1 ∪ I 1 )) -µ (J 2 ∪ J 1 ∪ I 1 ) = µ (E (J 2 ∪ J 1 ∪ I 1 )) -µ (J 1 ∪ I 1 ) -µ (J 2 ) = µ (E (J 2 ∪ J 1 ∪ I 1 ) ∩ (J 1 ∪ I 1 ) c ) -µ (J 2 ) ≥ µ (E (J 2 )) -µ (J 2 ) > 0,
where the second equality is due to the fact that

J 1 ∪I 1 ⊂ E (J 2 ∪ J 1 ∪ I 1 ), because J 1 ∪I 1 ⊂ V 1 .
The weak inequality follows from the fact that E (J 2 ) is disjoint from J 1 ∪ I 1 (because Î is an independent set of Ĝ), and thereby, is included in E (J 2 ∪ J 1 ∪ I 1 ) ∩ (J 1 ∪ I 1 ) c . The last strict inequality follows from the fact that I 2 is an independent set of G (and of Ĝ). This, together with (5.5), implies that

μ1/2 ( Î) < µ(E(J 2 ∪ J 1 ∪ I 1 )) = µ(E 1 (J 2 ∪ J 1 ∪ I 1 )) + µ(E 2 (J 2 ∪ J 1 ∪ I 1 )) = μ1/2 (E 1 (J 2 ∪ J 1 ∪ I 1 )) + μ1/2 E 1 (J 2 ∪ J 1 ∪ I 1 ) + μ1/2 (E 2 (J 2 ∪ J 1 ∪ I 1 )) = μ1/2 E 1 (J 2 ∪ J 1 ∪ I 1 ) ∪ E 1 (J 2 ∪ J 1 ∪ I 1 ) ∪ E 2 (J 2 ∪ J 1 ∪ I 1 ) = μ1/2 E(J 2 ∪ J 1 ∪ I 1 ) ∪ E 1 (J 2 ∪ J 1 ∪ I 1 ) = μ1/2 Ê(J 2 ∪ J 1 ∪ I 1 ) = μ1/2 Ê J 2 ∪ J 1 ∪ I 1 = μ1/2 ( Ê( Î)),
where the first equality is due to the fact that E = E 1 ∪ E 2 . The second equality follows from the fact that the equations (5.3) and (5.4) holds true. The third follows from the disjoint sets.

The fourth equality follows from the fact that E = E 1 ∪ E 2 . The fifth equality follows from the fact that Ê = E ∪ E 1 .

Which completes the proof.

Proof. Let µ be an invariant measure for P Y , and let b ∈ S . We have

a ∈S µ (a )P Y (a , b ) = a ∈S   a∈p -1 ({a }) µ(a)   P Y (a , b ) = a ∈S a∈p -1 ({a }) µ(a)P Y (a, p -1 ({b })) = s∈S µ(s)P Y (s, p -1 ({b })) = µ(p -1 ({b })) = µ (b ),
meaning that µ is invariant for P Y .

For µ ∈ NCOND(G), let us denote by Π B the unique stationary probability law associed to the chain (B n ) n∈N (cf. Prop. 5.5). It is defined by

∀w ∈ B, Π B (w) = αν B (w),
where α = (ν B (B)) -1 is given by (5.2) in view of (5.8). Let us now introduce the projection p :

   B -→ W w -→ w| V ,
which is well-defined from Lemma 5.3. We have the following result:

Proposition 5.6. Let µ ∈ NCOND(G). Then, the Markov chain (W n ) n∈N is positively recurrent, and its unique stationary probability distribution is the measure Π W defined on W by:

∀w ∈ W, Π W (w) = Π B (p -1 (w)) = w∈B : w| V =w Π B (w).
Proof. Let µ ∈ NCOND(G). We can apply Lemma 5.6 to P B and P W to prove that Π W is a stationary distribution for (W n ) n∈N . Indeed, using the fact that for any n ∈ N, W n is the restriction of the word B n to its letters in V, we have that ∀w, w ∈ W, ∀w ∈ p -1 ({w}), P B (w, p -1 ({w })) = P W (w, w ).

The measure Π W is a probability distribution on W, since

Π W (W) = Π B (p -1 (W)) = Π B (B) = 1.
The chain (W n ) n∈N being irreducible on W, it follows that Π W is its unique stationary probability distribution.

w) for a (G, Φ, µ) (resp. ( Ĝ, Φ, μ), ( Ǧ, Φ, μ)) system. In other words, for any n ∈ N we denote

∆ Φ µ F (w) = E F (W n+1 ) -F (W n ) W n = w ; ∆Φ μ F ( ŵ) = E F ( Ŵn+1 ) -F ( Ŵn ) Ŵn = ŵ ; ∆Φ μ F ( w) = E F ( Wn+1 ) -F ( Wn ) Wn = w .

Drift inequalities

Consider the following mappings,

Q :      Ŵ -→ R + ŵ -→ |V| i=1 (| ŵ| i ) 2 + |V 1 | i=1 (| ŵ| i ) 2 ;
(5.9)

L :      Ŵ -→ R + ŵ -→ |V| i=1 α i | ŵ| i + |V 1 | i=1 α i | ŵ| i , (5.10)
with α i , α i ∈ R + and α i = α i for all i ∈ V 1 .
Where it follows from the observation above that Q and L are well defined also on W and W.

Definition 5.8. Let Φ and Φ be two admissible matching policies, respectively on G and Ĝ.

We say that Φ extends Φ on Ĝ if, for any µ ∈ M (V) and μ ∈ M ( V), whenever both systems (G, Φ, µ) and ( Ĝ, Φ, μ) are in the same state w ∈ W and welcome the same arrival, Φ and Φ induce the same choice of match, if any.

We have the following result, Proposition 5.7. Let Φ be an admissible policy on G and µ ∈ M (V). Let Φ be a matching policy extending Φ on Ĝ and μ be a measure extending µ on V. Then, for all w ∈ W we

have that ∆ Φ µ Q(w) ≤ ∆Φ μ Q(w).
Proof. Fix w ∈ W throughout the proof. Recall that for all i ∈ V 1 (if any), we have that |w| i ∈ {0, 1}, and let us set

O w = {i ∈ V 1 : |w| i = 1}, Z w = {i ∈ V 1 : |w| i = 0 and |w| j = 0, for any j ∈ E(i)}.
First, for any i ∈ V 2 , an incoming item of class i finding the system (G, Φ, µ) in a state w finds the same possible matches (if any) as an incoming item of class i finding the system ( Ĝ, Φ, μ) in a state w. As Φ extends Φ, the choice of the match (if any) of the incoming item of class i is then the same, or follows the same distribution in case of a draw, in both systems. Thus, for all n ∈ N, as

| Ŵn+1 | V 1 = 0 the conditional distribution of W n+1 1l {V n+1 =i}
given {W n = w} equals the conditional distribution of Ŵn+1 1l { Vn+1 =i} given Ŵn = w . Therefore, we obtain that for all n ∈ N, (5.11) where the third equality due to the equality of the conditional distribution of W n+1 1l {V n+1 =i} given {W n = w} and Ŵn+1 1l { Vn+1 =i} given Ŵn = w .

E (Q(W n+1 ) -Q(W n )) 1l {V n+1 ∈V 2 } W n = w = i∈V 2 E Q(W n+1 )1l {V n+1 =i} W n = w - i∈V 2 E Q(W n )1l {V n+1 =i} W n = w = i∈V 2 E Q(W n+1 )1l {V n+1 =i} W n = w -µ(V 2 )Q(w) = i∈V 2 E Q Ŵn+1 1l { Vn+1 =i} Ŵn = w -μ(V 2 )Q(w) = E Q Ŵn+1 -Q Ŵn 1l { Vn+1 ∈V 2} Ŵn = w ,
Likewise, if a system (G, Φ, µ) is in state w, then, for any i ∈ V 1 ∩ (O w ) c ∩ (Z w ) c , an incoming of class i finds the same possible matches (if any) as an incoming item of class i or of class i finding the system ( Ĝ, Φ, μ) in the state w. Again, the choice of the match of the latter is the same in both systems, or follows the same distribution in case of a draw.

Like in (5.11), we obtain that, for all n ∈ N,

E (Q(W n+1 ) -Q(W n )) 1l {V n+1 ∈V 1 ∩(Ow) c ∩(Zw) c } W n = w = E Q Ŵn+1 -Q Ŵn 1l { Vn+1 ∈(V 1 ∩(Ow) c ∩(Zw) c )∪(V 1 ∩(Ow) c ∩(Zw) c )} Ŵn = w , (5.12)
where we also use the fact that

μ (V 1 ∩ (O w ) c ∩ (Z w ) c ) ∪ V 1 ∩ (O w ) c ∩ (Z w ) c = µ(V 1 ∩ (O w ) c ∩ (Z w ) c ).
Now, if a system (G, Φ, µ) is in state w, then, for any i ∈ Z w , and incoming item of class i finds no possible match. So, it is stored in line and the coordinate i of the chain increases from 0 to 1. Consequently, for any n ∈ N, conditional on {W n = w} and for any such i, we get that

(Q(W n+1 ) -Q(W n )) 1l {V n+1 =i} = (Q(wi) -Q(w)) 1l {V n+1 =i} = 1l {V n+1 =i} . (5.13)
Similarly, if the system ( Ĝ, Φ, μ) is in the state w and the entering item is of class i ∈ Z w or of class i ∈ Z w , then, in both cases, the entering item does not find any possible match in ( Ĝ, Φ, μ) and so the coordinate i or i of the Markov chain increases from 0 to 1. Thus, given that Ŵn = w , we get that

Q Ŵn+1 -Q Ŵn 1l { Vn+1 ∈{i,i}} = (Q(wi) -Q(w)) 1l { Vn+1 =i} + (Q (wi) -Q(w)) 1l { Vn+1 =i} = 1l { Vn+1 =i} + 1l { Vn+1 =i} .
(5.14)

This, together with (5.13), entails that

E (Q(W n+1 ) -Q(W n )) 1l {V n+1 ∈Zw} | W n = w = i∈Zw E 1l {V n+1 =i} | W n = w = µ(Z w ) = μ (Z w ) + μ Z w = i∈Zw E 1l { Vn+1 =i} + 1l { Vn+1 =i} | Ŵn = w = E Q( Ŵn+1 ) -Q( Ŵn ) 1l { Vn+1 ∈Zw∪Zw} | Ŵn = w , (5.15)
where the first equality due to the equation (5.13). The third equality follows from the equation (5.3) as Z w ⊂ V 1 . The fourth equality follows from the equation (5.14).

At last, if the system (G, Φ, µ) is in the state w, then, the arrival of a class i-item, for i ∈ O w , leads to the matching of two items of class i. Therefore, as |w| i = 1 we obtain

(Q(W n+1 ) -Q(W n )) 1l {V n+1 ∈Ow} = -1l {V n+1 ∈Ow} . (5.16)
Now, suppose that the system Ĝ, Φ, μ is in the state Ŵn = w. Then, if an item of class i ∈ O w enters in the system, the corresponding item is not matched and the number of i-items in the system increases from 1 to 2. Therefore we get that

Q Ŵn+1 -Q Ŵn 1l { Vn+1 ∈Ow} = 31l { Vn+1 ∈Ow} .
(5.17)

If on the other hand, an item of class i ∈ O w enters in the same system ( Ĝ, Φ, μ), then, the corresponding item match with the stored class i-item and so the coordinate i of the chain decreases to 0. Thus,

Q Ŵn+1 -Q Ŵn 1l { Vn+1 ∈Ow} = -1l { Vn+1 ∈Ow} .
Now, we also clearly have that

E L( Wn+1 ) -L( Wn ) 1l { Vn+1 ∈Pw} | Wn = w = i∈Pw α i µ (i) ; E L( Ŵn+1 ) -L( Ŵn ) 1l { Vn+1 ∈Pw} | Ŵn = w = i∈Pw α i μ (i) ; E L( Ŵn+1 ) -L( Ŵn ) 1l { Vn+1 ∈Pw} | Ŵn = w = - i∈Pw α i μ (i) ,
which, together with (5.21), implies that

∆Φ μ L(w) = ∆Φ µ L(w) -2 i∈Pw α i μ (i) .

Proofs of the remaining main results

We are now in position to prove Theorem 5.2, Theorem 5.3 and Proposition 5.3.

Proof of Theorem 5.2. Let µ ∈ NCOND(G). From Lemma 5.2, the measure μ belongs to NCOND( Ĝ). Let Φ be a matching policy of the Max-Weight class on G, with β > 0. Clearly, its extension Φ is also of the Max-Weight class on Ĝ. Then, we know from Theorem 5.3 in [START_REF] Jonckheere | Generalized Max-Weight policies in stochastic matching[END_REF] that the model ( Ĝ, Φ, μ) is stable. In particular, we see in the proof of Theorem 5.3 in [START_REF] Jonckheere | Generalized Max-Weight policies in stochastic matching[END_REF] that the Lyapunov-Foster Theorem 1.1 can be applied to the chain Ŵn n∈N for the quadratic function Q. Specifically, there exist η > 0 and a finite set K ⊂ Ŵ such that ∆Φ μ Q( ŵ) < -η for all ŵ ∈ K. Thus, in view of Proposition 5.7, we have that ∆ Φ µ Q(w) < -η for any w that lies outside the finite subset K = K ∩ W. We conclude by applying the Lyapunov-Foster Theorem to the mapping Q and the compact set K.

Proof of Theorem 5.3.

(i) Fix µ ∈ NCOND(G). First, if G is a graph (V 1 = ∅) and G = Ǧ
is complete p-partite for p ≥ 3, then the result follows from Theorem 2, Assertion ( 16) in [START_REF] Mairesse | Stability of the stochastc matching model[END_REF]: specifically, we have that for some η > 0, for any w ∈ W \ {ε},

∆ Φ µ L(w) < -η, (5.22)
and the Lyapunov-Foster criterion applies. Now, if G is not a graph, i.e.

L δ :      W -→ R + w -→ i∈V 1 δ 2µ(V 1 ) |w| i + i∈V 2 |w| i .
We also denote by X n the n-th marginal process corresponding to i 0 , defined by

X n (t) = X (nt), t ≥ 0,
and define

X n (t) = X (nt) n , t ≥ 0, n ≥ 1.
For the fluid analysis, we make two assumptions below, ASSUMPTION 1. Q n (0) ∈ E, for any n ≥ 1, and Qn (0) ⇒ Q(0) as n -→ ∞, where Q(0) is a deterministic element of R |V| , with Qi 0 (0) > 0 and Qi (0) = 0, i ∈ V\{i 0 }. ASSUMPTION 2. For all n ≥ 1, the E R -valued process X n is ergodic with stationary probalility π n .

For n ≥ 1, let

ρ n := ρ n (Q n (0)) := inf{t ≥ 0 : Q n i 0 (t) = 0}, with inf ∅ := ∞. (6.8)
In the case where G is a graph, the following result was given as Theorem 4 of [START_REF] Moyal | On the instability of matching queues[END_REF]. Hereafter, for a sequence of random variables {ρ n }, we write ρ n ⇒ ρ whenever

P [ρ n > M ] -→ n→∞ 1 for any M ∈ R.
Theorem 6.1. (FWLLN) Let G be a graph, and (G, Φ, λ) C be a matching queue such that Φ is class-admissible. If, for some node i 0

λ i 0 - j∈E(i 0 )
λ j π P R j (i 0 ) < 0, (6.9)

for π stationary probability and P R j (i 0 ), j ∈ E(i 0 ), then ρ n ⇒ ρ in R as n -→ ∞, for ρ n in (6.8), where ρ = Qi 0 (0)

j∈E(i 0 ) λ j π P R j (i 0 ) -λ i 0 . (6.10) Otherwise, ρ n ⇒ ∞. In either case, Qn ⇒ Q in D |V| [0, ρ) as n -→ ∞, where          Qi 0 (t) = Qi 0 (0) +   λ i 0 - j∈E(i 0 ) λ j π P R j (i 0 )   t, Qi (t) = 0, i ∈ V\{i 0 }. (6.11)
Notice that ρ n going to infinity in the sense specified above readily entails that the process Q cannot be positive recurrent, as is shown in Lemma 1 of [START_REF] Moyal | On the instability of matching queues[END_REF], following Proposition 9.9 in [START_REF] Robert | Stochastic networks and queues[END_REF]. In other words, Corollary 6.1. If ρ n ⇒ ∞, for ρ n in (6.8), then (G, Φ, λ) C is unstable. If

Qn (0) ⇒ xe 1 in R 4 for some x ∈ R ++ , then Qn ⇒ Q in D 4 [0, ρ) as n → +∞, where
Q(t) = (x + (λ 1 -λ 2 α)t, 0, 0, 0), 0 ≤ t < ρ,
for ρ := x/(λ 2 α -λ 1 ) if α > λ 1 /λ 2 and ρ := ∞ otherwise, and for

α := 1 + λ 3 λ 2 + λ 4 -λ 3 + λ 4 λ 2 + λ 3 -λ 4 -1 = (λ 2 ) 2 -(λ 3 -λ 4 ) 2 λ 2 (λ 2 + λ 3 + λ 4 ) . ( 6

.12)

Proof. The result follows from Corollary 6.2 by considering i 0 = 1. In that case the marginal process X has the following infinitesimal generator A R , with R = {3, 4},

                     A R ((i, 0), (i + 1, 0)) = λ 3 ; A R ((i, 0), (i -1, 0)) = (λ 2 + λ 4 )1l [1,+∞) (i); A R ((i, 0), (i, 0)) = -λ 3 + (λ 2 + λ 4 )1l [1,+∞) (i) ;
A R ((0, j), (0, j + 1)) = λ 4 ;

A R ((0, j), (0, j -1)) = (λ 2 + λ 3 )1l [1,+∞) (j);

A R ((0, j), (0, j))

= -λ 4 + (λ 2 + λ 3 )1l [1,+∞) (j) ; then we get,            -λ 3 π(0, 0) + (λ 2 + λ 4 )π(1, 0) = 0 λ 3 π(0, 0) -(λ 2 + λ 3 + λ 4 )π(1, 0) + (λ 2 + λ 4 )π(2, 0) = 0 λ 3 π(1, 0) -(λ 2 + λ 3 + λ 4 )π(2, 0) + (λ 2 + λ 4 )π(3, 0) = 0 . . . . . . . . . = 0 ⇐⇒                                π(1, 0) = λ 3 λ 2 + λ 4 π(0, 0) π(2, 0) = λ 3 λ 2 + λ 4 π(1, 0) π(3, 0) = λ 3 λ 2 + λ 4 π(2, 0) . . . ⇐⇒ π(i, 0) = λ 3 λ 2 + λ 4 π(i -1, 0) ; i ≥ 1.
Set π(0, 0) = α, so, for any state x ∈ E R we have,

π(x) =              α λ 3 λ 2 + λ 4 i x = (i, 0), i ≥ 1 α λ 4 λ 2 + λ 3 j x = (0, j), j ≥ 1.
Then we have,

1 = i≥1 π(i, 0) + j≥1 π(0, j) + π(0, 0) = π(0, 0) i≥1 π(i, 0) + j≥1 π(0, j) + 1 = π(0, 0) λ 3 λ 2 + λ 4 -λ 3 + λ 4 λ 2 + λ 3 -λ 4 + 1 .
The stationary distribution π of this reversible CTMC is unique, so Assumption 2 holds.

The stated convergence of Q n to the fluid limits follows from Corollary 6.2.

Proposition 6.2. The matching queue (G, Φ, λ) C corresponding to the pendant graph G with a self-loop on the vertex 2 and the priority type Φ depicted on Figure 6.1, is stable if and only if NCOND C (G) holds together with λ 1 < αλ 2 for α in (6.12).

Proof. It follows from Proposition 6.1 that, for any initial condition of the form (x, 0, 0, 0), x > 0, the fluid limit Q will hit the origin if and only if λ 1 < αλ 2 .

Assume that Q1 (0) > 0. Then at most one of Q3 (0) or Q4 (0) > 0. Say Q3 (0) > 0.

According to the priority of 3 over 1, then

Q3 (t) = Q3 (0) + (λ 3 -λ 2 -λ 4 )t, 0 ≤ t ≤ Q3 (0) λ 2 + λ 4 -λ 3 .
In particular, the fluid process Q3 will hit 0 in finite time, so that Q3 will hit the origin in finite time by Proposition 6.1. A similar argument applies to the case where Q4 (0) > 0.

Assume now that Q2 (0) > 0, there exists t 0 such that ∀t > t 0 , Q2 (t) = 0 (self-loop on vertex 2.) Now, since the prelimit processes Q i , i = 2, 3, 4 have drifts towards 0 whenever any of them is strictly positive, the fluid limit must remain in state 0 after hitting this state, and Proposition 6.1 shows that Q1 will also remain fixed at 0 after hitting that state. Thus, the ergodicity of the system follows from [17, Theorem 4.2].

Proposition 6.3. We have the strict inclusion

{λ 1 < αλ 2 } ∩ NCOND C (G) NCOND C (G).
Proof. Fix ε ∈ (0, 2/5] and set

     λ 1 = ε/2; λ 2 = ε; λ 3 = λ 4 = 1/2 -3ε/4.
Clearly, λ belong to the set NCOND C (G), but not to {λ 1 < αλ 2 }, since

λ 1 -αλ 2 = ε/2 - ε 2 ε + 1 -3ε/2 = ε/2 - 2ε 2 2 -ε ≥ 0.
Pendant graph with a self-loop on the vertex 3

Consider the multigraph G depicted on Figure 6. i.e., λ 1 < λ 2 < λ 1 + λ 3 + λ 4 , and

2 such that V 1 = {3}, V 2 = {1, 2, 4} and E = {{1, 2}, {2, 3}, {2, 4}, {3}, {3, 4}}.
λ 1 + λ 4 < λ 2 + λ 3 . If Qn (0) ⇒ xe 1 in R 4 for some x ∈ R ++ , then Qn ⇒ Q in D 4 [0, ρ) as n → +∞, where
Q(t) = (x + (λ 1 -λ 2 α)t, 0, 0, 0), 0 ≤ t < ρ,
for ρ := x/(λ 2 α -λ 1 ) if α > λ 1 /λ 2 and ρ := ∞ otherwise, and for

α := 1 + λ 3 λ 2 + λ 3 + λ 4 + λ 4 λ 2 + λ 3 -λ 4 -1 = (λ 2 + λ 3 ) 2 -λ 2 4 λ 2 2 + 2λ 2 3 + 3λ 2 λ 3 + λ 2 λ 4 . (6.13)
Proof. We prove with the same argue for Proposition 6.1. Set π(0, 0) = α, we get that

π(x) =            αλ 3 λ 2 + λ 3 + λ 4 x = (1, 0); α λ 4 λ 2 + λ 3 j x = (0, j), j ≥ 1.
Again, the stationary distribution π of this reversible CTMC is unique, so Assumption 2 holds. The stated convergence of Q n to the fluid limits follows from Corollary 6.2. Proposition 6.5. The matching queue (G, Φ, λ) C corresponding to the pendant graph G with a self-loop on the vertex 3 and the priority type Φ depicted on Figure 6.2, is stable if and only if NCOND C (G) holds together with λ 1 < αλ 2 for α in (6.13).

Proof. Assume that Q1 (0) > 0. It follows from the Proposition 6.4 that, for any initial condition of the form (x, 0, 0, 0), x > 0, the fluid limit Q will hit the origin if and only if λ 1 < αλ 2 .

Assume now that Q2 (0) > 0, then we have

Q2 (t) = Q2 (0) + (λ 2 -λ 1 -λ 3 -λ 4 )t, 0 ≤ t ≤ Q2 (0) λ 1 + λ 3 + λ 4 -λ 2 .
According to λ ∈ NCOND C (G) the fluid queue hits the origin in finite time.

Assume that Q1 (0) > 0, with at most one of Q3 (0) or Q4 (0) > 0. Set Q3 (0) > 0 then it is equal to 1. So there exists t 0 > 0 such that

Q3 (t) = 0, ∀t > t 0 .
Now assume that Q1 (0) > 0, and Q4 (0) > 0, then according to the priority of 4 over 1, then

Q4 (t) = Q4 (0) + (λ 4 -λ 2 -λ 3 )t, 0 ≤ t ≤ Q4 (0) λ 2 + λ 3 -λ 4 .
According to λ ∈ NCOND C (G), in particular, the fluid process Q4 will hit 0 in finite time, so that Q4 will hit the origin in finite time by Proposition 6.4. Now, since the prelimit processes Q i , i = 2, 3, 4 have drifts towards 0 whenever any of them is strictly positive, and Proposition 6.4 shows that Q1 will also remain fixed at 0 after hitting that state. Thus, the ergodicity of the system follows again from [17, Theorem 4.2].

Proposition 6.6. We have the strict inclusion

{λ 1 < αλ 2 } ∩ NCOND C (G) NCOND C (G).
Proof. Fix ε ∈ (0, 1/3] and set

     λ 1 = ε/2; λ 2 = ε. λ 3 = λ 4 = 1/2 -3ε/4;
Clearly, λ belongs to NCOND C (G), but not to {λ 1 < αλ 2 }, since

λ 1 -αλ 2 = ε/2- (ε + 1/2 -3ε/4) 2 -(1/2 -3ε/4) 2 ε 2 + 2 (1/2 -3ε/4) 2 + 4ε (1/2 -3ε/4) (ε) = ε/2- 8ε 2 -4ε 3 -7ε 2 + 4ε + 4
≥ 0.

Complete bipartite graphs with a self-loop

In this subsection, we present a different type of multigraphs of the form of complete bipartite graph with a self-loop on a such vertex.

Complete bipartite graph of order 3 with a self-loop on the vertex 2

Consider the multigraph G depicted on Figure 6.3 such that V 1 = {2}, V 2 = {1, 3} and E = {{1, 2}, {2, 3}, {2}}.

λ ∈ NCOND C (G) = {λ 1 + λ 3 < λ 2 }. If Qn (0) ⇒ xe 1 in R 3 for some x ∈ R ++ , then Qn ⇒ Q in D 3 [0, ρ) as n → +∞, where
Q(t) = (x + (λ 1 -αλ 2 )t, 0, 0), 0 ≤ t < ρ,
for ρ := x/(λ 2 α -λ 1 ) if α > λ 1 /λ 2 and ρ := ∞ otherwise, and for

α := 1 + λ 3 λ 2 -λ 3 -1 = λ 2 -λ 3 λ 2 . (6.14)
Proof. We argue as above. Setting π(0) = α, for any i ≥ 1, we get that

π(i) = α λ 3 λ 2 i ,
and the result follows again from Corollary 6.2.

Proposition 6.8. The matching queue (G, Φ, λ) C corresponding to the complete bipartite graph with a self-loop on the vertex 2 depicted on Figure 6.3 and for all matching policy Φ, (G, FCFM, µ) C is stable if and only if µ belongs to the set NCOND C (G).

Proof. First, consider that the priority type policy that depicted on Figure 6.3, we have:

Assume that that Q1 (0) > 0, and Q3 (0) > 0, then according to the priority of 3 over 1, then

Q3 (t) = Q3 (0) + (λ 3 -λ 2 )t, 0 ≤ t ≤ Q3 (0) λ 2 -λ 3 .
According to λ ∈ NCOND C (G), in particular, the fluid process Q3 will hit 0 in finite time, so that Q3 will hit the origin in finite time by Proposition 6.7.

Now assume that Q1 (0) > 0, it follows from the proposition 6.7 that, for any initial condition of the form (x, 0, 0), x > 0, the fluid limit Q will hit the origin if and only if λ 1 < αλ 2 . Indeed, we have

λ 1 < αλ 2 ⇐⇒ λ 1 < λ 2 -λ 3 λ 2 λ 2 ⇐⇒ λ 1 < λ 2 -λ 3 .
For this, it suffices that λ ∈ NCOND C (G). However, by symmetry between the vertices 1 and 3, we conclude that for all class-admissible matching policy Φ, we have STAB C (G, Φ) = NCOND C (G). See Theorem 5.3 (i).

Complete bipartite graph of order q = 4 with a self-loop on the vertex 1

Consider the multigraph G depicted on Figure 6.4 such that V 1 = {1}, V 2 = {1, 2, 3} and E = {{1}, {1, 2}, {1, 4}, {2, 3}, {3, 4}}. Proposition 6.9. Let G be the bipartite graph with a self-loop on the vertex 1 and Φ the matching policy depicted on Figure 6.4 (a). Consider an arrival-rate vector

λ ∈ NCOND C (G) = {λ 2 + λ 4 < λ 1 + λ 3 , and
λ 3 < λ 2 + λ 4 }. If Qn (0) ⇒ xe 3 in R 4 for some x ∈ R ++ , then Qn ⇒ Q in D 4 [0, ρ) as n → +∞, where
Q(t) = (0, 0, x + (λ 3 -α 1 (λ 2 + λ 4 ))t, 0), 0 ≤ t < ρ, for ρ := x/((λ 2 + λ 4 )α 1 -λ 3 ) if α 1 > λ 3 /(λ 2 + λ 4
) and ρ := ∞ otherwise, and for

α 1 = 1 + λ 1 λ 1 + λ 2 + λ 4 -1 = λ 1 + λ 2 + λ 4 2λ 1 + λ 2 + λ 4 . (6.15)
Proof. We argue as above, by computing explicitly the unique stationary distribution of the reversible marginal process.

Proposition 6.10. The matching queue (G, Φ, λ) C corresponding to the complete bipartite graph G with a self-loop on the vertex 1 and the priority type Φ depicted on Figure 6.4 (a), is stable if and only if NCOND C (G) holds together with

λ 3 < (λ 2 + λ 4 )α 1
for α 1 in (6.15).

Proof. Assume that Q2 (0) > 0, then according to the priority of 2 over 4, then

Q2 (t) = Q2 (0) + (λ 2 -(λ 1 + λ 3 ))t 0 ≤ t < Q2 (0) λ 1 + λ 3 -λ 2 .
Now assume that Q4 (0) > 0, so we have

Q4 (t) = Q4 (0) + (λ 4 -(λ 1 + λ 3 )α 2 )t 0 ≤ t < Q4 (0) (λ 1 + λ 3 )α 2 -λ 4 ,
for a simple calculs we get,

α 2 = λ 1 + λ 3 -λ 2 λ 1 + λ 3 . Observe that λ 4 -(λ 1 + λ 3 )α 2 = λ 2 + λ 4 -(λ 1 + λ 3 ), which is negative according to NCOND C (G).
Now assume that Q3 (0) > 0, so we have

Q3 (t) = Q3 (0) + (λ 3 -(λ 2 + λ 4 )α 1 )t 0 ≤ t < Q3 (0) (λ 2 + λ 4 )α 1 -λ 3 ,
it follows from the Proposition 6.9 that, for any initial condition of the form (x, 0, 0, 0), x > 0, the fluid limit Q will hit the origin if and only if λ 3 < α 1 (λ 2 + λ 4 ).

Proposition 6.11. We have the strict inclusion

{λ 3 < (λ 2 + λ 4 )α 1 } ∩ NCOND C (G) NCOND C (G).
Proof. Fix ε ∈ (0, 4/7] and set

     λ 1 = 1 -5ε/4; λ 2 = λ 4 = ε/2; λ 3 = 3ε/4.
Clearly, λ belong to NCOND C (G), but not to the set {λ 3 < (λ 2 + λ 4 )α 1 }, since

λ 3 -(λ 2 + λ 4 )α 1 = 3ε 4 -(ε) 1 -5ε/4 + ε 2 -5ε/2 + ε = 3ε 4 -(ε) 4 -ε 8 -6ε ≥ 0. Remark 6.1. Obseve that the multigraph G = (V, E) mentioned above is formed by V 1 =
{1} and V 2 = {2, 3, 4}. Then, if the matching policy Φ is V 2 -favorable depicted on Figure 6.4 (b), we get that

Q3 (t) = Q3 (0) + (λ 3 -λ 2 -λ 4 )t 0 ≤ t < Q3 (0) λ 2 + λ 4 -λ 3 ,
which satisfies the Theorem 5.3. Thus for all Φ = V 2 -favorable (G, V 2favorable, µ) C is stable if and only if µ belongs to the set NCOND C (G).

Hypergraphical cases study

In this section, we develop an example of a hypergraph in which we apply the fluid limits technique presented in Section 6.2 with some adaptation for hypregraphs and we find the results proved in Theorem 4.1 for complete 3-uniform hypergraph of order 4.

Complete 3-uniform hypergraph of order 4

First of all, given a complete 3-unifom hypergraph H = (V, H) of order q ≥ 4, then observe

that N - 3 (H) = µ(i) < 1 3 , ∀i ∈ V = µ(i) < 1 2 j∈V\{i} µ(j), i ∈ V .
Proposition 6.12. Let H = (V, H) be a complete 3-uniform hypergraph of order 4 and for all matching policy Φ. Consider an arrival-rate vector λ ∈ N -

C (H) i.e.    λ i < 1 2 j∈V\{i} λ(j), i ∈ V    . 1. If Qn (0) ⇒ xe 1 in R 4 for some x ∈ R ++ , then Qn ⇒ Q in D 4 [0, ρ) as n → +∞, 3
Q(t) = (x + (λ 1 -α 2 (λ 3 + λ 4 ) -α 3 (λ 2 + λ 4 ) -α 4 (λ 2 + λ 3 ))t, 0, 0, 0), 0 ≤ t < ρ, for ρ := x/(α 2 (λ 3 + λ 4 ) + α 3 (λ 2 + λ 4 ) + α 4 (λ 2 + λ 3 ) -λ 1 ), with                          α 2 = (λ 3 -λ 4 ) 2 + λ 2 (λ 3 + λ 4 ) λ 2 2 -(λ 3 -λ 4 ) 2 ; α 3 = (λ 2 -λ 4 ) 2 + λ 3 (λ 2 + λ 4 ) λ 2 3 -(λ 2 -λ 4 ) 2 ; α 4 = (λ 2 -λ 3 ) 2 + λ 4 (λ 2 + λ 3 ) λ 2 4 -(λ 2 -λ 3 ) 2 . (6.16) 2. If Qn (0) ⇒ xe 1 + ye 2 in R 4 for some x, y ∈ R ++ , then Qn ⇒ Q in D 4 [0, ρ) as n → +∞, where
Q (t) = (x + (λ 1 -λ 3 -λ 4 ))t, y + (λ 2 -λ 3 -λ 4 ))t, 0, 0), 0 ≤ t < ρ, for ρ := min (x/(λ 3 + λ 4 -λ 1 ), y/(λ 3 + λ 4 -λ 2 )) . where
Proof.

1. The marginal process is R = {2, 3, 4}. Then, similarly to the above resolution, we deduce that

π(x) =                            π(0, 0, 0) λ 2 λ 3 + λ 4 i , x = (i, 0, 0) i ≥ 1; π(0, 0, 0) λ 3 λ 2 + λ 4 j , x = (0, j, 0) j ≥ 1; π(0, 0, 0) λ 4 λ 2 + λ 3 k , x = (0, 0, k) k ≥ 1.
Set π(0, 0, 0) = π(0), and for any i, j, k ≥ 1, we set the following, π(i, 0, 0) = π 2 (i), π(0, j, 0) = π 3 (j) and π(0, 0, k) = π 3 (k).

1 = i≥1 π 1 (i) + j≥1 π 2 (j) + k≥1 π 3 (k) + π(0) = π(0) i≥1 λ 2 λ 3 + λ 4 i + j≥1 λ 3 λ 2 + λ 4 j + k≥1 λ 4 λ 2 + λ 3 k + 1 = π(0) λ 2 λ 3 + λ 4 -λ 2 + λ 3 λ 2 + λ 4 -λ 3 + λ 4 λ 2 + λ 3 -λ 4 + 1 = π(0) 4λ 2 λ 3 λ 4 (λ 3 + λ 4 -λ 2 )(λ 2 + λ 4 -λ 3 )(λ 2 + λ 3 -λ 4 )
.

Then we have,

π(0) = (λ 3 + λ 4 -λ 2 )(λ 2 + λ 4 -λ 3 )(λ 2 + λ 3 -λ 4 ) 4λ 2 λ 3 λ 4 .
Then the queue Q1 be as follow,

Q1 (t) = Q1 (0) + λ 1 -λ 2 j≥1 π 3 (j) + k≥1 π 4 (k) -λ 3 i≥1 π 2 (i) + k≥1 π 4 (k) -λ 4 i≥1 π 2 (i) + j≥1 π 3 (j) t = Q1 (0) + λ 1 -π(0) λ 2 λ 3 λ 2 + λ 4 -λ 3 + λ 4 λ 2 + λ 3 -λ 4 + λ 3 λ 2 λ 3 + λ 4 -λ 2 + λ 4 λ 2 + λ 3 -λ 4 + λ 4 λ 3 λ 2 + λ 4 -λ 3 + λ 2 λ 3 + λ 4 -λ 2 t = Q1 (0) + λ 1 - (λ 3 + λ 4 -λ 2 )(λ 2 + λ 4 -λ 3 )(λ 2 + λ 3 -λ 4 ) 4λ 2 λ 3 λ 4 2λ 2 λ 3 λ 4 (λ 2 + λ 3 + λ 4 ) (λ 3 + λ 4 -λ 2 )(λ 2 + λ 4 -λ 3 )(λ 2 + λ 3 -λ 4 ) t = Q1 (0) + λ 1 - 1 2 (λ 2 + λ 3 + λ 4 ) t, ∀t > 0.
Therefore, similarly we obtain that for any i ∈ V, ∃t 0 > 0, any Qi (t) < 0, ∀t > t 0 .

2. Observe that, for any i, j ∈ V, we have V\{i, j} be a transversal of H and k∈V\{i,j} µ(k) > 1/3, then k∈V\{i,j} µ(k) > µ(i) and k∈V\{i,j} µ(k) > µ(j). In other words, for any i, j ∈ V, we have λ V\{i,j} > λ i and λ V\{i,j} > λ j . In every two above cases, special blood tests and tissue are needed to find which help to match a donor's kidney. To receive a kidney where the recipient's markers and the donor's markers all are the same is a "perfect match" kidney. Perfect match transplants have the best chance of working for many years. Most perfectly matched kidney transplants come from siblings.

Crossmatch: Throughout life, the body makes substances called antibodies that act to destroy foreign materials. The crossmatch is done by mixing the recipient's blood with cells from the donor. If the crossmatch is positive, it means that there are antibodies against the donor. The recipient should not receive this particular kidney unless special treatment is done before transplantation to reduce the antibody levels. If the crossmatch is negative, it means the recipient does not have antibodies to the donor and that they are eligible to receive this kidney. See [START_REF] Özen | Incomplete Antibodies May Reduce ABO Cross-Match Incompatibility: A Pilot Study[END_REF].

Cross matches are performed several times during preparation for a living donor transplant, and a final crossmatch is performed within 48 hours before this type of transplant. The cross matches is a particular organization of kidney transplant with living donors authorized by the law of bioethics of July 7, 2011, and its decree of application published in September 2012. This donation is governed by three principles laid down by the law:

• The information of the donor,

• anonymity between the two pairs,

• simultaneity of surgical interventions.

This solution can be considered when the loved one who wishes to donate is not compatible with the patient.

The models

In all the aforementioned applications, elements (donors, receivers, or couples donor/receiver) arrive into the healthcare system at random times, and with various specificities. Compatibilities between elements (donors with receiver, or couples donor/receiver with other couples) need to be taken into account when performing the matches between them.

Thereafter, we will address the particular case of living donors: we assume that the elements entering the system are couples of family members consisting of a giver and a receiver and that the giver and the receiver may not be compatible amongst them. This system is modeled as a stochastic matching model in which items (i.e., couples) are gathered into classes. Here, we say for instance that the class of a given item i is (A, B) if the giver of the couple i has blood type A and the receiver has blood type B. Items of the various classes enter the system following independent Poisson processes of designated intensities and using a simple homogenization argument, we focus on the embedded chain of the corresponding continuous-time system, namely, we work with a discrete-time stochastic matching model.

Three types of matching can be taken into account:

1. In the one by one matching model, elements can be matched within couples, if possible. This corresponds equivalently, to an extended bipartite matching model (EBM) as defined in Chapter 3, in which items are single individuals rather than couples, and couples of items (giver/receiver) enter the system simultaneously. Then, the compatibility graph is bipartite, between givers and receivers. compatibilities between couples, in the sense specified above. A matching between two couples is made whenever the two matchings are performed together.

3. The three by three matching model allows couples to be matched by groups of three.

Then, a match between the three couples of respective classes i, j and k is possible if and only if the giver of i is compatible with the receiver of j, the giver of j is compatible with the receiver of k and the giver of k is compatible with the receiver of i. Then, the three transplants can be performed simultaneously. These settings thus correspond to a general stochastic model on a hypergraph that is 3-uniform, namely, matches are performed between groups of three items (i.e., couples) only. This situation may occur if we address only a designated part of the whole transplant network, or if we consider an access control, for instance. We then set V = {1, 2, 3, 4}, and consider the various matching structure S = (V, S), on V that correspond, respectively, to the various types of matchings introduced above. • And so on....

Matching one by one

In the above case, the matching one-by-one is preferable for items of classes 1, 2, and 3, since the transplants between the giver and the receiver of each of these compatible couples can be made between family members. However, it is easily seen that, if incoming items of classes 1, 2 and 3 are matched 'with themselves' in a systematic way, then the elements of the couples of class 4, which are not compatible, will never be matched since a A-giver cannot give to a B-receiver. Then the resulting system is unstable since class 4-items will accumulate to infinity.

Matching two by two

Now, consider the case of the two by two matching. In this type of matching, the matching structure S is a graph such that S = G = (V, E) and whose edges are defined as E = {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}} , as is easily seen. The graph is thus a complete 3-partite graph of order 4, as depicted in Then the stationary probability of the natural Markov chain (X n ) n∈N reads as follows: for all x ∈ X, Proof. Whatever Φ is, the transition matrix P of the class-content is defined as follows,

π(x) =                            α µ (
                              
P ((0, i, 0, 0), (0, i + 1, 0, 0)) = µ(2); P ((0, i, 0, 0), (0, i -1, 0, 0)) = 1 -µ(2); P ((0, 0, j, 0), (0, 0, j + 1, 0)) = µ(3); P ((0, 0, j, 0), (0, 0, j -1, 0)) = 1 -µ(3); P ((k, 0, 0, ), (k + 1, 0, 0, )) = µ(1); P ((k, 0, 0, ), (k, 0, 0, + 1)) = µ(4); P ((k, 0, 0, ), (k -1, 0, 0, )) = µ(2) + µ(3) choice 1;

P ((k, 0, 0, ), (k, 0, 0, -1)) = µ(2) + µ(3) choice 4.

Then, we get

π(x) =                           
π(0, 0, 0, 0) µ(2) 1 -µ(2) i x = (0, i, 0, 0) ; i ≥ 1 π(0, 0, 0, 0) µ(3) 1 -µ(3) j x = (0, 0, j, 0) ; j ≥ 1 π(0, 0, 0, 0) µ(1) + µ(4) 1 -(µ(1) + µ(4)) k+ x = (k, 0, 0, ) ; k ∨ ≥ 1.

Set π(0, 0, 0, 0) = π(0), and for any i, j, k ≥ 1 we set the following, π(0, i, 0, 0) = π 2 (i), π(0, 0, j, 0) = π 3 (j) and π(k, 0, 0, ) = π 1,4 (k + ).

Then, we have Proof. The set of admissible queue details W is given by,

W ={ε} ∪ 2 k : k ≥ 1 ∪ 3 k : k ≥ 1
∪ 1 r 1 4 1 1 r 2 4 2 ... : k, k ≥ 0, 0 ≤ r i ≤ k, 0 ≤ j ≤ k , i = {1, 2, ...}, j = {1, 2, ...} .

We compute explicitly Π W , as the following values: , where we use the fact that the set of independent sets reads I (G) = {{1}, {2}, {3}, {4}, {1, 4}}.

                       Π W (ε) = α Π W (2 k ) = α µ(2) 1-µ(2) k Π W (3 k ) = α µ(3) 1-µ(3) k Π W (1 r

Matching three by three

We now consider the three by three matching procedure: for any triplet of items of respectives classes (X 1 , Y 1 ), (X 2 , Y 2 ) and (X 3 , Y 3 ), then X 1 donates to Y 2 , X 2 donates to Y 3 and X 3 donates to Y 1 . In this type of matching, the matching structure S is an hypergraph. Specifically, we set S = H = (V, H), where the hyperedges are defined as We have simulated one thousand trajectories of the three-by-three system, each one starting from an empty system and consisting of one million arrivals. Then,

Step 1: We count the total number of construction points over the million arrivals, and we get the average over the thousand trajectories.

Step 2: We count the total number of empty buffers at the instance 999999 for each of one million arrivals and get the average over the thousand trajectories.

In Table 7.1 hereafter we present our results for different distributions µ, applying for each distribution the two aforementioned steps. We denote the first average by 'Trajectorial Average' and the average of the empty buffers at time 999999 by 'Av. EB.' It is obvious that the three-by-three matching system is 3-periodic. Thus, starting from the empty state, it can be empty only at times that are multiples of three. So, it is only pertinent to compare the average of construction points for the whole trajectories (fourth column) to the third of the number of construction points seen at time 999999, a multiple of three (see the fifth column).

µ(1) µ( 2) µ(3) µ(4) Trajectorial Average Av. EB π(0, 0, 0, 0) ,m,p,s∈H µ( )µ(m)µ(p)µ(s) = ν i (µ)x i + β i (µ), (7.12)

1. 1 4 (

 14 Left: Graph. Middle: Hypergraph. Right: Multigraph. . . . . . . . . . . . . 1.2 Complete 3-partite graphs. . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Left: 'N' graph. Middle: 'NN' graph. Right: 'W' graph. . . . . . . . . . . 1.4 Left: Complete 3-uniform hypergraph of order 4. Right: multiple hypergraph. 1.5 A 3-uniform 3-partite hypergraph. . . . . . . . . . . . . . . . . . . . . . . 1.6 Left: A 3-uniform 2-cycle of order 12. Right: A 3-uniform 2-cycle of order 6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.7 Middle: A multigraph G. Left: Its maximal subgraph Ǧ. Right: Its minimal blow-up graph Ĝ. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.8 The renormalized process ( L(t)) and the fluctuations of ( LN (t)). . . . . . . 2.1 The matching model in action, on the matching hypergraph of Figure 1.left). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Matching Model (CTMC). . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Left: A skill-based queueing system. Right: A bipartite matching model. . . 3.2 The bipartite matching graph for the 'W' model. . . . . . . . . . . . . . . . 3.3 Left: Pendant graph. Right: 5-cycle graph. . . . . . . . . . . . . . . . . . . 3.4 A queueing network view of a system with four input streams and two matchings. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Any hypergraph with two isolated nodes is non-stabilizable. . . . . . . . . 4.2 Two intersecting hyperedges containing each, an isolated node outside of their intersection, make the system unstable. . . . . . . . . . . . . . . . . . 4.3 The Fano plane minus the hyperedge {4, 5, 7}. . . . . . . . . . . . . . . . . 4.4 Auxiliary Markov chain of the complete 3-uniform hypergraph. . . . . . . . 4.5 The curve of the function f (x) = 2x 4 -9x 3 + 12x 2 -

  For a and b in N, we denote by a, b the integer interval [a, b] ∩ N. We let a ∧ b and a ∨ b denote the minimum and the maximum of two numbers a, b ∈ R respectively.

For

  an interval I ⊂ [0, ∞), let D d (I) denote the space of R d -valued functions on I that are right continuous and have limits from the left everywhere denoted by 'RCLL', given with the standard Skorohod J 1 topology [4]. To simplify notation, we write, e.g., D d (a, b) := D d ((a, b)), and D(I) := D 1 (I). However, for the convergence in D d that holds over an arbitrary compact subinterval of [0, ∞) we omit the interval from the notation. We write ⇒ to denote convergence in distribution and denote {Y n ; n ∈ Z ++ } the sequence of real-valued random variables. For any M > 0, if P (Y n > M ) → 1 as n → ∞, then we write Y n ⇒ ∞. Denote by Ȳ n := Y n /n the fluid-scaled version of a sequence of stochastic processes {Y n ; n ∈ Z ++ }.

Figure 1 . 1 :

 11 Figure 1.1: Left: Graph. Middle: Hypergraph. Right: Multigraph.

Figure 1 . 2 :

 12 Figure 1.2: Complete 3-partite graphs.

3 Figure 1 . 3 :

 313 Figure 1.3: Left: 'N' graph. Middle: 'NN' graph. Right: 'W' graph.

Figure 1 . 4 :Example 1 . 2 .

 1412 Figure 1.4: Left: Complete 3-uniform hypergraph of order 4. Right: multiple hypergraph.

7 .

 7 The representative graph of a hypergraph H = (V, H) is the graph L(H) = (H, E) whose nodes are the elements of H, and such that (H i , H j ) ∈ E (i.e., H i and H j share an edge in the graph) if and only if H i ∩ H j = ∅. The hypergraph H is said connected if L(H) is connected.

Figure 1 . 5 :

 15 Figure 1.5: A 3-uniform 3-partite hypergraph.

Figure 1 . 6 :

 16 Figure 1.6: Left: A 3-uniform 2-cycle of order 12. Right: A 3-uniform 2-cycle of order 6.

2 Figure 1 . 7 :

 217 Figure 1.7: Middle: A multigraph G. Left: Its maximal subgraph Ǧ. Right: Its minimal blow-up graph Ĝ.

Figure 1 . 8 :

 18 Figure 1.8: The renormalized process ( L(t)) and the fluctuations of ( LN (t)).

Figure 2 . 1 :

 21 Figure 2.1: The matching model in action, on the matching hypergraph of Figure 1.4 (left).

Figure 2 . 2 :

 22 Figure 2.2: Matching Model (CTMC).

  (a) Modelisation of call center 'Skill-based'. (b) Bipartite matching model.

Figure 3 . 1 :

 31 Figure 3.1: Left: A skill-based queueing system. Right: A bipartite matching model.

'

  NN' model (i.e., the matching structure of the model is of the form 'NN' graph), and then the Conjecture (3.2) holds for any bipartite graph in which every server type is connected to all but at most 2 of the customer types and vice versa. A dynamic representation of 'W' model is given in Figure 3.2.(a) The bipartite graph for the 'W' model (b) The FCFS infinite matching for the 'W' model

Figure 3 . 2 :

 32 Figure 3.2: The bipartite matching graph for the 'W' model.

  copy of V. Define a bipartite matching model with classes V, server classes Ṽ, possible matches {(u, ṽ) | u-v}, and arriving sequence (v n , ṽn ) n . If the matching policies are the same, then at any time, the buffer-content of the bipartite matching model (U, Ũ ), if the buffer-content of the original matching model is U. Then several result transferred from the (EBM) model to (GM) model.

Figure 3 . 3 :

 33 Figure 3.3: Left: Pendant graph. Right: 5-cycle graph.

Figure 3 . 4 :

 34 Figure 3.4: A queueing network view of a system with four input streams and two matchings.

Fix a matching

  model (H, Φ, µ) on a hypergraph H = (V, H). Denote for any n, B ⊂ V and B ⊂ H, by A n (B) the number of arrivals of elements in B and by M n (B) the number of matchings of hyperedges in B realized up to n, i.e., A n (B) = n k=1 1l {V k ∈B} ; M n (B) = n k=1 1l {H(k)∈B} ;

  whereas if I ∈ I µ (H), as µ ∈ N 1 (H) we have thatµ(I) < H∈H |H ∩ I| min k∈H µ(k) ≤ H∈H |H ∩ I| min k∈H∩ Ī µ(k), hence µ ∈ N + 1 (H).It remains to show that µ ∈ N ++ 1 (H), and for this, we first observe that for all I ∈ I(H), µ(I)

( 4 . 7 )

 47 , we have that µ(B r ) ≤ H∈H |H ∩ B r | min k∈H µ(k), which implies by an immediate induction using (4.8), that µ(B) ≤ H∈H |H ∩ B| min k∈H µ(k).

Remark 4 . 1 .

 41 [Graphical case] Let us consider the special case where H = (V, H) is a graph. Then, it is shown in Proposition 2 of [32] that the stability region of the model is included in the set NCOND(H) = {µ ∈ M (V) : ∀I ∈ I(H), µ(I) < µ(E(I))} , where for any set B ⊂ V, E(B) = {j ∈ V : (i, j) ∈ H for some i ∈ B} . It is then easy to check by hand that NCOND(H) is included in N ++ 1 (H). Indeed, if we let µ ∈ NCOND(H) and I ∈ I(H) (meaning that I is an independent set of the graph H, in the usual sense), then, for any edge H ∈ H, |H ∩ I| = 1 if I contains a vertex of the edge H, and 0 else, so we get that H∈H |H ∩ I| min j∈H∩ Ī µ(j) = (i,j)∈H : i∈I µ(j) ≥ j∈E(I) µ(j) = µ(E(I)),

Proposition 4 . 3 .

 43 For any connected hypergraph H = (V, H) and any admissible policy Φ, STAB(H, Φ) ⊂ N + 3 (H). (4.13)

  ) hence the chain {W n ; n ∈ N} is transient since the right-hand side of the above is positive from (4.15).

Figure 4 . 1 :

 41 Figure 4.1: Any hypergraph with two isolated nodes is non-stabilizable.

Figure 4 . 2 :

 42 Figure 4.2: Two intersecting hyperedges containing each, an isolated node outside of their intersection, make the system unstable.

Figure 4 . 3 :

 43 Figure 4.3: The Fano plane minus the hyperedge {4, 5, 7}.

  ∈ N + , P α (x,y),(x-1,y-1) = 1 -2α, x, y ∈ N + ,and arbitrary transitions from (0, 0) to any element of N 2 . (These transitions are represented in Figure4.4 below).

Figure 4 . 4 :

 44 Figure 4.4: Auxiliary Markov chain of the complete 3-uniform hypergraph.

- 4 ,

 4 m,p∈H: ends with µ 2 ( )µ(m)µ(p)-40 ,m,p∈H: otherwise µ 2 ( )µ(m)µ(p)-96 ,m,p,s∈H µ( )µ(m)µ(p)µ(s).

Remark 4 . 4 . 2 , 4 . 3 . 24 1Figure 4 . 5 :

 442432445 Figure 4.5: The curve of the function f (x) = 2x 4 -9x 3 + 12x 2 -13x + 12 6x 2 + 10x + 24

5 Figure 5 . 1 :

 551 Figure 5.1: Middle: A multigraph G. Left: Its maximal complete 3-partite subgraph Ǧ.

Example 5 . 1 . 2 3 4 Figure 5 . 2 :

 512452 Figure 5.2: Multigraph G of Example 5.1.

Example 5 . 2 .

 52 Consider the multigraph G (at the middle) of Figure 1.7. From Theorems 5.1 and 5.2, both the stability region STAB(G, FCFM) under First Come, First Matched, and the stability region STAB(G, MW) under any Max-Weight policy, coincide with the set

3 Figure 5 . 3 :

 353 Figure 5.3: Left: A multigraph whose maximal subgraph is a complete 2-partite graph of order 3. Right: Its minimal blow-up graph.

V 1 =

 1 ∅, then let δ = min {µ(E(I)) -µ(I) : I ∈ I(G)} , which is strictly positive since µ ∈ NCOND(G), and the mapping

Figure 6 . 1 :

 61 Figure 6.1: Multigraph G with a self-loop on the vertex 2.

Figure 6 . 2 :Proposition 6 . 4 .

 6264 Figure 6.2: Multigraph G with a self-loop on the vertex 3.

1 2 3 Figure 6 . 3 :Proposition 6 . 7 .

 36367 Figure 6.3: Complete bipartite graph of order 2 with a self-loop on the vertex 2.

  Non V 2 -favorable policy.

  V 2 -favorable policy.

Figure 6 . 4 :

 64 Figure 6.4: Complete bipartite graph of order 4 with a self-loop on the vertex 1.

2 .

 2 The two by two matching model corresponds to the cross-transplant system, namely, couples of items, says of classes i and j, can be matched if and only if the giver class of class i is compatible with the receiver class of class j, and the giver class of class j is compatible with the receiver class of class i. Then the two transplants are performed simultaneously. In our framework, this corresponds to a general stochastic matching model (GM) in which the compatibility graph is general, and represents the 123

Figure 7 . 1 :

 71 Figure 7.1: Paired and pooled organ donation -Cross matching Two-by-Two and Three-by-Three [14].

Remark 7 . 1 .

 71 As will appear clearly below, similar matching models are obtained if, instead of (7.1), we consider for instance arrivals of the following couples,• 1 = (A,AB), 2 = (O, AB), 3 = (B, A) and 4 = (A, B); • 1 = (A, AB), 2 = (O, A), 3 = (B, A) and 4 = (A, B); 124 7.3. MATCHING ONE BY ONE • 1 = (B, AB), 2 = (O, B), 3 = (A, B) and 4 = (B, A); • 1 = (A, AB), 2 = (B, AB), 3 = (A, B) and 4 = (O, A);

Figure 7 .Figure 7 . 2 :

 772 Figure 7.2 below. In other words, G is analog to separable graph of order 3 and I 1 = {2}, I 2 = {3} and I 3 = {1, 4} are the maximal independent sets partitionning V,

(7. 2 ) 7 . 1 . 1 )

 2711 Proposition Consider the graph G = (V, E). Then, for all matching policy Φ the sets STAB(G, Φ) and NCOND(G) coincide, that is, the general stochastic matching model (G, Φ, µ) is stable if and only if µ satisfies condition(7.2). In other words we have STAB(G, Φ) = + µ(4) < 1/2.

(7. 3 )Proposition 7 . 2 .

 372 Proof. As G is a separable graph of order 3, then from [32, Proposition 2], we get that ∀Φ, µ ∈ STAB(G, Φ) ⇐⇒ µ ∈ NCOND(G). Consider the graph G = (V, E), and any admissible matching policy Φ.

2 ) 1 - 1 α 1 α µ( 1 ) 1 ( 7 . 4 )

 21111174 µ(2) i x = (0, i, 0, 0) ; i ≥ 0, 0, j, 0) ; j ≥ + µ(4) 1 -(µ(1) + µ(4)) k+ x = (k, 0, 0, ) ; k ∨ ≥where the normalizing constant is given byα = π(0, 0, 0, 0) = (1 -2µ(2))(1 -2µ(3))(1 -2(µ(1) + µ(4))) 4µ(2)µ(3)(µ(1) + µ(4)) . (7.5)

1 - 7 . 3 .

 173 2µ(2))(1 -2µ(3))(1 -2(µ(1) + µ(4))) ,and we conclude thatπ(0, 0, 0, 0) = (1 -2µ(2))(1 -2µ(3))(1 -2(µ(1) + µ(4))) 4µ(2)µ(3)(µ(1) + µ(4)) . (7.6) 7.5. MATCHING THREE BY THREE Proposition Consider the graph G. If Φ =FCFM, then we retrieve the results of [35, Theorem 1].

1 4 1 2 )

 12 1 r 2 4 2 ...) = α + µ(3) -µ(1) -µ(4) -1

H 1 =

 1 {1, 2, 3}, H 2 = {1, 4, 2}, H 3 = {4, 3, 1}, and H 4 = {4, 2, 3}. In other words, the hypergraph is a complete 3-uniform hypergraph as depicted in Figure 1.4. From Proposition 4.3 the necessary condition of stability for this matching model reads N - 3 (H) = {µ ∈ M (V) : µ(i) < 1/3, ∀i ∈ V} . (7.7)

  24µ( )µ(m)µ(p)µ(s) = m = p = s ∈ H. (7.11) 138 THE TRANSITIONS FOR THE PROOF OF THEROEM 4.1Then we decduce that,∆ i := E [Q (Y n+1 ) -Q (Y n ) |Y n = x i .e i ] = (8a i + 16)µ 4 (i) + 4(6a i + 10)µ 3 (i) ∈V µ( ) + 6(4a i + 8)µ 2 (i) ∈V µ 2 ( ) + 4(2a i + 10)µ(i) )µ( )µ(m) + 36µ(i) j∈H: ,m∈H: otherwise µ(j)µ( )µ(m) + 48µ(i) ,m,p∈H µ( )µ(m)µ(p) + 44 j,k∈H µ(j)µ 3 (k) -4(2a i + 5) j∈H: ∈H µ(j)µ 3 ( ) -2(2a i + 5) j,k∈H: ∈H: ends with kk µ(j)µ 2 (k)µ( ) -10(2a i + 3) j,k∈H: ∈H: otherwise µ(j)µ 2 (k)µ( ) -12(4a i + 4)µ(j)µ(k) ∈H µ 2 ( ) -2(2a i + 5) j∈H: ∈H: ends with µ(j)µ 2 ( )µ(m) -10(4a i + 4) j∈H: ∈H: otherwise µ(j)µ 2 ( )µ(m) -4(2a i + 3)µ(j)µ(k) ,m∈H: ends with jk µ( )µ(m) -20(4a i + 4)µ(j)µ(k) ,m∈H: otherwise µ( )µ(m) -24(4a i + 4) j∈H: ,m∈H µ(j)µ( )µ(m)µ(p) + 12(4a i + 6)µ 2 (i)µ(j)µ(k) + 12(2a i + 1)µ 2 (i) j∈H: ∈H µ(j)µ( ) + 12(2a i + 1)µ 2 (i) ,m∈H µ( )µ(m) + 48µ 2 (j)µ 2 (k) -6(4a i + 4) j∈H: ∈H µ 2 (j)µ 2 ( ) -2(2a i + 5) j∈H: ∈H: ends with jj µ 2 (j)µ( )µ(m) -10(4a i + 4) j∈H: ∈H: otherwise µ 2 (j)µ( )µ(m) -4(2a i + 5) j∈H: ∈H µ 3 (j)µ( ) + 12(2a i + 6)µ(i) j,k∈H µ(j)µ 2 (k) + 48µ(i)µ(j)µ(k) ∈H µ( ) -4(2a i + 5) ,m∈H µ 3 ( )µ(m) -6(4a i + 4) ,m∈H µ 2 ( )µ 2 (m) -2(2a i + 5),m,p∈H: ends with µ 2 ( )µ(m)µ(p) -10(4a i + 4) ,m,p∈H: otherwise µ 2 ( )µ(m)µ(p) -24(4a i + 4)

  This is the case if and only if all nodes are of degree at least 2, or all nodes of degree 1 are not the only minimum of µ on the single hyperedge they belong to. Observe the following

characterization, Lemma 4.1. Let H = (V, H) be a hypergraph, and denote H = {H 1 , ..., H m }. An independent set I = {v 1 , ..., v p } is µ-minimal if and only if for all n and all k 1 , ..., k m such that

  Having Corollary 4.1, and Propositions 4.1, 4.2 and 4.3 in hand, one can identify classes of hypergraphs H such that (H, Φ, µ) has an empty stability region for any admissible Φ.

	We start with the following elementary observation,
	Proposition 4.4. If a hyperedge of H = (V, H) contains two isolated nodes, i.e., there exist
	H ∈ H and i, j ∈ H such that d(i) = d(j) = 1, then the model cannot be stable, i.e.,
	STAB(H, Φ) = ∅ for any admissible Φ.

  Kidneys for transplantation come from two different sources: a living donor or a deceased donor. See[START_REF] Holscher | Transplanting the untransplantable[END_REF].The Living Donor: In most cases, the donor is a family member. The donor must be in excellent health, well informed about transplantation, and able to give informed consent.Any healthy person can donate a kidney safely. Deceased Donor: It is a person who has suffered brain death. The kidneys are removed and stored until a recipient has been selected.

	7.1. INTRODUCTION
	The compatibilities of Blood Types Donors are described as follows:
	Blood Type Donate Blood To Receive Blood From
	A	A, AB	A, O
	B	B, AB	B, O
	AB	AB	A, B, AB, O
	O	A, B, AB, O	O
	Kidney Transplantation:

Regardless of the type of kidney transplant-living donor or deceased donor-special blood tests are needed to find out what type of blood and tissue is present. These test results help to match a donor kidney to the recipient.

Table 7 .

 7 1: The comparison of the stationary probability on G and the simulated results of the matching model on H.Conclusion 2:In Table7.1 we emphasize, first, the speed of convergence to the steadystate (approximated by the final state -column 5), as the results of columns 4 and 5 tend to coincide. Second, when comparing the frequency of construction points for the three-bythree system to the stationary probability of an empty two-by-two system, we see that the     Y n + 4e i w.p. µ(i) 4 ; Y n + 3e i + e w.p. 4µ(i) 3 µ( ) + 2e j + 2e k w.p. 6µ(j) 2 µ(k) 2 ; Y n -2e i w.p. 6µ(j) 2 µ( ) 2 ∈ H; Y n -e i + 2e j w.p. 2µ(j) 2 µ( )µ(m) = m ∈ H ends with jj; Y n -2e i w.p. 10µ(j) 2 µ( )µ(m) = m ∈ H otherwise; Y n -e i + 2e j w.p. 4µ(j) 3 µ( ) ∈ H;Y n + e i + e j + 2e k w.p. 12µ(i)µ(j)µ(k) 2 ;

	0.25 0.27 0.25 0.23	0.05137131	0.155	0.07098765
	0.25 0.26 0.25 0.24	0.05348423	0.160	0.03767661
	0.25 0.264 0.25 0.236	0.05279672	0.17	0.05150268
	0.25 0.263 0.25 0.237	0.05294198	0.156	0.04811018
	0.25 0.265 0.25 0.235	0.05260348	0.157	0.05485314
	0.19 0.26 0.25	0.3	0.03445104	0.115	0.03767661
	0.25	0.3	0.21 0.24	0.03740660	0.109	0.03757694
	0.25 0.32 0.19 0.24	0.01779171	0.062	0.03745972
	0.17 0.26 0.25 0.32	0.01639216	0.035	0.03767661
	0.18 0.32 0.32 0.18	0.00542774	0.018	0.24609380
	0.197 0.253 0.25	0.3	0.03558512	0.111	0.01178613

n -e i + 2e k w.p. 2µ(j)µ(k) 2 µ( ) ∈ H ends with kk; Y n -e i + e j + e k w.p. 10µ(j)µ(k) 2 µ( ) ∈ H otherwise; Y n -2e i w.p. 12µ(j)µ(k)µ( ) 2 ∈ H; Y n -e i + 2e w.p. 2µ(j)µ( ) 2 µ(m) = m ∈ H n + 2e i + e j + e k w.p. 12µ(i) 2 µ(j)µ(k); Y n + e i w.p. 12µ(i) 2 µ(j)µ( ) ∈ H; Y n + e i w.p. 12µ(i) 2 µ( )µ(m) = m ∈ H; Y n n -e i + 2e w.p. 2µ( ) 2 µ(m)µ(p) = m = p ∈ H ends with ; Y n -2e i w.p. 10µ( ) 2 µ(m)µ(p) = m = p ∈ H otherwise; Y n -2e i w.p.

> 0, for any w such that

These NCOND are necessary stability conditions. An analog result holds in (3.3). In particular, the latter condition is empty if and only the compatibility graph is bipartite (which justifies why items enter by pairs in BM and EBM models -otherwise the model could not be stabilizable).

The stability region of the model denoted by STAB(G, Φ), is then defined as the set of measures µ such that the model is positive recurrent (see Section 2.4). Also, in [START_REF] Mairesse | Stability of the stochastc matching model[END_REF] the authors have proven that:

• the matching model may be stable if and only if the matching graph in non bipartite,

• G graph non bipartite then the model is always stable under Φ=ML, i.e., STAB(G, ML) = NCOND(G),

• G complete p-partite graph, p ≥ 3 (which is called in [START_REF] Mairesse | Stability of the stochastc matching model[END_REF] separable graph of order p), then for all Φ, µ ∈ NCOND(G), the model (G, Φ, µ) is stable, i.e., ∀Φ, STAB(G, Φ) = NCOND(G).

However, [START_REF] Moyal | On the instability of matching queues[END_REF] shows that, aside from a particular class of graphs, random policies are never maximal, and that there always exists a strict priority policy that isn't maximal either. Then, by adapting the dynamic reversibility argument of [START_REF] Adan | Reversibility and further properties of the FCFM Bipartite matching model[END_REF] to the GM models, [START_REF] Moyal | A product form and a sub-additive theorem for the general stochastic matching model[END_REF] shows that the matching policy First Come, First Matched (FCFM) is maximal and derives the stationary probability in a product form. More recently, following the work of [START_REF] Nazari | Optimal control of general dynamic matching systems[END_REF], matching policies of the broader Max-Weight type (including 'Match the Longest') are shown to be also maximal and drift inequalities allow to bound the speed of convergence to the equilibrium, and the first two moments of the stationary state.

On another hand, since a matching queue is easily seen, the stability region of a discretetime stochastic model can be studied by embedding it in an appropriate continuous-time model. Thus, the continuous-time counterparts of the results in [START_REF] Mairesse | Stability of the stochastc matching model[END_REF] hold for matching queues and vice versa. The advantage of the continuous-time setting is that powerful fluidlimit techniques can be employed, which greatly facilitate the stability analysis.

Fluid models are arguably the most effective tool to prove that a queueing network is stable, and can also be employed to prove the instability of such networks. Specifically, following [START_REF] Rybko | Ergodicity of stochastic processes describing the operations of open queueing networks[END_REF][START_REF] Dai | On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models[END_REF] they have found that, under mild regularity conditions, if all the (subsequential) fluid limits of the queues, for all possible initial conditions, converge to 0 in a finite time w.p.1, then the system is stable, in the sense that the underlying queue process is

Main results

We now state the main results of this chapter. Similarly to [START_REF] Mairesse | Stability of the stochastc matching model[END_REF], we will be led to consider the set NCOND(G) = {µ ∈ M (V) : ∀ I ∈ I(G), µ (I) < µ (E (I))} .

(5.1)

Let us immediately observe that Lemma 5.1. For any connected multigraph G, we have that

Where Ǧ = (V, Ě) is the maximal subgraph of G (see Definition 1.13).

Proof. The result simply follows from the obvious facts that I(G) ⊂ I Ǧ and that, for any

It is stated in Theorem 1 of [START_REF] Mairesse | Stability of the stochastc matching model[END_REF] that, if G is a graph, the set NCOND(G) is non-empty if and only if G is not a bipartite graph. This result can be generalized to multigraphs:

Proposition 5.1. For any connected multigraph G, we have that

Proposition 5.1 is proven in Section 5.3. From Proposition 2 in [START_REF] Mairesse | Stability of the stochastc matching model[END_REF], whenever G is a graph (i.e., V 1 = ∅), the set STAB(G, Φ) is included in NCOND(G) for any admissible policy Φ.

In other words, for any measure µ, belonging to NCOND(G) is necessary for the stability of the system (G, Φ, µ), for any Φ. A similar result holds for any multigraph G:

Proposition 5.2. For any connected multigraph G = (V, E) and any admissible matching policy Φ, we have that

Proof. The proof is analog to that of Proposition 2 in [START_REF] Mairesse | Stability of the stochastc matching model[END_REF].

Hence, the notion of maximality of a matching policy is:

Definition 5.1. For any connected multigraph G that is not a bipartite graph, a matching policy Φ is said maximal if the sets STAB(G, Φ) and NCOND(G) coincide.

Whenever G is a graph, Theorem 1 of [START_REF] Moyal | A product form and a sub-additive theorem for the general stochastic matching model[END_REF] shows, first, that the policy 'First Come, First Matched' (FCFM) is maximal, and second, that the stationary probability of the chain {W n ; n ∈ N} can be expressed in a remarkable product form. We generalize this result to multigraphs:

Example 5.4. Last, consider the multigraph G represented in (the middle figure of) Figure 5.1. The maximal subgraph is complete 3-partite, and we readily obtain that

Then, from Theorems 5.1 and 5.2, the respective stability regions STAB(G, FCFM) and STAB(G, MW) under First Come, First Matched, or any Max-Weight policy coincide with the set NCOND(G). From Theorem 5.3 (i), for any policy Φ on G according to which all items prioritize 3-items over 5 items is maximal, i.e., STAB(G, Φ) = NCOND(G). From Theorem 5.3 (ii), any policy Φ on G is such that NCOND( Ǧ) ⊂ STAB(G, Φ). Last, from Proposition 5.3, any policy Φ on Ĝ giving priority to 3-items over 5 and 5-items is maximal, whereas for any matching policy Φ and any measure μ on V extending a measure of NCOND( Ǧ), the model ( Ĝ, Φ, μ) is stable.

Proof of Proposition 5.1

Throughout this section, fix a connected multigraph G = (V, E), where V = V 1 ∪ V 2 , and denote its minimal blow-up graph by Ĝ = ( V, Ê), where V = V ∪ V 1 . We first have the following, Lemma 5.2. For any µ ∈ M (V) we have that

where μ1/2 is the extended measure of µ such that

(5.4)

Proof. For any

Let us prove first the implication ⇐=: Let μ1/2 ∈ NCOND( Ĝ) and

we get that

We can now turn to the proof of Proposition 5.1:

Proof of Proposition 5.1. If G is a bipartite graph, then it follows from Theorem 1 in [START_REF] Mairesse | Stability of the stochastc matching model[END_REF] that NCOND(G) is empty. Regarding the converse, suppose that G is not a bipartite graph.

Then, Ĝ cannot be a bipartite graph neither. Indeed, there are two cases:

, then Ĝ = G and so is not a bipartite graph.

includes the triangle i-i-j-i. (Observe that j necessarily exists since G is supposed connected with at least two nodes.) In particular, Ĝ is not a bipartite graph.

As a consequence, again from Theorem 1 in [START_REF] Mairesse | Stability of the stochastc matching model[END_REF], NCOND( Ĝ) is non-empty and thus, from Lemma 5.2, the set NCOND(G) is also non-empty.

Proof of Theorem 5.1

Let us recall that the multigraph G = (V, E) is connected but is not a bipartite graph, with |V| ≥ 2. Then, in particular, NCOND(G) = ∅ (cf. Proposition 5.1). Our product form result, Theorem 5.1, follows from a reversibility scheme that generalizes to the case of multigraphs, the one constructed in [START_REF] Moyal | A product form and a sub-additive theorem for the general stochastic matching model[END_REF]. In fact, we propose a proof that is simpler, at some points, than the one in [START_REF] Moyal | A product form and a sub-additive theorem for the general stochastic matching model[END_REF]. We reproduce hereafter the main steps of this construction for easy reference, and only develop exhaustively the points that are specific to the present context, or based on different arguments.

Hereafter, we denote by P W , the transition operator of the buffer-content Markov chain, that is, for all w, w ∈ W, we write P W (w, w

for any n ∈ N.

Two auxiliary chains

As in section 3.2 of [START_REF] Moyal | A product form and a sub-additive theorem for the general stochastic matching model[END_REF], we first need to define two auxiliary Markov chains. For this, let us denote by V an independent copy of V, i.e., a set with the same cardinal formed with copies of elements of V. We set V = V ∪ V, and we define, for w ∈ V * ,

For a ∈ V, we will use the notation a = a.

Definition 5.6. We define the backward detailed chain as the process (B n ) n∈N with values in V * given by B 0 = ε and, for any n ≥ 1,

• if W n = ε (i.e., all the items arrived up to time n are matched at time n), then B n = ε,

• otherwise, let i(n) ∈ [ [1, n]] be the arrival time of the oldest item still in the buffer, then, the word B n is the word of length n -i(n) + 1, defined, for any

by

In other words, the word B n gathers the class indexes of all unmatched items entered up

to n, at the places corresponding to their arrival times, and the copies of the class indexes of the items matched before n, but after the arrival of the oldest unmatched item at n, at the place corresponding to the arrival time of their respective match.

Observe that by the construction of (B n ) n∈N , for all n ∈ N, the word B n necessarily contains all the letters of W n . More precisely, for any n ∈ N, W n is the restriction of the word B n to its letters in V. Furthermore, (B n ) n∈N is also a Markov chain since for any n ≥ 0, the value of B n+1 can be deduced from that of B n and from the class V n+1 of the item entered at time n + 1.

A state w ∈ V * is said to be admissible for (B n ) n∈N if it can be reached by the chain (B n ) n∈N , under the FCFM policy. We set

The following result can be proven exactly as Lemma 1 in [START_REF] Moyal | A product form and a sub-additive theorem for the general stochastic matching model[END_REF].

Lemma 5.3. Let w = w 1 . . . w q ∈ V * . Then, w ∈ B if and only if w 1 ∈ V and for

As a consequence of Lemma 5.3, any word w ∈ B can be written as

The transition operator of the chain {B n ; n ∈ N} is denoted by P B , that is, for all w, w ∈ B, we write P B (w, w ) = P [B n+1 = w | B n = w], for all n ∈ N. Definition 5.7. We define the forward detailed chain as the process (F n ) n∈N with values in V * given by F 0 = ε (the empty word) and, for any n ≥ 1,

• if W n = ε (i.e., all the items arrived up to time n are matched at time n), then F n = ε,

• otherwise, let U n be the set of items arrived before time n that are not matched at time n (note that U n is non-empty since W n = ε). Also, set

In other words, the word F n contains the copies of all the class indexes of the items entered up to time n and matched after n, at the place corresponding to the arrival time of their respective match, together with the class indexes of all items entered after n and before the last item matched with an item entered up to n, and not matched with an element entered before n, if any, at the place corresponding to their arrival time. Similarly to [START_REF] Moyal | A product form and a sub-additive theorem for the general stochastic matching model[END_REF], we make the three following simple observations:

• If F n is a.s. an element of V * for all n ∈ N.

As for the backward chain, we say that a state w ∈ V * is admissible for (F n ) n∈N if it can be reached by the chain (F n ) n∈N , under the FCFM policy. Then, we set

and we denote by P F the transition operator of the chain {F n ; n ∈ N} on F. For any word w = w 1 . . . w n ∈ V * , let us define its reversed-copy by

Thus, Ψ is a bijection and its inverse function is Ψ -1 = Ψ.

Lemma 5.4. The map

is well-defined and bijective.

Proof. Exactly as in Lemma 2 in [START_REF] Moyal | A product form and a sub-additive theorem for the general stochastic matching model[END_REF], it can be proven that w ∈ F if and only if Ψ(w) ∈ B.

This guarantees that the mapping Φ is well-defined and surjective. It is injective because Ψ clearly is so.

Let us define a measure ν on V * by ν(ε) = 1 and

We can use the measure ν defined above to establish the following link between the dynamics of the chains (B n ) n∈N and (F n ) n∈N . The following result can be established exactly as Lemma 3 in [START_REF] Moyal | A product form and a sub-additive theorem for the general stochastic matching model[END_REF],

Proposition 5.4. For any (w, w ) ∈ B 2 , we have that

We will exploit the local balance equations of Proposition 5.4 to derive stationary distributions of these two Markov chains. To this end, the following technical lemma will simplify the proofs.

Lemma 5.5. The measure ν defined by (5.6) satisfies the following properties:

For any

Proof. The first point follows from the definition of ν and the second point is a direct consequence of its multiplicative structure. Regarding the third point, observe that

We can now state the following result, Proposition 5.5. Suppose that µ ∈ NCOND(G). Then, the chains (B n ) n∈N and (F n ) n∈N are positively recurrent and admit respectively the restrictions on B and on F of ν (that is, ν B (w) = ν F (Φ(w)) = ν(w), for any w ∈ B) as unique stationary measure (up to a multiplicative constant), respectively on B and F.

Proof. Let µ ∈ NCOND(G).

Step 1: we first prove that ν B is a stationary measure for the chain (B n ) n∈N .

For this, let us fix w ∈ B. Then we have that

where the first equality follows from Proposition 5.4, the second from the fact that ν B ←w = ν B (w ) and the last, from Lemma 5.4. Thus, for all w ∈ B, we have that

which means exactly that ν B is a stationary measure for the chain (B n ) n∈N .

Step 2: we now prove that ν B (B) < ∞.

By Lemma 5.3, we know that w ∈ B \ {ε} if and only if w belongs to a set

where b 1 , . . . , b q are elements of V such that {b 1 , . . . , b q } ∈ I Ǧ and such that for all

, and where we denote

Equivalently, by highlighting only the first occurrence of each letter of V appearing in w and employing a similar notation to (5.7) we obtain that w ∈ B \ {ε} if and only if w belongs to some set of the form

where I = e 1 , ..., e |I| ∈ I Ǧ , σ ∈ S |I| , and where we denote

In view of assertion (1) of Lemma 5.5, we have that for all i ∈ 1, k ,

Since {e σ(1) , . . . , e σ(i) } ∈ I( Ǧ), we have, by definition, that {e σ(1) , . . . , e σ(i

and since the measure µ satisfies NCOND(G), it follows that

and thereby, that ν B (B i ) < 1. As a conclusion, applying successively all assertions of Lemma 5.5, we obtain that for all such I and σ,

.

The set B is the disjoint union of the sets C I,σ , for I in the finite set I Ǧ , and σ in the finite set S |I| . It follows that ν B (B) is finite, and given by

. (5.8)

Step 3: we conclude with the positive recurrence of the two chains.

By the results above, the chain (B n ) n∈N has a stationary probability distribution on B, which is given by the measure ν B normalized by ν B (B).

Observe that the chain is irreducible on B. To see this, let w ∈ B and first observe that the empty word ε leads to w with positive probability for the transitions of {B n ; n ∈ N} (this is the constructive argument proving Lemma 5.3 -see the proof of Lemma 1 in [START_REF] Moyal | A product form and a sub-additive theorem for the general stochastic matching model[END_REF]).

Conversely, denoting by b 1 , . . . , b q the elements of V(w), it is easy to see that the word w leads to the empty word with positive probability for the transitions of {B n ; n ∈ N} : indeed, by the definition of the policy FCFM, if the chain is in the state w, then it will reach the empty state after exactly q steps, by seeing the successive arrivals of q elements of respective classes in E(b 1 ), E(b 2 ), . . . , E(b q ), which concludes the proof of irreducibility.

It then follows that the chain {B n ; n ∈ N} is positively recurrent on B and that its stationary probability distribution is unique. Consequently, ν B is the unique stationary measure (up to a multiplicative constant) of the chain (B n ) n∈N . Now, as in step 1, we obtain that for all w ∈ B,

Using Lemma 5.4, we deduce that ν F is a stationary measure for the chain (F n ) n∈N . Then, step 2 shows equivalently that ν F (F) < ∞. So, the chain (F n ) n∈N has a stationary probability distribution on F, which is given by the measure ν F normalized by ν F (F).

Similarly as above, we can check that the chain {F n ; n ∈ N} is irreducible on F. First, the empty word leads with positive probability to any element w ∈ F, as can be checked using the same constructive argument as in the proof of Lemma 5. and let r = q + q i=1 k i be the length of w. Then, going forward in time, perform the FCFM matching of the 'unmatched' elements of respective classes in V(w). Say there remains in the system, at time n + r, unmatched elements denoted c 1 , c 2 , . . . , c in their order of arrivals. Then, the chain can return to the empty state in particular if the first arrivals after time n + r (excluded) are of respective classes in E(c 1 ), E(c 2 ), . . . , E(c ). This concludes the proof of irreducibility.

As a consequence, the chain {F n ; n ∈ N} is positively recurrent on F and its stationary probability distribution is unique. Consequently, ν F is the unique stationary measure (up to a multiplicative constant) of the chain (F n ) n∈N , which concludes the proof.

Positive recurrence of (W n ) n∈N

The Markov chain (W n ) n∈N can be seen as the projection of the chain (B n ) n∈N on V * . In order to obtain the stationary probability distribution of (W n ) n∈N from the one of (B n ) n∈N , we will use the following lemma: Then, if a measure µ is invariant for P Y , the measure µ defined by µ (a ) = µ(p -1 ({a })) for all a ∈ S , is an invariant measure for P Y on S .

Concluding the proof

We first show that STAB(G, FCFM) = NCOND(G). First, we know from Proposition 5.2 that STAB(G, FCFM) ⊂ NCOND(G). Also, from Proposition 5.1, NCOND(G) = ∅, since G is not a bipartite graph. Then, for all µ ∈ NCOND(G), by Proposition 5.6, the chain (W n ) n∈N is positively recurrent on W. So, NCOND(G) ⊂ STAB(G, FCFM), and therefore STAB(G, FCFM) = NCOND(G).

We now fix µ ∈ NCOND(G), and compute explicitly the unique stationary probability

given by (5.2). Now, fix w = ε in W. By (5.7), we know that if w = w 1 . . . w q ∈ W, q ≥ 1,

, for all i ∈ 1, q . Applying Lemma 5.5 and observing that for all i, µ

The proof is complete.

Remaining proofs

Throughout the section G is a connected multigraph, Ǧ is its maximal subgraph and Ĝ denotes its minimal blow-up graph. To simply compare a (G, Φ, µ) system with the two corresponding matching models on graphs ( Ĝ, Φ, μ) and ( Ǧ, Φ, µ), let us add a "hat" (resp.

a "check") to all characteristics of the second (resp. the third) system: in particular, we denote, for all n, by Vn (resp. Vn ), the class of the item entering in the ( Ĝ, Φ, μ) resp.

( Ǧ, Φ, µ) system at time n. The natural Markov chain of the system is then denoted by ( Ŵn ) n∈N resp. ( Wn ) n∈N and its state space, by Ŵ resp. W . Specifically,

Observe that we have W ⊂ W ⊂ Ŵ.

For any measurable mapping F : W → R (resp. W → R, Ŵ → R) and any given w ∈ W (resp. ŵ ∈ Ŵ, w ∈ W), we denote by ∆F Φ µ (w) (resp. ∆F Φ μ ( ŵ), ∆F Φ μ ( w)) the drift of the chain {W n ; n ∈ N} (resp. Ŵn ; n ∈ N , Wn ; n ∈ N ) starting from w (resp. ŵ, Gathering this with (5.16) and (5.17) and then taking expectations, we obtain that

Finally, (5.11) together with (5.12), (5.15) and (5.18) give that

which concludes the proof.

Definition 5.9. Let G be a connected multigraph and Φ be an admissible matching policy on G. We say that Φ reduces Φ if, for any µ ∈ M (V), whenever the two systems ( Ǧ, Φ, µ)

and (G, Φ, µ) are in the same state w ∈ W and welcome the same arrival, then Φ and Φ induce the same choice of match, if any.

Proposition 5.8. Let G = (V, E) be a connected multigraph and Φ be a class admissible policy on G and µ ∈ M (V). Let Φ be a matching policy extending Φ on Ĝ, μ a measure extending µ on V and Φ be a policy that reduces Φ on Ǧ. Then the drift of the respective Markov chains are such that for all w ∈ W,

Proof. Fix w ∈ W. The only case in which the proof of the left inequality of (5.20) differs from that of Proposition 5.7 is when an item of class i ∈ O w enters the ( Ĝ, Φ, μ) system in a state w and we multiply each transition by it's convenient α i . Then, we now get that for

which, taking expectations and reasoning as in (5.19), leads to

We now turn to the proof of the right inequality of (5.20). Denote

Fix also n ∈ N, and denote by Vn , the class of the incoming item at time n in the ( Ǧ, Φ, µ)

system. First, similarly to (5.11), (5.12) and (5.15) we clearly get that

Then, for any w ∈ W the set I w = {i ∈ V : |w| i > 0} is an independent set of Ǧ, so by the very definition of a complete p-partite graph, there exists a unique maximal independent set Ǐ of Ǧ such that I w ⊂ Ǐ. Then, for all w ∈ W such that I w ∩ V 2 = ∅, for any n, if {W n = w} the Markov chain can make two types of moves upon the arrival of V n+1 :

• or one coordinate of

Therefore, for any V 2 -favorable matching policy Φ we have that

(5.23)

Observe that Ǐ ∩ V 2 is an independent set of G, and that Ǐc = E Ǐ ∩ V 2 . Hence (5.23) implies that

As this is true for any w outside the finite set {w ∈ W : I w ∩ V 2 = ∅}, we conclude again using the Lyapunov-Foster Theorem that STAB(G, Φ) = NCOND(G).

(ii) Fix µ ∈ NCOND( Ǧ), and an admissible matching policy Φ. Applying (5.22) to Ǧ, we obtain that for any Φ that reduces Φ, for some η > 0 we have ∆Φ µ L( w) < -η for all w ∈ W \ {ε}. Combining this with (5.20), and recalling that W ⊂ W we obtain that ∆ Φ µ L(w) < -η for all w ∈ W \ {ε}, which concludes the proof.

Proof of Proposition 5.3. (i) Remark that for any ŵ ∈ Ŵ, the set {i ∈ V : | ŵ| i > 0} is again an independent set of Ǧ. So we can apply, for any μ ∈ NCOND( Ĝ), the exact same argument as for assertion (i) in Theorem 5.3, by replacing

(ii) Let μ be an element of M ( V) whose reduced measure µ belongs to NCOND( Ǧ). Let Φ be an admissible policy on V, Φ be a policy on V such that Φ extends Φ, and Φ be a policy reducing Φ on Ǧ.

First, as in (5.22) there exists η > 0 such that ∆Φ µ L(w) < -η for any w ∈ W \ {ε}. Fix ŵ in Ŵ \ {ε}. Then define the permutation γ of V by

Let us also denote by γ( ŵ), the word obtained from w by replacing the letters of ŵ by their image through γ, in other words for all i ∈ 1, | ŵ| , γ( ŵ) i = γ( ŵi ). Observe that γ( ŵ) is clearly an element of W \ {ε}, so in view of the above observation we have that

(5.24) Now, as i and i have the same connectivity in Ĝ for any i ∈ V 1 , for all n the conditional distribution of Ŵn+1 given { Ŵn = ŵ} in the ( Ĝ, Φ, μ) system equals that of Ŵn+1 given { Ŵn = γ( ŵ)} in the ( Ĝ, Φ, μ • γ) system. In particular, we have that

(5.25)

On the other hand, as γ( ŵ) is an element of W and the measure μ • γ ∈ M ( V) clearly extends the measure µ, the right inequality of (5.20) implies that

and it follows from (5.24-5.25) that ∆Φ μ ( ŵ) < -η. As this is true for any ŵ in Ŵ \ {ε}, the proof is complete.

Discussion of results and conclusion

In this chapter, we have studied a generalization of stochastic matching models on graphs by allowing the self-loops matching. Different applications appear to this class of models such as dating sites or collaborative sites, that is, individuals of the same class can be married.

For a given multigraph G, we build its maximal subgraph Ǧ that is obtained by deleting all self-loops in G, and its minimal blow-up graph Ĝ that is obtained by duplicating each node having a self-loop by two nodes having the same neighborhood and replacing each self-loop by an edge between the node and its copy. Taken into consideration the graphs Ǧ and Ĝ which are built above, we can transmit and generalize different results to G.

The multigraph G under the matching policies FCFM and Max-Weight such that β > 0 are maximal. Also, if G is a complete p-partite multigraph, (p ≥ 2), then for p ≥ 3 or V 1 = 0, any V 2 -favorable matching policy is maximal.

Chapter 6

Fluid limits techniques for stability

Introduction

In the previous chapters, we studied the stability of stochastic matching models using Lyapunov techniques. In this chapter, we present a new approach that allows us to retrieve, and complete these results in continuous-time settings. This technique consists of speeding up time and scaling the process appropriately to obtain a deterministic and continuous approximation of the original process, which allows, among other features, to study the ergodicity properties of the process at hand. In the limit, one gets a sort of caricature of the initial stochastic process which is defined as its fluid limit.

This chapter is organized as follows: In Section 6.1 we start by providing necessary conditions of stability for graphical matching models in continuous time. In Section 6.2

we derive fluid approximations of matching models on multigraphs. In Section 6.3 we present different case studies. Last, in Section 6.4 we elaborate the fluid limit technique to study matching models on complete 3-uniform hypergraphs and complete 3-uniform kpartite hypergraphs. We conclude and discuss this chapter in Section 6.5.

Necessary conditions of stability

The necessary condition of stability for discrete-time stochastic matching models on graphs was recalled in Section 3.4. For all G = (V, E) it reads as follows, NCOND(G) := µ with support V : µ(I) < µ(E(I)) for all I ∈ I(G) . (6.1)

The first question that arises is to find an analog of (6.1) for continuous-time models, that is, in the context of matching queues, as defined in section 2.5 (recall the notation therein).

The following condition was introduced in [START_REF] Moyal | On the instability of matching queues[END_REF]: for any matching graph G,

Fix a graph G = (V, E), a class-admissible matching policy Φ, and an arrival vector

Then, it is easily seen that µ λ defines a probability measure on V. Further, if we denote for all n ≥ 1, by A(n) := {A n (i), i ∈ V} the vector tracking the number of items in the buffers of all nodes up to time n in the discrete-time system associated to G, Φ and µ λ . On another hand, let N be the superposition of the arrival Poisson processes in the continuoustime matching system associated with G, Φ and λ. Then, it is immediate that we have the identity in distribution Q t = A(N (t)). As there are finitely many Poisson processes in the continuous-time model, the sojourn time of the corresponding CTMC is of a rate that is bounded away from zero. This implies that Q is positive recurrent if and only if A is so, see [START_REF] Kulkarni | Modeling and analysis of stochastic systems[END_REF]Theorem 6.18]. Consequently, relating (6.1) to (6.2) we get that the stability region of the continuous-time model is included in NCOND C (G).

We now use fluid-limit technique to derive precisely the stability region of continuoustime models. A throughout presentation of the following section can be found e.g. in [START_REF] Moyal | On the instability of matching queues[END_REF].

Fluid Stability

Fix a multigraph G = (V 1 ∪ V 2 , E), a matching policy Φ of the priority type and an arrival vector λ. Observe that for all t ≥ 0, for all i ∈ V, Q i (t) increases by 1 for each class-i arrivals such that Q j (t) = 0 for any j ∈ E(i). On another hand, Q i (t) decreases by 1 (when it is positive) for any class-j arrival with j ∈ E(i), such that Q k (t) are empty for any k ∈ E(j) such that j gives a higher priority to k over i.

The state space in CTMC is then as follows:

For each i ∈ V, we introduce the following sets,

O i := {z ∈ E : z j = 0 for all j ∈ E(i)};

Φ j (i) := {k ∈ E(j); j gives priority to k over i according to Φ} ;

(6.4)

Marginal process corresponding to a particular node. Fix a matching node i 0 of G. Let

For x, y ∈ E, denote by A(x, y) the infinitesimal generator of the queue process Q. For any z ∈ E such that z i 0 > 0, the only positive terms A(z, y), y ∈ E, are given by

Let R := R i 0 = {R(t) : t ≥ 0} denote the restriction of the process Q to the nodes of R, i.e.,

Define the set

Conditionally on the i 0 -th coordinate of Q being positive, the process R clearly coincides in distribution with a Markov process X on E R . The latter will be termed marginal Markov process associated to node i 0 . The idea is as follows: using a stochastic averaging principle, as in [START_REF] Kurtz | Averaging for martingale problems and stochastic approximation[END_REF], showing that the marginal process reaches its stationary state immediately at fluid scale. The drifts of the fluid limit of Q will then be a function of this stationary measure.

The FWLLN. We consider the sequence of fluid-scaled processes { Qn : n ≥ 1},

is always zero or one, so the i-th coordinate of the fluid limit Q is necessarily null at all times. Moreover, it is immediate to observe the following, Corollary 6.2. For any class-admissible policy Φ, the conclusions of Theorem 6.1 and Corollary 6.1 remain valid for a continuous-time model (G, Φ, λ) C on a multigraph G if we assume that (6.9) holds for some i 0 ∈ V 2 .

In the Section 6.3 below, we will study examples of multigraphs for which the stationary probability of the marginal process can be explicitly computed, and so an explicit fluid limit and an explicit necessary condition of stability can be derived, respectively using Theorem 6.1 and Corollary 6.2. Moreover, using fluid stability arguments as in [START_REF] Dai | On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models[END_REF] will also prove that the latter conditions are also sufficient, thereby providing the exact stability region of the models under consideration.

Multigraphical cases study

In this section we present different examples of multigraph E) and the corresponding matching queues (G, Φ, λ) C , for the arrival-rate vector λ :

and a priority policy Φ that is depicted by the arrows on each dedicated figure. We deduce the precise stability regions of the corresponding stochastic matching models using the above fluid limit results.

Pendant graphs with a self-loop

In the subsection below, we present various multigraphs that consist of a pendant graph with a self-loop on a given vertex.

Pendant graph with a self-loop on the vertex 2

Consider the multigraph G depicted on Figure 6.

Proposition 6.1. Let G be the pendant graph with a self-loop on the vertex 2 and Φ the matching policy depicted on Figure 6.1. Consider an arrival-rate vector λ ∈ NCOND C (G),

i.e.,

Now, for all t ≥ 0 we have, Q1 (t) = Q1 (0) + (λ 1 -λ 3 -λ 4 ) t, ∀t > 0. Then, as a result of the observation above, there exists t 0 > 0 such that Q1 (t) < 0 for all t ≥ t 0 .

Similarly, we deduce that there exists t 1 > 0 such that Q2 (t) < 0 for all t ≥ t 1 . We conclude that there exists t ≥ t 0 ∨ t 1 the prelimit process Q i , i = 1, 2 have drifts towards 0 whenever any them is striclty positive, then Q1 and Q2 will remain fixed at 0 after hitting that state. Thus the ergodicity of the sytem follows again from [START_REF] Dai | On positive Harris recurrence of multiclass queueing networks: a unified approach via fluid limit models[END_REF]Theorem 4.2].

Observe that, the complete 3-uniform k-partite hypergraph is just the complete 3-uniform hypergraph of order k, where all the sets I 1 , ..., I k are of cardinality 1 (i.e., there are no replica). In particular case the complete 3-uniform 4-partite hypergraph is the complete 3-uniform hypergraph of order 4.

Discussion of results and conclusion

In this chapter, we have generalized stochastic matching models to the continuous-time settings. Items of different classes arrive at the system according to an independent Poisson process of intensity λ. We addressed a new technique that allows us to explicitly derive the stability region of the models at hand, by using fluid limits techniques, to prove the existence of a local steady-state, rather than applying Lyapunov techniques. The scaling consists of speeding up time by the norm of the initial state. The behavior of such rescaled stochastic processes is analyzed when the scaling parameter goes to infinity. In Corollary 6.2, we generalized the [START_REF] Moyal | On the instability of matching queues[END_REF]Theorem 4] to multigraphs. The main difference of graphs, that is, for

is always zero or one, so the i-th coordinate of the fluid limit Q, that is, necessarily null at all times.

Moreover, we have studied several examples of multigraphs for which the stationary probability of the marginal process can be explicitly computed. We have studied some cases of pendant graph with a self-loop on a vertex and we distinguish that the stability region is strictly included in the necessary condition NCOND C . However, we retrieve the results of Theorem 5.3 dedicated to the exact stability of the model by considering the complete bipartite graphs with a self-loop on a vertex with the V 2 -favorable matching policy.

In Section 6.4, also by using fluid limit arguments, we provided the exact stability region to the model for complete 3-uniform hypergraphs of order 4.

Chapter 7

Comparison of models for organ transplant applications

Introduction

A blood type (also called a blood group) is defined as the classification of blood-based on the presence or absence of inherited antigenic substances on the surface of red blood cells (RBCs). A series of related blood types constitute a blood group ABO system, see [START_REF] Watkins | Blood-group substances[END_REF].

We set the blood types as follows:

• Blood Type A -If the red blood cell contains only "A" molecules.

• Blood Type B -If the red blood cell contains only "B" molecules.

• Blood Type AB -If the red blood cell contains a mixture of molecules "A" and "B".

• Blood Type O -If the red blood cell has neither "A" nor "B" molecules.

Donating Blood by Compatible Type

Blood groups are very important when a transfusion is required. During the transfusion, the patient must receive a blood that is compatible with his/her own. If the blood types do not match, the red blood cells will clump together and form clots that can block blood vessels and cause death.

If two different blood groups are mixed, the blood cells can clump together in the blood vessels, causing potentially fatal diseases. Therefore, it is important to match blood types before performing transfusions. In emergencies, blood group O may be given because all blood groups will accept it. However, there is always a risk. See [START_REF] Harm | Immunologic risks of whole blood: ABO compatibility, Dalloimmunization, and transfusion-related acute lung injury[END_REF].

Proposition 7.4. Consider the hypergraph H = (V, H) . Then, for all matching policy Φ the sets STAB(H, Φ) and N - 3 (H) coincide, in other words the general stochastic matching model (H, Φ, µ) is stable if and only if µ satisfies condition (7.7). In other words we have

Proof. As H is a complete 3-uniform hypergraph of order 4, the result follows from Theorem 4.1.

Comparaison between STAB(G, Φ) and STAB(H, Φ)

To summarize, we obtain that the stability region of the two-by-two matching system is STAB(G, Φ) given by (7.3), whereas the stability region of the three-by-three matching system is STAB(H, Φ), given by (7.8).

Let us observe that the two regions are not included in one another. Indeed, it is easily checked that the probability measure µ(1) = 0.25, µ(2) = 0.35, µ(3) = 0.2 and µ(4) = 0.2, is an element STAB(G, Φ) but not of STAB(H, Φ). On the other hand, the probability measure µ(1) = 0.3, µ(2) = 0.2, µ(3) = 0.2 and µ(4) = 0.3 clearly belongs to STAB(H, Φ), but is not an element of STAB(G, Φ).

Conclusion 1:

Take the stability of the system as a primary performance criterion. Then, the one-by-one matching is never stable. Second, it is preferable to perform matchings twoby-two in some cases, and matchings three-by-three in other cases.

The intersection between the two stability regions is given by

The question arising now is the following: suppose that µ satisfies (7.9), that is, it belongs to both STAB(G, Φ) and STAB(H, Φ), implying that both systems are stable. Considering a secondary performance criterion, the frequency of construction points, that is, of visits to the zero state, what is the best matching procedure between two by two and three by three matchings?

We saw in Section 7.4 that the probability of finding an empty system in steady-state can be given in closed form for the two-by-two matching system. However, such a result is, to date, not available for the three-by-three system. We then resort to simulations to compare the two procedures.

first one seems to perform better in some cases, while the second performs better for some other values of µ.

Discussion of results and conclusion

In this chapter, we have proposed simple modeling of kidney transplant systems using stochastic matching models. We have shown that models on various matching structures (bipartite models, general models on graphs, and models on hypergraphs) are suitable to various contexts. In the context of cross-transplants, a simple case study has shown that there is no clear hierarchy between cross-transplants by pairs of couples (matchings two-bytwo) and cross-transplants by triplets of couples (matching three by three) when it comes to comparing the stability regions. In some cases, one system is stable while the other is not.

Second, we show that the same remark holds if we compare the frequency of construction points in simulated three-by-three systems to the (exact) value of the steady-state probability of the two-by-two system being empty: the first performs better for some values of µ, while the second performs better otherwise. Moreover, we do not understand which is the best matching procedure.

Conclusion and perspectives

In this thesis, we have studied a generalization of stochastic matching models on the graph, by allowing the matching structure to be a hypergraph or multigraph. This class of models appears to have a wide range of applications in operations management, healthcare, and assemble-to-order systems. After formally introducing the model, we have proposed a simple Markovian representation, under IID assumptions. We have then addressed the general question of stochastic stability, viewed as the positive recurrence of the underlying Markov chain. For this class of systems, solving this elementary and central question turns out to be an intricate problem.

In this thesis, the stochastic matching model in discrete-time is formally defined as follows: items enter the system by a single. On other hand, in continuous-time items enter the system according to an independent Poisson process of intensity λ > 0. The arrivals get matched by groups of 2 or more (hypergraphical cases), following compatibilities that are represented by a given hypergraph and by groups of 2 with possible compatibility with itself (multigraphical cases). A matching policy determines the matchings to be executed in the case of a multiple-choice, and the unmatched items are stored in a buffer, waiting for a future match.

bility region for complete 3-uniform k-partite hypergraph. Moreover, we demonstrated a lower bound for the stability region for the incomplete 3-uniform hypergraphs for a matching policy ML. For this, we resorted to ad-hoc multi-dimensional Lyapunov techniques in discrete-time (each step an item enters the system).

In this thesis, we have also studied a generalization of stochastic matching models on graphs by allowing the self-loops matching, that is, a stochastic matching model on multigraphs. Given a multigraph G, its maximal subgraph Ǧ obtained by deleting all self-loops in G and the minimal blow-up graph Ĝ obtained from G by duplicating each node having a self-loop by two nodes having the same neighborhood and replacing each self-loop by an edge between the node and its copy. From that, we transmit and generalize several results that are known for Ǧ and Ĝ to their multigraphs.

Also, in this context, we have provided the exact stability region under FCFM and MW policy such that β > 0. Given a multigraph G = (V 1 ∪V 2 , E), we introduced a new matching policy called V 2 -favorable, that is, for any arrival items always prioritizes to match with an item in V 2 over an item in V 1 .

In addition, we have proved that if Ǧ is a complete p-partite graph, (p ≥ 2), then for p ≥ 3 or V 1 = 0, any V 2 -favorable matching policy is maximal.

In this thesis, we have also studied a new technique that allows us to find the stability of the model by using the fluid limits in continuous-time (items of the various classes enter the system following the independent Poisson process of designated intensities). This new method consists of speeding up the time and rescaling the process to get a sort of caricature of the initial stochastic process. We provide further results that are in agreement with the previous results. The advantage of the continuous-time setting is that powerful fluid-limit techniques can be employed, which greatly facilitate the stability analysis. Indeed, we have also studied several cases of multigraphs such as pendant graphs with a self-loop on such vertex, we proved a lower bound of stability region. In other words, the model is stable if and only if the necessary condition for stability on continuous-time NCOND C holds together with certain conditions. Moreover, we retrieved the results for some specific complete bipartite graphs with a self-loop on such vertex for V 2 -favorable.

Further, using the fluid limits technique, we provided the exact stability region of the model on complete 3-uniform hypergraphs of order 4.

To illustrate the practical relevance of our results, we also have studied an application of the stochastic matching model that addressed particular cases of living donors in the context of cross-matching. In that case, the items enter the system by couples (X, Y ) of family members, the first component X represents the 'giver' and the second component Y represents the 'receiver'. The problem consists of studied a special case in three types of matching on various matching structures:

• bipartite graphs (matching one-by-one);

• general graphs (matching two-by-two);

• complete 3-uniform hypergraphs (matching three-by-three).

We studied the performance criterion between the two-by-two matching system and threeby-three matching system of the frequency of visits to zero state, to distinguish what is the best matching procedure. Motivated by a simulation of one thousand trajectories of threeby-three, we see that the two-by-two seems to perform better in some cases, while three-bythree performs better for some other values of µ. In this instance, we cannot conclude which is the best.

Perspectives

All the results obtained in this thesis, are according to some hypotheses: stochastic matching model on hypergraphs and multigraphs, stability region, steady-state, and so on. There is still much to do regarding this class of systems. Let us give a few directions of research that we are currently following, or aim to follow in a near future:

• Finding an explicit form of the stationary probability of the chain {W n ; n ∈ N} of the model (H, FCFM, Φ).

• Comparing the necessary conditions of stability of the model (H, FCFM, Φ) between them.

• Applying the proposed matching model on hypergraphs and multigraphs for several domains of applications.

• Comparing the simple hypergraphs, of the optimal policy with those obtained by the "Greedy Primal-Dual" optimization algorithms (Nazari and Stolyar, 2017), a dynamic control strategy introduced to maximize the utility of queue networks waiting subject to stability, which turns out to be (asymptotically) optimal in this case.

• Comparing the matching policies for the models on the hypergraphs and the determination of an optimal matching policy: MW? In which way?

• Determining the exact zones of stability of the random pairing models on particular cases of hypergraphs, in particular for small non-trivial hypergraphs such as the Fano plane (the projective plane of size 7) or the models representing the networks of cross kidney donation with loop.

• Generalizing the results of Theorem 4.1, to the complete k-uniform hypergraphs. In that case, we conjecture that the stability region is equal to N - 3 (H) = {µ, µ(i) < 1/k, i ∈ V}.

We believe that the present thesis represents a good starting point for a fruitful avenue for research on such systems.

Appendix

The transitions for the proof of Theorem 4.1 (i) First, for any i ∈ J, and any integer x i ≥ 2, the chain {Y n ; n ∈ N} makes the following transitions from state

Y n + 4e i w.p. µ(i) 4 ; Y n + 3e i + e j w.p. 4µ(i) 3 µ(j); Y n + 2e i + 2e j w.p. 6µ(i) 2 µ(j) 2 ;

Y n + e i + 3e j w.p. 4µ(i)µ(j) (the input is of the form ijjj); Y n -2e i w.p. 6µ(j) 2 µ(k) 2 ; Y n -e i + 2e j w.p. 4µ(j) 3 µ(k); Y n + e j w.p. 24µ(i)µ(k)µ( )µ(j); Y n -2e i w.p. 24µ(j)µ(k)µ( )µ(m).

(7.10) (ii) For any i ∈ J, and any integer x i ≥ 2, the transitions of {Y n ; n ∈ N} from the state x i .e i can be retrieved as a similar fashion to (7.10). Set H = {i, j, k} ⊂ J, we have the following transitions,