The two-sided game of Googol and sample-based prophet inequalities
Professor Advisor
dc.contributor.advisor
Correa Haeussler, José
Author
dc.contributor.author
Epstein Von Loebenstein, Boris Alexander
Associate professor
dc.contributor.other
Ordóñez Pizarro, Fernando
Associate professor
dc.contributor.other
Soto San Martín, José
Admission date
dc.date.accessioned
2020-07-29T22:50:55Z
Available date
dc.date.available
2020-07-29T22:50:55Z
Publication date
dc.date.issued
2020
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/176188
General note
dc.description
Tesis para optar al grado de Magíster en Gestión de Operaciones
es_ES
General note
dc.description
Memoria para optar al título de Ingeniero Civil Industrial
Abstract
dc.description.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.