Problème du secrétaire
Le problème du ou de la secrétaire[1], ou des secrétaires, est un problème mathématique de l’arrêt optimal en théorie de la décision, en théorie des probabilités et en statistique. Le problème est aussi connu sous le nom de problème de la princesse[2] et de problème du recrutement immédiat[3].
Énoncé
modifierLe contexte est le suivant : quelqu'un veut recruter un ou une secrétaire et voit défiler un nombre fini et connu de candidats. Pour chacun, il doit décider s'il l'engage ou pas. Si oui, il termine le processus de recrutement sans voir les autres candidats. Sinon, il n'a pas la possibilité de rappeler la candidate plus tard[4]. Dans le contexte de ce problème, le recruteur n'a pas accès à une valeur intrinsèque des candidats (comme « ce candidat vaut 7/10 » ), il ne peut que les comparer (par exemple « ce candidat est meilleur que le premier, mais moins bon que le deuxième »)[4].
Le but est de définir une stratégie qui maximise la probabilité d'engager le meilleur candidat.
Le problème peut être vu comme un problème algorithmique, dans le contexte des algorithmes en ligne.
Stratégie
modifierLa meilleure stratégie[5] consiste à laisser passer 37 % des candidats (ou, plus précisément, une proportion 1/e), puis à engager le premier candidat meilleur que les précédents[4]. On parle aussi de « la règle des 37 % »[2].
Par extension, on peut étendre l'analyse au recrutement de plusieurs personnes[3]. Sous l'hypothèse de sous-modularité (plus on a déjà recruté de candidats, moins le recrutement d'un nouveau apporte de valeur ajoutée[6]), pour k postes disponibles et N candidats, la meilleur stratégie consiste à :
- Constituer k groupes de N/k candidats ;
- Dans chaque groupe, observer les (N/k)/e premiers candidats sans proposer d'offre ;
- Faire une offre au premier candidat du groupe dont la valeur marginale est meilleure que celle des k premiers candidats.
Analyse
modifier
Le principe consiste à s'arrêter après avoir observé un pourcentage de candidats, suffisamment représentatif de la population totale. Le niveau moyen des candidats vus permet de détecter et recruter le premier candidat qui sera au-dessus de cette moyenne, en étant (presque) assuré de ne pas rater un candidat encore meilleur. Les calculs théoriques, confirmés par l'expérience, montrent que le pourcentage le plus efficace est 37 %. En deçà, l'estimation n'est pas assez fiable ; au-delà, elle ne s'affine que peu et on risque de plus en plus de laisser passer le meilleur candidat.
Exemple d'application
modifierLa stratégie de résolution du problème du secrétaire peut être mise en pratique dans diverses situations de la vie quotidienne. Par exemple, un conducteur est à la recherche d'une station-service pour faire le plein de carburant au meilleur prix possible. Il dispose encore de suffisamment de carburant pour passer devant 30 stations-service où il peut visualiser les prix. En suivant la règle des 37 %, il devra laisser passer les 11 premières stations-service et s'arrêter à la prochaine qui affichera un meilleur prix que les précédents.
Références
modifier- Danielle Florens-Zmirou, « Jeux de la secrétaire », Cahiers du Bureau universitaire de recherche opérationnelle Série Recherche, Institut Henri Poincaré - Institut de Statistique de l'Université de Paris, vol. 32, , p. 35-68 (lire en ligne).
- Michel Benaim et Nicole El Karoui, Promenade aléatoire : Chaînes de Markov et simulations ; martingales et stratégies, Les éditions de l’École polytechnique, , 316 p. (ISBN 978-2-7302-1168-0), chap. 6.4 (« Arrêt optimal »), p. 210-211.
- Claire Mathieu, « Algorithmes pour flux de données », support du cours [PDF], sur Collège de France, , p. 30.
- Etienne Ghys, « Décision », sur Images des maths, .
- Pour un nombre de candidates tendant vers l'infini.
- Valeur(A) > Valeur(A,B) - Valeur(B) > Valeur(A,B,C) - Valeur(B,C).
