The two-sided game of Googol and sample-based prophet inequalities

Abstract

El problema de la secretaria o el juego de Googol son modelos clásicos para problemas de selección en línea que han recibido atención significativa en las últimas cinco décadas. En este trabajo consideramos una variante del problema y exploramos sus conexiones con selección en línea basada en datos. Específicamente, se nos entregan n cartas con números arbitrarios y no negativos escritos en ambos lados. Las cartas son puestas al azar en n posiciones consecutivas en una mesa, y para cada carta el lado visible también se elige al azar. La jugadora ve el lado visible de todas las cartas y quiere seleccionar la carta con el número escondido más alto. Para tal fin, la jugadora da vuelta la primera carta, observa el valor oculto y decide o bien detener el proceso y elegirlo, o descartarlo y continuar con la siguiente carta. Estudiamos algoritmos con dos objetivos naturales. En el primero, similar al problema de la secretaria, la jugadora desea maximizar la probabilidad de elegir el número oculto más grande. Probamos que esto se puede lograr con una probabilidad de al menos 0.45292. En el segundo objetivo, similar a la desigualdad del profeta, la jugadora desea maximizar la esperanza del valor elegido. Acá probamos una garantía de al menos 0.63518 con respecto a la esperanza del número oculto más grande. Nuestros algoritmos son el resultado de combinar tres estrategias básicas. Una es detenerse la primera vez que revelamos un valor más grande que los n valores visibles iniciales. La segunda es detenerse la primera vez que revelamos un valor que es el más grande entre los n valores actualmente visibles. La tercera es similar a la segunda, añadiendo la condición de que para detenerse el valor revelado también tiene que ser mayor que el otro lado de su carta. Aplicamos nuestros resultados a prophet secretary problem sin conocer las distribuciones de los valores, y en cambio teniendo acceso a una muestra de cada distribución. En particular, nuestra garantía mejora la garantía de 1-1/e para este problema, la cual es actualmente la mejor garantía conocida y solo funciona para el caso en que las distribuciones son independientes e idénticamente distribuidas.