Estudio de variantes del problema de la Secretaria

Abstract

El Problema de la Secretaria (SP) (por Secretary Problem), un problema con mucho interés desde los años 50, se trata de encontrar una manera de procesar las entrevistas de N candidatos a un puesto de secretaria para maximizar la probabilidad de contratar al mejor de ellos, bajo el supuesto que las entrevistas se realizan en orden aleatorio y que las decisiones tomadas: rechazar o aceptar, son irrevocables. Esto permite modelar directamente la versión discreta del problema. También se puede considerar una versión contínua con una infinidad de candidatos, suponiendo que los instantes de entrevista son tiempos aleatorios uniformes sobre el intervalo [0,1]. Este problema y sus variantes tienen muchas aplicaciones. Esta memoria se enfoca en el estudio de la variante llamada Problema de la Secretaria con Restricciones de Tiempo (TCSP). En la formulación discreta del (TCSP) se rechazan k candidatos y luego se quiere contratar al mejor de los N−k que quedan, mientras que en su formulación contínua se rechazan todos los candidatos entrevistados antes de un tiempo T y luego se quiere contratar al mejor de los candidatos entrevistados después del tiempo T. En ambos casos los candidatos rechazados al principio forman un sampleo, y se puede utilizar la información acumulada en este sampleo inicial para mejorar la toma de decisión durante la fase de aceptación que sigue. Después de familiarizarse con esta variante, se demuestran propiedades que cumple la regla óptima que resuelve el (TCSP) discreto. Basándose en esto, se estudia la siguiente estrategia para el caso contínuo. Se selecciona una sucesión creciente de constantes absolutas {T_i} en [0,1] o tiempos barreras, independientes del tiempo T del sampleo. El proceso de selección se realiza del siguiente modo: sólo se acepta un candidato entrevistado entre los tiempos T_i y T_{i+1} si es mejor que todos los ya entrevistado después del tiempo T y mejor que el i-ésimo mejor del sampleo inicial. Se encuentran fórmulas explícitas para calcular dichas barreras. La regla óptima para resolver el (TCSP) discreto tiene una forma similar, donde en vez de tiempos barreras, se usan candidatos barreras. Se comprueba que a medida que N tiende a infinito, las razones entre la posición del candidato barrera i-ésimo y el número de candidatos tienden al valor encontrado para los tiempos barreras en el caso contínuo. Finalmente, se estudia una variante del (TCSP) en la cual el empleador sólo puede recordar un candidato del periodo del sampleo (no necesariamente el mejor) y al mejor candidato entrevistado luego del sampleo. Se deduce en el caso discreto la forma de la regla óptima en la situación donde el algoritmo guarda el i-ésimo mejor candidato de la zona sampleada. Esta regla interpretada en el caso contínuo consiste en: rechazar a todos los candidatos hasta un tiempo T_1 > T, luego aceptar un candidato entrevistado entre los tiempos T_1 y T_0 > T_1 si es mejor que ambos miembros en memoria, y luego si no se aceptó a nadie, aceptar a un candidato entrevistado después del tiempo T_0 solamente si es mejor que el mejor entrevistado después del tiempo T. Se encuentran fórmulas explícitas para las barreras T_1 y T_0 como función de T y del rango i del candidato del sampleo guardado en memoria.