DRH Simulator

Il y a le problème des cartes Panini : à quel moment faut-il arrêter d'acheter au hasard ses cartes à collectionner et les acheter à l'unité, quitte à les payer plus cher ? J'en avais parlé dans cet article.
Il y a le problème du parking avant un concert : faut-il se garer dès la première place disponible et avoir à marcher jusqu'à la salle, ou bien faut-il tenter de se rapprocher au maximum de l'entrée, quitte à perdre du temps en ayant à faire demi-tour ?
Il y a aussi le problème de la meilleure station-service : faut-il s'arrêter prendre de l'essence à la grande surface avant de partir, ou bien s'arrêter à l'une des stations sur le trajet, en espérant y trouver de meilleurs prix ?
On trouve des questions équivalentes dès qu'il s'agit d'investir en bourse ou de poursuivre l'exploitation d'une machine usée plutôt que de la remplacer... Bref, dans une situation qui fait la part belle au hasard, à quel moment faut-il arrêter de tenter le diable ? Un tel problème est un problème d'arrêt optimal, et c'est du plus célèbre d'entre eux que je souhaite parler aujourd'hui : le problème du gogol, aka problème du mariage, aka problème de la dot, aka problème du casting aka...

Qui sera le meilleur secrétaire ?...

Le problème des secrétaires
En bon chef d'entreprise que vous êtes, vous avez décidé d'engager un (et un seul) nouveau secrétaire. Vous organisez donc une série d'entretiens, où n candidats se présentent (vous connaissez à l'avance ce nombre n de postulants). Les candidats seront interviewés tour à tour, l'ordre étant aléatoire. A l'issue de chaque entrevue, vous n'avez que deux possibilités : le candidat est embauché ou bien rejeté. S'il est embauché, vous ne poursuivez pas les entretiens ; si il est rejeté, vous n'aurez plus l'occasion de le revoir. Attention : si vous rejetez tous les candidats, vous devrez impérativement garder le dernier (La France est en crise, il faut réduire le chômage, quitte à embaucher n'importe qui). La question est donc : à quel moment est-il préférable d'arrêter les entretiens ? 

Pour faire le meilleur choix, vous ne pouvez vous baser que sur un seul critère : le candidat est-il oui ou non meilleur que tous ses prédécesseurs (on suppose ici que l'on peut classer l'ensemble des postulants du moins bon au meilleur, sans ex aequo possibles). Mais comment peut-on faire pour maximiser les chances de tomber sur LE meilleur des candidats ?

La modélisation du problème est critiquable : un bon responsable des ressources humaines se gardera toujours la possibilité de rappeler un candidat après interview ("on vous rappellera"). De plus, il s'agit rarement de trouver le meilleur candidat, mais celui qui est qualifié pour le poste, quitte à ne garder au final aucun candidat. De plus, on peut imaginer que tous les candidats ne sont pas comparables deux à deux. Le problème des secrétaires connaît de très nombreuses variantes prenant ou non en compte ces objections, ce qui fait que le problèmes d'arrêt optimal forment une catégorie de problèmes particulièrement étudiés.

Cas n = 4
Prenons un premier exemple, avec n = 4 candidats : A (d'un niveau assez bon), B (d'un bon niveau), C (niveau très bon) et D (niveau excellent). L'objectif est donc de choisir D.
L'ordre étant aléatoire, on dénombre 24 possibilités : ABCD, ABDC, ACBD, ACDB, ADBC, ADCB, BACD, BADC, BCAD, BCDA, BDAC, BDCA, CABD, CADB, CBAD, CBDA, CDAB, CDBA, DABC, DACB, DBAC, DBCA, DCAB et DCBA.

Stratégie 0 : Une première stratégie envisageable est de choisir le premier candidat, quoi qu'il arrive. On obtient alors une stratégie qui fonctionne avec une chance sur 4 (25%).

Stratégie 1 : Une autre stratégie envisageable est de s'entrenir avec le premier candidat, sans le garder. Ensuite, on gardera le premier des candidats à se présenter qui sera meilleur que le candidat n°1. Plusieurs cas sont envisageables :
- le premier candidat est D : il sera éliminé, tant pis.
- le premier candidat est C : le seul candidat meilleur que C est D, qui sera donc forcément choisi quand il se présentera -> 6 possibilités sur 24
- le premier candidat est B. Sous cette condition, on prendra le premier des candidats C ou D à se présenter -> 3 possibilités sur 24
- le premier candidat est A. Sous cette condition, le candidat n°2 sera choisi, soit une chance sur trois de tomber sur D -> 2 possibilités sur 24.
Au final, cette stratégie donne 11 chances sur 24 (46% de chances) de tomber sur D, le meilleur candidat. On peut aussi vérifier que l'on choisira C avec une probabilité de 7/24, B avec une probabilité de 4/24 et A avec une probabilité de 2/24.

Stratégie 2 : Une autre stratégie envisageable est de s'entrenir avec les deux premiers candidats sans les garder, puis de choisir le candidat n°3 s'il est meilleur que les deux premier, et le n°4 sinon.
Dans ce cas, D sera choisi systématiquement si les premiers candidats sont AC, BC, CA ou CB. Si les premiers candidats sont AB ou BA, D sera choisi dans la moitié des cas. Sinon, c'est que D est parmi les deux premiers candidats, et donc éliminé. On en déduit alors que D sera choisi avec une probabilité de 10/24 (soit 42%). Pour C, la probabilité est de 6/24, pour B et A, elle est de 4/24.

On peut oublier la stratégie 3 consistant à ne pas sélectionner les trois premiers candidats pour ne garder que le dernier, qui fait retomber la probabilité d'embaucher D à 1 chance sur 4.

En appelant "stratégie k" la stratégie consistant à faire passer les k premiers candidats sans les garder, puis sélectionner le premier des candidats meilleur que ces k premiers, on vient de vérifier que dans le cas n = 4, la stratégie optimale est la stratégie 1. Le meilleur des candidats sera sélectionné avec une probabilité d'environ 46%.

Cas n = 5
On peut procéder à la même analyse pour le cas n = 5, en envisageant les 120 ordres possibles pour 5 candidats. Les probabilités d'obtenir le meilleur candidat, suivant les différentes stratégies envisageables, sont alors :

Stratégie 0 : p = 20 %
Stratégie 1 : p = 41.7 %
Stratégie 2 : p = 43,3 %
Stratégie 3 : p = 35 %
Stratégie 4 : p = 20 %

Bref, la meilleure stratégie consiste ici à laisser passer les deux premiers candidats.

Mais pour les valeurs plus grande ? Il existe forcément une stratégie meilleure que les autres, mais laquelle ? Et la solution est plutôt simple : même si vous devez auditionner 100 000 secrétaires, il existe toujours une stratégie permettant de trouver le meilleur avec une probabilité supérieure à 36% ! Cette stratégie, c'est la stratégie n/e : il faut laisser passer le premier tiers (36.79% des candidats, pour être un peu plus précis) des candidats, puis prendre le premier des candidats meilleurs. Et on va le prouver !

Le jeu du gogol
Le problème des secrétaires trouve ses origines dans la rubrique Mathematical Games de Martin Gardner dans le numéro de février 1960 du Scientific American. Le problème y est présenté sous la forme du "jeu du gogol" : un joueur écrit sur des feuilles des nombres quelconques, arbitrairement grands ou petits (d'où le nom du jeu : on peut y écrire des nombres aussi grand qu'un gogol, ie, 10¹⁰⁰), le but étant pour l'autre joueur de les retourner successivement, mais de s'arrêter sur le plus grand d'entre eux. La question de la stratégie optimale à suivre pour le deuxième joueur revient à résoudre le problème des secrétaires.  La solution arrivera dans la même rubrique du magazine, le mois suivant. On retrouvera plus tard le même problème sous le nom de "problème du mariage" (un Don Juan fait défiler des candidate pour son mariage, jusqu'à faire un choix), ou sous d'autres appellations tout aussi sexistes (problème de la dot, problème du concours de beauté, ...).

Les origines du problème semble cependant remonter au XVIIe siècle, après que l'astronome allemand Johannes Kepler a perdu sa première femme à cause du choléra. Bien décidé à en trouver une nouvelle, il a cherché à ne pas faire la même erreur que pour son premier mariage, qui lui avait été arrangé. Pour ce faire, il a consacré deux ans de sa vie à chercher la femme idéale, et 11 ont répondu à l'appel. De nombreuses lettres de Kepler relatent son processus de décision pas tout à fait au point. Le problème se termine bien : il finira par choisir la cinquième, ils se marièrent et eurent beaucoup (7) d'enfants.
En fait, Kepler n'a pas réellement inventé le problème des secrétaires (la plupart des hypothèses du problème ne sont pas respectées, puisqu'il s'est autorisé à revenir sur ses choix), mais il a quand même énoncé le premier problème d'arrêt optimal, en inventant au passage le principe du speed-dating (qui dure deux ans).

Cas général
Revenons au problème général, avec n secrétaires. Les informations que l'on a à notre disposition limitent pas mal les différentes stratégies possibles. En fait, les seules stratégies envisageables sont les stratégie k (k ∈ [0 ; n-1]) : on interroge les k premiers candidats pour se donner une idée de leur niveau en les rejetant systématiquement, puis, parmi les n-k candidats suivants, on choisit le premier à être meilleur que les k premiers. Reste à savoir quelle est, en fonction de n, la valeur de k idéale.

Notons j la position de ce mystérieux candidat meilleur que les autres. La probabilité que j soit une valeur fixée à l'avance est de 1/n.
Si j ≤ k, alors le candidat n°j sera ignoré, et donc, non choisi.
Si j = k+1, c'est que le meilleur candidat arrive pile au bon moment : il est choisi.
Si j ≥ k+2, le candidat n°j sera sélectionné seulement s'il n'y a pas de candidat opportuniste (meilleur que les k premiers) entre la position k+1 et j-1. Ceci n'arrivera qu'avec une probabilité de k/(j-1) : la probabilité que le meilleur des (j-1) premiers soit dans les k premiers (formellement, c'est la probabilité de choisir le j-ième candidat sachant que c'est le meilleur).

La probabilité que la stratégie k permette de trouver le meilleur candidat est donc :

En simplifiant :

Pour des petites valeurs de n, on peut calculer ces probabilités pour toutes les valeurs de k afin de déterminer la stratégie optimale :

Pour n = 3, P est maximal pour k = 1 (P = 0.5)
Pour n = 4, P est maximal pour k = 1 (P = 0.458)
Pour n = 5, P est maximal pour k = 2 (P = 0.433)
Pour n = 6, P est maximal pour k = 2 (P = 0.428)
Pour n = 7, P est maximal pour k = 2 (P = 0.414)
Pour n = 8, P est maximal pour k = 3 (P = 0.410)
Pour n = 9, P est maximal pour k = 3 (P = 0.406)
Pour n = 10, P est maximal pour k = 3 (P = 0.398)
En poursuivant les calculs, on peut se convaincre que n/k tend vers e.

Pour des valeurs de n plus élevées, on va plutôt déterminer une valeur approchée de P_n,k. Un peu de calcul intégral permet de voir que

La probabilité de succès de la stratégie k est donc environ égale à P_n,k = (k/n) ln(n/k). Il n'y a plus qu'à chercher pour quelle valeur de k cette probabilité est maximale. 
Posons x = (k/n). La fonction f(x) = x ln(1/x) est maximale (si si, je vous l'assure) lorsque x = 1/e ≈ 0.368, ce qui signifie que la probabilité est maximale quand le rapport entre k et n vaut approximativement 36.8 %.
La meilleure stratégie, pour un nombre de candidat n, est donc la stratégie n/e. Cette stratégie offre une probabilité de succès valant f(1/e) = 1/e ≈ 0.368.

Il y a des tas d'autres problèmes d'arrêt optimal, comme celui du jeu d'Arthur "à prendre ou à laisser". Puisqu'il paraît que le jeu revient à la télé à la rentrée, ça me fera une bonne excuse pour faire d'autres articles sur le sujet !

---

Sources :
Who solved the secretary problem, Thomas S. Ferguson

Illustration : Queue

Comments

[Moringa]

très intéressant (et ça va celui-là j'ai réussi à comprendre malgré le manque de vitalité ce jour lol)

[Chopchop]

Si on représente la valeur d'un candidat par un entier entre $1$ et $n$, est-ce que l'on sait quelque chose sur l'espérance de la valeur du candidat choisi par la stratégie $k$ ?

[Grob]

Si n devient grand, et que l'on arrive toujours à trier les secrétaires, aurait-on alors une manière de quantifier le talent d'un secrétaire ? On ne peut pas alors inventer une stratégie qui dirait "bon au début je regarde [comme pour la stratégie présentée], ensuite si un postulant est largement au dessus de ce que j'ai déjà vu je le prend, si il est juste au dessus et qu'au final j'en suis même pas à la moitié, je laisse passer, c'est surement un opportuniste"..?

[Clydevil]

Hello,

Ce qui est intéressant dans le jeu d'Arthur (et oui on peut y voir un point intéressant :p) c'est qu'il y a aussi le rôle du mec qui propose une échappatoire si je me souviens bien. A un moment donné il propose de s’arrêter contre une certaine somme acquise de manière certaine. Il y a peut être de la stratégie mixte la dedans, dans la mesure ou le but du gugus serait de minimiser les pertes de l’émission, mais avec une part nécessaire de bluff pour éviter d'introduire de l'information.

A suivre...