Problème du secrétaire

vignette|Portrait d'une femme devant une machine à écrire. Le problème de la secrétaire ou des secrétaires est un problème mathématique de 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 et de problème du recrutement immédiat. 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. 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 »). 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. La meilleure stratégie 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. On parle aussi de « la règle des 37 % ». Par extension, on peut étendre l'analyse au recrutement de plusieurs personnes. 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), 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. 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.