February 5, 2024
Jean Michel Fourneau (DAVID, UVSQ)A matching model is a triple based on a compatibility graph, a set of Poisson processes and a matching discipline. Each node of the graph is associated with a type of objects and the compatibility graph shows which objects interact. The interaction is the immediate deletion of some objects. If an arriving objet does not interact, it enters the system and wait until it can interact with someone. One of the possible applications of matching models is the kidney exchange system organized in many countries. In this talk I will show a performance paradox: adding more flexibility in the compatibility graph (i.e. adding new edges) will, for some graphs and arrival rates, lead to an increase of the total average sojourn time in the system. And this is proved for any greedy disciplines. We show this property holds for some family of graphs and is lifted for some modular constructions of graphs. As this result is mostly based on strong aggregation of Markov chains, I will begin by a short introduction of this property which is used in general to decrease the size of the models.