Problème de Robbins

Informellement, le problème est le suivant : un recruteur travaillant dans une entreprise cherche à embaucher un secrétaire. Pour cela il va faire passer un entretien d'embauche à un certain nombre de candidats (ce nombre est fini et connu du recruteur). À la fin de chaque entretien, le recruteur attribue une note (un nombre réel) entre 0 et 1 en fonction des performances du candidat. Plus la note est proche de 0, plus le candidat est qualifié. On suppose que pour chaque candidat toutes les notes possibles sont équiprobables (les candidats ont autant de chance d'être bons que mauvais). On suppose aussi que les notes des candidats n'influent pas sur les performances des autres. A la fin de chaque entretien le recruteur doit prendre une décision irrévocable : soit il accepte le candidat et l'embauche sur le champ sans faire passer l'entretien aux prochains ; soit il refuse le candidat et alors il ne pourra plus revenir sur sa décision. Le problème consiste alors à déterminer une stratégie optimale permettant de minimiser le rang du candidat retenu (le rang étant le classement par rapport aux autres, par exemple le candidat de rang 1 est le meilleur de tous, celui de rang 2 est le deuxième meilleur, etc).

Plus formellement, soit ${\displaystyle X_{1},\dots ,X_{n}}$ des variables i.i.d de loi uniforme dans ${\displaystyle [0,1]}$. Pour tout ${\displaystyle 0\leq k\leq n}$, on pose ${\displaystyle {\mathcal {F}}_{k}:=\sigma (X_{1},\dots ,X_{k})}$ la tribu engendrée par les ${\displaystyle k}$ premières variables aléatoires ${\displaystyle X_{1},\dots ,X_{k}}$. On définit le rang absolu :

${\displaystyle R_{k}:=\sum _{i=1}^{n}\mathbf {1} _{X_{i}\leq X_{k}}}$.

On cherche alors un temps d'arrêt optimal ${\displaystyle \tau ^{*}}$ qui minimiserait la quantité ${\displaystyle V_{n}:=\inf _{\tau }\mathbb {E} [R_{\tau }]}$ où l'infimum est pris sur l'ensemble des temps d'arrêt adaptés à la filtration ${\displaystyle ({\mathcal {F}}_{k})}$.

Les premières valeurs de ${\displaystyle V_{n}}$ sont connues pour ${\displaystyle n=1,2,3,4}$[2] :

${\displaystyle V_{1}=1}$, ${\displaystyle V_{2}=1,25}$, ${\displaystyle V_{3}=1,39155\dots }$ et ${\displaystyle V_{4}=1,4932\dots }$

La complexité des calculs grandit très vite et calculer ${\displaystyle V_{4}}$ n'est pas trivial.

Un argument de «prophète»[1] permet de montrer que la suite ${\displaystyle (V_{n})}$ est croissante. De plus elle est bornée. En effet, dans le troisième problème de la secrétaire, qui est identique au problème de Robbins à la différence que le recruteur n'a accès qu'aux rangs relatifs et non aux notes des candidats, la suite associée ${\displaystyle (V'_{n})}$ est bornée. Or il est clair que ${\displaystyle V_{n}\leq V'_{n}}$ pour tout ${\displaystyle n\geq 1}$. Ainsi la suite ${\displaystyle (V_{n})}$ converge vers une limite notée ${\displaystyle V}$.

Actuellement la valeur de ${\displaystyle V}$ est inconnue et le meilleur encadrement connu est ${\displaystyle 1.909\leq V\leq 2,32614}$. La borne inférieure a été trouvée en utilisant une méthode de troncation[3] tandis que la borne supérieure a été trouvée en utilisant une stratégie à seuil sans mémoire modifiée[4].

Une stratégie à seuil sans mémoire consiste à sélectionner le candidat numéro ${\displaystyle k}$ si et seulement si sa note est inférieure à un certain seuil, sans se soucier des performances des candidats précédents (d'où l'appellation «sans mémoire»). Plus formellement, fixons une fonction de seuil ${\displaystyle s:\{1,\dots ,n\}\rightarrow [0,1]}$ telle que ${\displaystyle s(n)=1}$. La stratégie à seuil sans mémoire associée à la fonction ${\displaystyle s}$ correspond alors au temps d'arrêt

${\displaystyle \tau$ :=\inf\{k:X_{k}\leq s(k)\}} .

Par exemple en prenant

${\displaystyle s(k):={\frac {2}{n-k+2}}~~~\forall k=1,2,\dots ,n}$

on obtient que l'espérance de la note du candidat retenu vérifie, pour tout ${\displaystyle n\geq 1}$[3] :

${\displaystyle \mathbb {E} (R_{\tau })\leq 7/3}$.

Cela implique donc en particulier que ${\displaystyle V\leq 7/3}$.

• Problème du secrétaire

• Portail des mathématiques
• Portail de l'informatique théorique