Variantes y extensiones del problema de la secretaria
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.
Una forma de construir nuevos problemas de la secretaria consiste en modificar uno o varios componentes del modelo clásico:
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.