Correspondance en ligne de prophet-inequality avec des applications à l'allocation d'annonces

Nous étudions le problème de la correspondance en ligne de prophet-inequality dans les graphes bipartis. Il existe un ensemble statique d'enchérisseurs et un flux en ligne d'articles. Nous représentons l'intérêt des enchérisseurs pour les articles par un graphe biparti pondéré. Chaque enchérisseur a une capacité, c'est-à-dire une limite supérieure sur le nombre d'articles qui peuvent lui être alloués. Le poids d'une correspondance est le poids total des arêtes appariées aux enchérisseurs. À l'arrivée d'un article, l'algorithme en ligne doit soit l'allouer à un enchérisseur, soit le jeter. L'objectif est de maximiser le poids de la correspondance résultante. Nous considérons ce modèle dans un cadre stochastique où nous connaissons la distribution des articles entrants à l'avance. De plus, nous permettons aux articles d'être tirés de différentes distributions, c'est-à-dire que nous pouvons supposer que le t-ième article est tiré de la distribution Dt. Contrairement au modèle i.i.d., cela nous permet de modéliser le changement dans la distribution des articles au fil du temps. Nous appelons ce cadre le Prophet-Inequality Matching en raison de la possibilité d'avoir une distribution différente pour chaque moment. Nous généralisons l'inégalité classique du prophète en présentant un algorithme avec un ratio d'approximation de 1--1/√k+3 où k est la capacité minimale. Dans le cas où k=2, l'algorithme donne un ratio serré de 1/2, qui constitue une preuve différente de l'inégalité du prophète.