Problème du secrétaire

Le problème du secrétaire, 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 bonne stratégie[5] est de laisser passer 37 % des candidates (ou, plus précisément, une proportion 1/e), puis d'attendre d'avoir une candidate meilleure que toutes celles de ce premier échantillon[4]. On parle parfois de la règle des 37 %[2].

Extensions

Sous certaines hypothèses, on peut étendre l'analyse au recrutement de plusieurs personnes[3].

Références
  1. 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)
  2. 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.
  3. Claire Mathieu, « Support du cours « Algorithmes pour flux de données » au collège de France, le 16 janvier 2018 », sur Collège de France.
  4. Etienne Ghys, « Décision », sur Images des maths,
  5. Pour un nombre de candidates tendant vers l'infini.

Voir aussi
  • Portail des mathématiques
  • Portail de l'informatique théorique
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.