Jeudis de la Science - Modèles de matching stochastique généraux et leurs paradoxes, ou comment augmenter l’offre peut entrainer dans certains cas une degradation des performances globales

Les modèles de matching stochastiques servent  à compter des objets en attente d’un objet compatible avant de disparaitre ensemble. Ils permettent ainsi de représenter les déséquilibres entre producteurs et consommateurs et on trouve des exemple d’utilisation en économie, en médecine pour des affectations d’organes, ou pour des opérateurs de ride-sharing. 

Les objets ont un type et les compatibilités entre objets  sont représentées par un graphedont les noeuds sont les types et les arêtes indiquent que les objets sont compatibles. Quand plusieurs objets sont compatibles, on utilise une discipline de matching pour indiquer l’objet qui sera détruit. On ajoute également des processus d’arrivées pour chaque type d’objet. Sous des hypothèses simples sur les arrivées et la discipline, on obtient une chaine de Markov en temps continu à espace infini dénombrable. 

On dit qu’il y a paradoxe de performance quand, en ajoutant une arête au graphe de compatibilité, l’espérance du nombre total d’objet en attente augmente. Cet augmentation est paradoxale car en ajoutant des possibilités de matching, on s’attend à diminuer le nombre total d’objets en attente et à améliorer l’efficacité du système. 

On a au départ démontré ce paradoxe sur un exemple associé à la discipline First Come First Match (donc en choisissant l’objet compatible le plus ancien) pour un graphe très simple. Puis on a généralisé ce problème à toutes les disciplines gloutonnes et à une famille infinie
de graphes. 

Enfin, motivé par l’exemple des échanges de reins entre donneurs compatibles, nous avons introduit une extension du modele où les objets peuvent quitter le système sans qu’un matching puisse avoir lieu et avec un taux proportionnel à la taille de la population (un taux de mort). Ces taux de mort stabilisent le système mais des paradoxes de performances apparaissent cependant. 

Ce phénomène semble donc intrinsèque à la problématique du matching dynamique stochastique et interdit des solutions simplistes pour optimiser de tels systèmes.