Problème du secrétaire
Le problème de la secrétaire[1] ou des secrétaires est un problème mathématique de théorie de l’arrêt optimal (en) 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é
Le 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 onlines.
Stratégie
La 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.
Exemple d'application
La stratégie au 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
- 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 Karaoui, Promenades aléatoires : Chaînes de Markov et simulations ; martingales et stratégies, Les éditions de l’École polytechnique, 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).