The Secretary Problem Site
  • Home
  • Classical Problem
  • Simulations
  • Backward Induction
  • Variants
  • Resources
  • Timeline
  • References
  • About
  • Español

En esta página

  • Variantes y extensiones del problema de la secretaria
  • El modelo clásico como referencia
  • 1. Problema de la secretaria con información completa
    • Planteamiento
    • ¿Qué cambia?
    • Estructura de la estrategia óptima
    • Experimento interactivo: primera decisión (observaciones uniformes)
    • Relación con el modelo clásico
  • 2. El problema del posdoctorado: seleccionar al segundo mejor
    • Planteamiento
    • ¿Qué cambia?
    • Decisión interactiva del posdoctorado (inducción hacia atrás exacta)
    • Relación con el modelo clásico
  • 3. Problemas de elecciones múltiples y de dote
    • Planteamiento
    • Contribución de Sakaguchi
    • Problemas de dos elecciones de Tamaki
    • Estructura de programación dinámica
    • Relación con el modelo clásico
  • 4. Horizonte desconocido o aleatorio
    • Planteamiento
    • ¿Qué cambia?
    • Relación con el fenómeno \(1/e\)
  • 5. Problemas del último éxito y teorema de las razones
    • Planteamiento
    • Relación con los problemas de la secretaria
    • Experimento interactivo: suma de las razones
  • 6. El problema desde la perspectiva del aspirante
    • Planteamiento
    • ¿Qué cambia?
    • Rango propio conocido
  • 7. Rango propio incierto
  • Comparación de las principales variantes
  • Mapa de la familia de problemas de la secretaria
  • Cómo continuar

Variantes y extensiones del problema de la secretaria

Estudia variantes del problema de la secretaria: información completa, segundo mejor, elecciones múltiples, horizontes aleatorios y otros objetivos.

Inicio · Problema clásico · Simulaciones · Inducción hacia atrás · Variantes · Recursos · Cronología · Referencias · Acerca del sitio

Variantes y extensiones del problema de la secretaria

El problema clásico de la secretaria es tan solo el punto de partida.

Cambiar la información disponible, el objetivo, el número de elecciones permitidas o el horizonte produce problemas de parada óptima verdaderamente distintos.

El modelo clásico como referencia

Tenemos \(n\) aspirantes cuyos rangos absolutos forman una permutación uniformemente aleatoria de

\[ 1,2,\ldots,n, \]

donde el rango \(1\) corresponde al mejor. Denotemos por \(X_k\) el rango absoluto del aspirante que ocupa la posición \(k\) y por \(R_k\) su rango relativo entre los primeros \(k\) aspirantes.

Los aspirantes se observan sucesivamente. En el instante \(k\) solo se conoce el rango relativo del aspirante entre los primeros \(k\). Las decisiones son irrevocables y solo se permite una selección.

El objetivo es

\[ \max_{\tau}\Pr(X_\tau=1). \]

Para un umbral \(1\le r<n\), se rechaza a los primeros \(r\) aspirantes y luego se acepta al primer aspirante que establezca un récord. La probabilidad de éxito es

\[ P_n(r) = \frac{r}{n} \sum_{j=r+1}^{n}\frac{1}{j-1}. \]

Si \(r=0\), se selecciona inmediatamente al primer aspirante y \(P_n(0)=1/n\).

Cuando \(n\to\infty\), una elección de umbral óptimo \(r_n^\star\) satisface

\[ \frac{r_n^\star}{n}\to \frac1e, \]

y la probabilidad óptima de éxito también converge a \(1/e\).

Las siguientes extensiones se organizan según qué componente del modelo clásico se modifica.


1. Problema de la secretaria con información completa

Planteamiento

En lugar de observar únicamente los rangos relativos, supongamos que se conocen sucesivamente los valores numéricos

\[ Y_1,\ldots,Y_n\overset{\mathrm{iid}}{\sim}F \]

donde \(F\) es una distribución continua conocida. Aquí \(Y_k\) es el valor observado, no el rango absoluto \(X_k\) del modelo clásico.

El objetivo es to maximize

\[ \Pr\!\left(Y_\tau=\max_{1\le j\le n}Y_j\right). \]

¿Qué cambia?

El valor numérico de la observación actual contiene información sobre la posibilidad de que futuras observaciones la superen.

Por eso la decisión óptima depende tanto de si la observación actual establece un récord como de su magnitud.

Estructura de la estrategia óptima

Mediante la transformación integral de probabilidad,

\[ U_i=F(Y_i), \]

el problema se reduce a observaciones independientes \(U(0,1)\).

La regla óptima se describe mediante valores críticos dependientes del tiempo: un récord se acepta únicamente si su valor es suficientemente grande en relación con el número de observaciones restantes.

Experimento interactivo: primera decisión (observaciones uniformes)

Para obtener decisiones de parada exactas y verificables, el experimento utiliza \(Y_1,\ldots,Y_n\overset{\mathrm{iid}}{\sim}U(0,1)\) con \(n=2\) o \(n=3\). Después de observar el primer valor \(x\), aceptarlo produce una probabilidad de éxito \(x^{n-1}\).

Si se rechaza ese valor y después se actúa óptimamente, la probabilidad es

\[ C_2(x)=1-x, \]

y

\[ C_3(x)= \begin{cases} \frac34-\frac{x^2}{2},&0\le x\le\frac12,\\ \frac12+x-\frac{3x^2}{2},&\frac12<x\le1. \end{cases} \]

Si \(n=3\) y se rechaza \(x\), la segunda observación \(y\) debe aceptarse solo si establece un récord y \(y\ge 1/2\). En otro caso, la última observación se elige únicamente cuando establece un nuevo récord. Al integrar sobre la segunda observación se obtiene la expresión anterior para \(C_3(x)\).

Así, los umbrales de aceptación de la primera observación son \(1/2\) para \(n=2\) y \((1+\sqrt6)/5\approx0.68990\) para \(n=3\). Se trata de umbrales de la primera etapa, no de la regla para un horizonte arbitrario.

Información completa: ¿seleccionar o continuar?

Aceptar ahora

Continuar óptimamente

Umbral de la primera etapa:

Supuestos: observaciones uniformes (0,1), independientes, idénticamente distribuidas y continuas. Se usan fórmulas analíticas exactas; los porcentajes se muestran redondeados.

Relación con el modelo clásico

Ambos problemas buscan seleccionar el máximo de toda la secuencia.

La diferencia radica en la información:

  • información relativa: solo se observan los rangos relativos;
  • información completa: se observan los valores numéricos.

Gilbert y Mosteller desarrollaron el análisis fundamental de ambos modelos (Gilbert y Mosteller (1966)).


2. El problema del posdoctorado: seleccionar al segundo mejor

Planteamiento

Cambiemos el objetivo de seleccionar al aspirante de rango absoluto \(1\) por el de seleccionar al de rango absoluto \(2\):

\[ \max_{\tau}\Pr(X_\tau=2). \]

El orden sigue siendo uniformemente aleatorio, las decisiones continúan siendo irrevocables y solo se observan rangos relativos.

¿Qué cambia?

Un aspirante que establece un récord ya no es el único que puede ser seleccionado: alguien con rango relativo \(2\) también puede ser el segundo mejor de toda la secuencia. Los rangos relativos \(a\ge3\) tienen probabilidad inmediata de éxito igual a cero. Cambiar el objetivo modifica las decisiones óptimas, aunque se conserve la misma información.

Decisión interactiva del posdoctorado (inducción hacia atrás exacta)

Condicionado a observar el rango relativo \(a\) en la posición \(k\), la probabilidad de que el aspirante tenga rango absoluto \(2\) es

\[ g_{n,k}(a)= \begin{cases} \dfrac{k(n-k)}{n(n-1)},&a=1,\\[4pt] \dfrac{k(k-1)}{n(n-1)},&a=2,\\[4pt] 0,&a\ge3. \end{cases} \]

Los rangos relativos son independientes y \(R_k\) es uniforme en \(\{1,\ldots,k\}\). Sea \(V_{n+1}=0\) y denotemos por \(V_k\) la probabilidad máxima de seleccionar al aspirante de rango absoluto \(2\), antes de observar \(R_k\). Entonces

\[ V_k=\frac1k\sum_{a=1}^k\max\{g_{n,k}(a),V_{k+1}\}, \qquad k=n,n-1,\ldots,1. \]

En la posición \(k\) se selecciona si \(g_{n,k}(a)\ge V_{k+1}\) y esa probabilidad es positiva; en otro caso se continúa. En caso de empate en cero, el experimento muestra «continuar». La programación dinámica optimiza entre todas las decisiones admisibles basadas en los rangos relativos observados.

Problema del posdoctorado: seleccionar el rango 2

Seleccionar ahora

Continuar óptimamente

Probabilidad óptima de éxito antes de entrevistar al primer aspirante:

Supuestos: orden uniformemente aleatorio, solo rangos relativos y una selección irrevocable. Los cálculos usan la recursión exacta de Bellman y muestran porcentajes redondeados.

Relación con el modelo clásico

La estructura de información es la misma; solo cambia la recompensa:

\[ \mathbf 1_{\{X_\tau=1\}} \quad\longrightarrow\quad \mathbf 1_{\{X_\tau=2\}}. \]

Esto ilustra cómo cambia la regla óptima al modificar el rango objetivo. Para un análisis adicional del problema del posdoctorado y su relación con la selección del mejor o el peor, véase Bayón et al. (2018).


3. Problemas de elecciones múltiples y de dote

Planteamiento

Supongamos que se permite realizar más de una selección.

Con \(m\) elecciones disponibles, se eligen tiempos de parada

\[ \tau_1<\tau_2<\cdots<\tau_m. \]

El evento de éxito depende del modelo: por ejemplo, se puede exigir que alguna observación seleccionada sea la mejor o que se seleccionen varios de los rangos superiores.

Contribución de Sakaguchi

El trabajo de Sakaguchi es un antecedente importante de esta rama de la literatura.

Su artículo de 1978, Dowry Problems and OLA Policies (Sakaguchi (1978)), estudió reglas de parada de tipo secretaria bajo una formulación de problemas de dote y contribuyó al desarrollo de extensiones con paradas múltiples.

Sakaguchi también estudió modelos generalizados con empleo incierto, mostrando que modificar el mecanismo de selección puede generar nuevas estructuras de parada óptima.

Problemas de dos elecciones de Tamaki

Posteriormente, Tamaki analizó problemas de secretaria con dos elecciones.

En una formulación se permiten dos elecciones y se tiene éxito si alguna de ellas es el mejor o el segundo mejor aspirante (Tamaki (1979a)). En otra, el objetivo es seleccionar tanto al máximo como al segundo máximo (Tamaki (1979b)).

Estos modelos muestran por qué las elecciones múltiples requieren un estado con más información que el problema clásico de una sola elección.

Estructura de programación dinámica

Si en el instante \(k\) quedan \(j\) elecciones, el estado debe registrar la información observada y el número de selecciones restantes.

Esquemáticamente,

\[ V_{k,j}(s) = \max\{ \text{value of selecting now}, \text{value of continuing} \}. \]

Seleccionar ahora disminuye de \(j\) a \(j-1\) el número de elecciones restantes.

Relación con el modelo clásico

Se recupera el problema clásico cuando

\[ m=1. \]

Por tanto, los modelos de elecciones múltiples agregan una variable de recursos: el número de elecciones disponibles.


4. Horizonte desconocido o aleatorio

Planteamiento

El modelo clásico supone conocido el número total \(n\) de observaciones.

Supongamos, en cambio, que el número de observaciones es una variable aleatoria

\[ N. \]

La distribución de \(N\) puede conocerse, aunque su valor realizado sea desconocido.

¿Qué cambia?

Con un horizonte fijo se sabe cuántas observaciones quedan.

Con un horizonte aleatorio, el valor de continuación debe incorporar la probabilidad de que la secuencia termine.

Los valores de continuación dependen tanto de la información observada como de la distribución condicional del horizonte restante.

Relación con el fenómeno \(1/e\)

El umbral clásico \(1/e\) no es universal para horizontes aleatorios. En el modelo de tiempo continuo del enfoque unificado de Bruss (1984), una ley \(1/e\) se cumple bajo supuestos específicos de independencia condicional. Una distribución a priori arbitraria del horizonte desconocido \(N\) no necesariamente produce la misma regla óptima ni la misma probabilidad de éxito (Bruss (1984)).


5. Problemas del último éxito y teorema de las razones

Planteamiento

Sean

\[ I_1,\ldots,I_n \]

variables aleatorias de Bernoulli independientes, con

\[ \Pr(I_k=1)=p_k,\qquad 0\le p_k<1. \]

El objetivo es detenerse en un índice \(\tau\) tal que \(I_\tau=1\) y no aparezcan éxitos posteriores. Si no hay éxitos, el intento fracasa. Se supone que cada decisión depende solo de las observaciones realizadas hasta el instante actual.

Definimos

\[ q_k=1-p_k>0, \qquad r_k=\frac{p_k}{q_k}. \]

Regla de la suma de las razones (Bruss, 2000). Definimos

\[ s=\max\left(\{1\}\cup\left\{k\in\{1,\ldots,n\}:\sum_{j=k}^{n}r_j\ge1\right\}\right). \]

Se rechazan las observaciones anteriores a \(s\) y se elige el primer éxito \(I_k=1\) con \(k\ge s\). Si no hay éxitos después de \(s\), el intento fracasa. Si la suma total de las razones es menor que \(1\), esta convención da \(s=1\). Esta regla maximiza la probabilidad de detenerse en el último éxito entre todos los tiempos de parada admisibles del modelo. Véase Bruss (2000).

Relación con los problemas de la secretaria

El teorema de las razones no es, en sí mismo, el problema clásico de la secretaria.

Forma parte de una familia más amplia de parada óptima: se debe decidir sin saber si un evento futuro superará al actual.


Experimento interactivo: suma de las razones

Modifica las probabilidades de éxito de cuatro ensayos de Bernoulli independientes. La página calcula la probabilidad exacta de detenerse en el último éxito para cada posición inicial y destaca la posición prescrita por el teorema de Bruss. Se ignoran los éxitos anteriores a esa posición y se acepta el primero posterior.

Inicio óptimo —

Probabilidad exacta de éxito —

Esta demostración corresponde al último éxito, no a seleccionar al mejor aspirante del problema clásico. Las probabilidades son estrictamente menores que 1.

6. El problema desde la perspectiva del aspirante

Planteamiento

El problema clásico se formula desde la perspectiva del empleador:

¿Cuándo debería detenerse el empleador?

Glass (2012) estudió el problema desde la perspectiva del aspirante (Glass (2012)).

Supongamos que el empleador sigue una regla de parada conocida y que un aspirante puede elegir su posición de entrevista \(i\).

El aspirante busca maximizar

\[ \Pr(\text{selected}\mid\text{position }i). \]

¿Qué cambia?

La variable de decisión del aspirante es la posición de entrevista \(i\), no el tiempo de parada \(\tau\) del empleador. La regla del empleador se considera fija al elegir la posición.

Rango propio conocido

Si el aspirante conoce su rango absoluto, la posición óptima puede depender considerablemente de ese rango.

Así surge un problema de posicionamiento estratégico basado en una regla de parada clásica.


7. Rango propio incierto

Supongamos que el aspirante desconoce su rango absoluto.

Let

\[ J\in\{1,\ldots,n\} \]

el rango absoluto aleatorio del aspirante, distinto de los rangos relativos observados \(R_k\), con una distribución a priori. Suponemos que el empleador sigue una regla de parada determinada. Por ejemplo, una distribución geométrica truncada viene dada por

\[ \Pr(J=j) = \frac{(1-q)q^{j-1}}{1-q^n}, \qquad 0<q<1. \]

El valor para el aspirante de elegir la posición \(i\) es

\[ V(i) = \sum_{j=1}^{n} \Pr(J=j) \Pr(\text{selected}\mid J=j,\text{position }i). \]

De este modo, elegir la posición de entrevista se convierte en un problema bayesiano de decisión bajo la regla de parada del empleador.


Comparación de las principales variantes

Variante Información Objetivo Decisión
Secretaria clásica Rangos relativos Seleccionar el rango \(1\) Un tiempo de parada
Información completa Valores numéricos Seleccionar el máximo Un tiempo de parada
Posdoctorado Rangos relativos Seleccionar el rango \(2\) Un tiempo de parada
Elecciones múltiples / dote Rangos relativos Alcanzar el objetivo con varias elecciones Varios tiempos de parada
Horizonte aleatorio Rangos relativos o eventos Mejor elección con \(N\) incierto Tiempo de parada
Teorema de las razones Éxitos de Bernoulli Detenerse en el último éxito Tiempo de parada
Perspectiva del aspirante Regla del empleador + rango propio Ser seleccionado Posición de entrevista
Rango propio incierto Distribución a priori del rango propio Ser seleccionado Posición de entrevista

Mapa de la familia de problemas de la secretaria

Las principales extensiones se clasifican según el componente del modelo clásico que se modifica.

Problema de la secretaria
Información
Rangos relativos
Valores completos
Información parcial
Rango propio incierto
Objetivo
Mejor aspirante
Segundo mejor
Top k
Último éxito
Estructura de elecciones
Una elección
Elecciones múltiples
Problemas de dote
Posicionamiento estratégico
Horizonte
Fijo
Aleatorio
Desconocido

Una forma de construir nuevos problemas de la secretaria consiste en modificar uno o varios componentes del modelo clásico:

Information + Objective + Choice structure + Horizon

Cada modificación puede producir un problema de parada óptima distinto.


Cómo continuar

Este sitio presenta los temas desde varios puntos de vista complementarios.

  • Inducción hacia atrás muestra cómo resolver problemas con horizonte finito, estado por estado.
  • Simulaciones permite experimentar con estrategias de umbral.
  • Cronología presenta los desarrollos más importantes en su contexto histórico.
  • Recursos ofrece ejemplos y ejercicios en Python para las variantes interactivas.

Versión en inglés

Referencias

Bayón, L., P. Fortuny Ayuso, J. M. Grau, A. M. Oller-Marcén, y M. M. Ruiz. 2018. «The Best-or-Worst and the Postdoc Problems». Journal of Combinatorial Optimization 35 (3). https://doi.org/10.1007/s10878-017-0203-4.
Bruss, F. Thomas. 1984. «A Unified Approach to a Class of Best Choice Problems with an Unknown Number of Options». The Annals of Probability 12 (3). https://doi.org/10.1214/aop/1176993237.
———. 2000. «Sum the Odds to One and Stop». The Annals of Probability 28 (3): 1384-91. https://doi.org/10.1214/aop/1019160340.
Gilbert, John P., y Frederick Mosteller. 1966. «Recognizing the Maximum of a Sequence». Journal of the American Statistical Association 61 (313): 35-73. https://doi.org/10.1080/01621459.1966.10502008.
Glass, Darren. 2012. «The Secretary Problem from the Applicant’s Point of View». The College Mathematics Journal 43 (1): 76-81. https://doi.org/10.4169/college.math.j.43.1.076.
Sakaguchi, Minoru. 1978. «Dowry Problems and OLA Policies». Reports of Statistical Application Research, Japanese Union of Scientists and Engineers 25: 124-28.
Tamaki, Mitsushi. 1979a. «A Secretary Problem with Double Choices». Journal of the Operations Research Society of Japan 22 (4): 257-65. https://doi.org/10.15807/jorsj.22.257.
———. 1979b. «Recognizing Both the Maximum and the Second Maximum of a Sequence». Journal of Applied Probability 16 (4): 803-12. https://doi.org/10.2307/3213146.

© 2026 José Ángel Islas Anguiano

Secretary problems and optimal stopping

Facultad de Ciencias Naturales y Exactas (FACINE), Universidad Autónoma de Sinaloa (UAS)