Appariement dynamique pondéré avec des taux d'arrivée et de départ hétérogènes

Résumé

Nous étudions un problème d'appariement dynamique non bipartite. Il existe un ensemble fixe de types d'agents, et les agents d'un type donné arrivent et partent selon des processus de Poisson spécifiques au type. La valeur d'un appariement est déterminée par les types des agents appariés. Nous présentons un algorithme en ligne qui est (1/8)-compétitif par rapport à la valeur de la politique optimale a posteriori, pour des graphes pondérés arbitraires. C'est le premier résultat à atteindre un ratio compétitif constant lorsque les arrivées et les départs sont aléatoires et non annoncés. Notre algorithme traite les agents de manière hétérogène, en interpolant entre l'appariement immédiat et l'appariement différé afin d'épaissir le marché tout en continuant à apparier les agents de valeur de manière opportuniste.