Problème de secrétaire

Le problème de secrétaire de est un problème de arrêt optimal du qui a été étudié intensivement dans les domaines de la probabilité appliquée par , des statistiques , et de la théorie de la décision . On le connaît également comme problème de mariage de , problème de la dot du sultan de , problème tatillon de prétendant de , et problème bien choisi meilleur. Le problème peut être énoncé comme suit :

il y a une position de secrétariat simple à remplir.

Il y a des demandeurs de

n

pour la position, et ceci est connu.

Les demandeurs peuvent être rangés du meilleur à plus mauvais sans des cravates.

Les demandeurs sont interviewés séquentiellement dans un ordre aléatoire, avec chaque ordre étant également probable.

Après que chaque entrevue, le demandeur soit acceptée ou rejetée.

La décision à acceptent ou rejettent un demandeur peut être basée seulement sur les rangs relatifs des demandeurs interviewés jusqu'ici.

Des demandeurs rejetés ne peuvent pas être rappelés.

L'objet est de choisir le meilleur demandeur. Le profit est 1 pour le meilleur demandeur et zéro autrement.

Disons qu'un demandeur est un candidat de seulement s'il est meilleur que tous les demandeurs vus précédemment. Clairement, puisque l'objectif dans le problème est de choisir le meilleur demandeur simple, seulement des candidats seront considérés pour l'acceptation. Une raison pour laquelle le problème de secrétaire a suscité tellement l'attention est que la politique optimale pour le problème (le arrêtant règle ) a un dispositif étonnant. Spécifiquement, parce que grand $n$ la politique optimale est de sauter les premiers demandeurs du $e$ de $n/$ et puis d'accepter le prochain candidat qui est meilleur que tout ceux précédemment interviewés, où $e$ est la base du logarithme naturel . Pendant que $n$ devient plus grand, la probabilité de choisir le meilleur demandeur à partir de la piscine va à $1/e$ , qui est environ 37%. Si on recherche par 100 ou 100.000 demandeurs, la politique optimale choisira le meilleur simple un environ 37% du temps.

Dérivation de la politique optimale

La politique optimale pour le problème est un arrêtant la règle . Sous elle, l'interviewer devrait sauter les premiers demandeurs de

r-1

, et puis prend le prochain demandeur qui est un candidat (c., qui a le meilleur rang relatif de ceux interviewé jusqu'à ce point). Pour une coupure arbitraire

r

, la probabilité que le meilleur demandeur est choisi est

$P (r)= \ sum_ {j=r} ^ {} de n \ laissé (\ frac {1} {n} \ droit) \ parti (\ frac {r-1} {j-1} \ droit) = \ parti (\ frac {r-1} {n} \ droit) \ sum_ {j=r} ^ {} de n \ laissé (\ frac {1} {j-1} \ droit).$

Laissant $n$ tendre à l'infini, écrivant $x$ comme limite de $r/n$ , using $t$ pour $j/n$ et $dt$ pour $1/n$ , la somme peut être rapproché par l'intégrale

$= - x \ texte {notation} (x).$

Prise du dérivé du $P (r)$ en ce qui concerne $x$ , le plaçant à 0, et le résolvant pour $x$ , nous constatons que le $x$ optimal est égal à $1/e$ . Ainsi, la coupure optimale tend à $n/e$ à mesure que $n$ augmente, et le meilleur demandeur est choisi avec la probabilité $1/e$ .

Pour de petites valeurs de $n$ , le $r$ optimal peut également être obtenu par des méthodes standard de la programmation dynamique . Les seuils optimaux $r$ et la probabilité de choisir la meilleure alternative $P$ pour plusieurs valeurs de $n$ sont montrés dans la table suivante.

Exécution heuristique

Stein, Seale, et Rapoport (2003) ont dérivé les probabilités de succès prévues pour des plusieurs l'heuristique psychologiquement plausible qui pourrait être utilisée dans le problème de secrétaire. L'heuristique qu'ils ont examinée étaient :
de

la règle de coupure (CR) : n'acceptent pas les premiers demandeurs l'uns des de $y$ ; ensuite, choisir le premier candidat produit (c., un demandeur avec le rang relatif 1). Cette règle a comme point de droit spécial la politique optimale pour le CSP pour lequel $y=r$ .
Règle de compte de candidat de (CCR) : choisissent le candidat produit par $y$ . La note, cette cette règle ne saute nécessairement aucun demandeur ; elle considère seulement combien de candidats ont été observés, pas comment profondément le décideur est dans l'ordre de demandeur.
Règle successive de Non-Candidate de (SNCR) : choisissent le premier candidat produit après avoir observé les non-candidates de $y$ (c., demandeurs avec le rang relatif >1).

Noter que chacun heuristique a un paramètre simple $y$ . La figure (montrée sur la droite) montre les probabilités de succès prévues pour chacun heuristique en fonction de $y$ pour des problèmes avec $n=80$ .

Variante cardinale de profit

La conclusion du meilleur demandeur simple pourrait sembler comme un objectif plutôt strict. On peut imaginer que l'interviewer engagerait plutôt un demandeur haut-évalué que lower-valued, et non seulement soit concerné par tirer le meilleur parti. C'est-à-dire, elle dérivera une certaine valeur de choisir un demandeur qui n'est pas nécessairement le meilleur, et la valeur qu'elle dérive augmente en valeur de celle elle choisit.

Pour modeler ce problème, supposer que les demandeurs de $n$ ont le " ; true" ; valeurs qui sont le dessiné par $X$ aléatoire des variables I.d d'une distribution uniforme sur . Semblable au problème classique décrit ci-dessus, l'interviewer observe seulement si chaque demandeur est le meilleur jusqu'ici (un candidat), doit accepter ou rejeter chacun sur place, et le doit accepter dernier s'il est atteint. (Pour être clair, l'interviewer n'apprend pas le grade relatif réel du chaque demandeur de . Elle apprend seulement si le demandeur a le grade relatif 1.) cependant, dans cette version que son profit de est donné par la valeur vraie du demandeur choisi. Par exemple, si elle choisit un demandeur dont la valeur vraie est 0.8, puis elle gagnera 0. L'objectif de l'interviewer est de maximiser la valeur prévue du demandeur choisi.

Puisque les valeurs du demandeur sont i.d tire d'une distribution uniforme sur , la valeur prévue du demandeur de $t$ th étant donné que le $x_ {t} = \ maximum \ est parti \ {x_ {1}, le x_ {2}, \ ldots, x_ {t} \ droit \}$ est donné près

$Le =E d'E_ {t} \ est parti (X_ {t}|I_ {t} =1 \) = droit \ frac {t} {t+1}.$

Comme dans le problème classique, la politique optimale est donnée par un seuil, que pour ce problème nous dénoterons par $c$ , auquel l'interviewer devrait commencer à accepter des candidats. Bearden (2006) a prouvé que $c$ est $n \ rfloor$ ou $\ lceil \ racine carrée n \ rceil$ . Ceci suit du fait que donné un problème avec des demandeurs de $n$ , le profit prévu pour un certain seuil arbitraire $1 \ leq c \ leq n$ est

$V_ {n} (c)= \ sum_ {t=c} ^ {n-1} \ laissé \ laissé (\ frac {1} {t+1} \ droits) + \ laissé \ frac {1} {2} = {\ frac {^ 2cn- {c} {2} +c-n} {2cn}}.$

Différenciant le $V_ {n} (c)$ en ce qui concerne $c$ , on obtient le $\ V partiel/\ partiel c= \ parti (- {c} ^ {\, 2} +n \) droit/\ (2 ^ {c} {\, 2} n \ droit)$ laissé. Depuis le $\ partial^ {\, 2} V/\ c^ partiel {\, 2} <0$ pour tout permis des valeurs de $c$ , nous constatons que $V$ est maximisé au $c= \ racine carrée n$ . Puisque $V$ est convexe dans $c$ , le seuil nombre-évalué optimal doit être $\ lfloor \ racine carrée n \ rfloor$ ou $\ lceil \ racine carrée n \ rceil$ . Ainsi, parce que la plupart des valeurs de $n$ que l'interviewer commencera à accepter des demandeurs plus tôt dans la version cardinale de profit que dans la version classique où l'objectif est de choisir le meilleur demandeur simple. Noter que ce n'est pas un résultat asymptotique : Il se tient pour tout le $n$ .

D'autres variantes

On a proposé un certain nombre d'autres variations du problème classique de secrétaire.

Études expérimentales

Les psychologues et les économistes expérimentaux ont étudié le comportement de décision des personnes réelles dans des problèmes de secrétaire. Dans la grande partie, ce travail a prouvé que les gens tendent à cesser de rechercher trop tôt. Ceci peut être expliqué, au moins en partie, par le coût d'évaluer des candidats. Extrapolant aux arrangements de monde réel, ceci pourrait suggérer que les gens ne recherchent pas assez toutes les fois qu'ils sont confrontés aux problèmes où les solutions de rechange de décision sont produites séquentiellement. Par exemple, en essayant de décider à quelle station service s'arrêter pour le gaz, les gens ne pourrait pas rechercher asse'avant l'arrêt. Si vrais, alors ils tendraient à payer plus le gaz qu'ils pourraient les ont eus ont recherché plus longtemps. Les mêmes peuvent être vrais quand la recherche de personnes en ligne pour des billets d'avion, indiquent. La recherche expérimentale sur des problèmes tels que le problème de secrétaire est parfois mentionnée comme la recherche opérationnelle comportementale .

Citations

eflist

Random links: