Around the stability of different stochastic matching models

Les modèles d'appariements aléatoires représentent de nombreux systèmes stochastiques concrets dans lesquels des éléments de différentes classes sont appariés selon des règles de compatibilités spécifiées. Par exemple, on peut citer les systèmes dédiés à l'allocation d'organes, les sites de recherche d'emplois, de logements, etc. De tels modèles sont toujours associés à un triptyque d'éléments : un graphe connexe, dit de compatibilités, dont les sommets représentent les classes des éléments pouvant entrer dans le systèmeet dont chaque arête relie deux classes compatibles, une politique d'appariements permettant de décider, en cas d'incertitude, quels appariements vont s'effectuer à l'intérieur du système, et un taux d'arrivées selon lequel les éléments entrent en son sein. Dans cette thèse, nous considérons des graphes généralisés, c'est-à-dire que l'on autorise l'appariement de deux éléments de la même classe, et nous étendons donc à ce cadre certains résultats déjà connus dans le cas de graphes simples. La stabilité d'un système régi par un modèle d'appariements est une propriété très importante. En effet, elle assure que les admissions au sein du système étudié sont contrôlées de sorte que les éléments ne restent pas bloqués à l'intérieur et que leur nombre n'augmente pas indéfiniment. Il est donc essentiel que le taux d'arrivées des éléments permette au système d'être stable. Dans ce manuscrit, nous caractérisons de manière algébrique cette zone de stabilité pour certains modèles d'appariements (généraux, généraux avec abandons, bipartis, bipartis étendus) ou de files d'attente, dites skill-based. Par ailleurs, nous démontrons que la politique d'appariements dite First Come, First Matched (FCFM) possède la propriété d'être maximale (généralisée), c'est-à-dire que la zone de stabilité du modèle d'appariements général associé à un graphe de compatibilités et à une politique quelconque est toujours incluse dans celle associée à ce même graphe et à FCFM. Notons que cette dernière coïncide alors avec un ensemble de mesures défini par des conditions purement algébriques. Dans ce cas, la question de l'étude des mesures permettant la stabilité des systèmes régis par un modèle d'appariements revient donc à celle, plus élémentaire, de la caractérisation d'un ensemble déterministe. Nous donnons alors un moyen de construction (simple) des mesures appartenant à celui-ci, ce qui peut s'avérer très utile pour calibrer le contrôle d'accès au système. En effet, la vérification algorithmique qu'une mesure quelconque vérifie ces conditions algébriques nécessite un nombre d'opérations polynomial en le nombre de sommets du graphe, et devient donc très coûteuse à mesure que ce cardinal augmente. Nous explicitons également, sous une forme produit, l'expression de la loi stationnaire de l'évolution temporelle du contenu d'un système stable régi par un modèle d'appariements général et sous la politique FCFM, permettant, notamment, de calculer explicitement des caractéristiques à l'équilibre de systèmes concrets et d'estimer leurs performances en temps long. On peut ainsi, par exemple, calculer la taille moyenne à l'équilibre d'une liste d'attente dans le cadre de dons croisés de reins, ou encore, estimer le temps moyen d'attente sur une interface pair-à-pair ou un site de rencontres.Enfin, les taux d'appariements associés à un modèle d'appariements (général ou biparti étendu) stable sont étudiés. Ils sont définis comme étant les fréquences asymptotiques des appariements réalisés et fournissent un critère de performance des systèmes régis par de tels modèles d'appariements, de même que les propriétés de politique-insensibilité et d'équité de ces taux, qui sont également discutées.Stochastic matching models represent many concrete stochastic systems in which elements of different classes are matched according to specified compatibility rules. For example, we can cite systems dedicated to organs allocation, job search sites, housing allocation programs, etc. Such models are typically associated to a triplet of elements: a connected graph, called compatibility graph, whose vertices represent the classes of elements that can enter the system and whose edges connect two compatible classes, amatching policy which decides the matches to be concretely executed, in case of multiple choices, and an arrival rate according to which the elements enter within it. In this thesis, we consider generalized graphs, meaning that we allow the matching of two elements of the same class, and we therefore extend to this framework some results already known in the case of simple graphs.The stability of a system governed by a matching model is a very important property. It ensures that the admissions within the system under study, are regulated, so that the elements do not accumulate in the system in the long run. It is therefore essential that the arrival rate of the elements allows the system to be stable. In this manuscript, we characterize, algebraically, this stability region for some matching models (general, general with reneging, bipartite, extended bipartite) or skill-based queueing systems.Moreover, we demonstrate that the matching policy called First Come, First Matched (FCFM) has the property of being (generalized) maximal, meaning that the stability region of the general matching model associated with a compatibility graph and with any policy is always included in the one associated with this same graph and ruled by FCFM. Note that this latter then coincides with a set of measures defined by purely algebraic conditions. In this case, the study of stability of the matching model at hand boils down to the more elementary question of characterizing of a deterministic set of measures. We then givea (simple) way to construct the measures belonging to the latter set. This turns out to be very useful for admission control, as checking the algebraic conditions requires a number of operations which is polynomial in the number of vertices of the considered compatibility graph, and therefore becomes very expensive as the number of vertices grows large.We also give, in a product form, the expression of the stationary distribution of the number-in-system process of a stable system governed by a general matching model and under the FCFM policy, allowing, in particular, to explicitly calculate characteristics at equilibrium of concrete systems and to estimate their long-time performance. We can thus, for example, calculate the size average at equilibrium of a waiting list in the case of cross-donation of kidneys, or even, estimate the average waiting time on a peer-to-peerinterface or on a dating website.Finally, the matching rates associated with a stable matching model (general or extended bipartite) are studied. They are defined as the asymptotic frequencies of the executed respective matchings, and provide an insightful performance criterion for the corresponding matching systems, as well as the policy-insensitivity and fairness properties of the matching rates, which are also discussed