Problème du secrétaire

Un article de Wikipédia, l'encyclopédie libre.
Ceci est une version archivée de cette page, en date du 15 avril 2021 à 11:27 et modifiée en dernier par 2a01:e0a:96f:e640:e5ac:a944:66bf:73d4 (discuter). Elle peut contenir des erreurs, des inexactitudes ou des contenus vandalisés non présents dans la version actuelle.

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].

Analyse

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

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. ↑ a et b 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. ↑ a et b 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. ↑ a b et c Etienne Ghys, « Décision », sur Images des maths,
  5. ↑ Pour un nombre de candidates tendant vers l'infini.

Voir aussi

Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Problème_du_secrétaire&oldid=181922183 ».