Prophet inequality through schur-convexity and optimal control

Abstract

En el clásico problema de tiempo de parada óptimo conocido como Desigualdad del profeta realizaciones de variables positivas e independientes son descubiertas secuencialmente. Una jugadora que conoce las distribuciones, pero no puede ver en el futuro, debe decidir cuándo parar y tomar la última variable revelada. Su objetivo es maximizar la esperanza de lo obtenido y su rendimiento está dado por el peor caso del cociente entre la esperanza de que obtiene y la esperanza de lo que obtendría un profeta (que puede ver en el futuro y así siempre elegir el máximo). En los setenta, Krengel y Sucheston, y Garling, [16] determinaron que el rendimiento de una jugadora puede ser una constante y que 1/2 es la mejor constante. En la última década, la desigualdad del profeta ha resurgido como un problema importante dada su conexión con "Posted Price Mechanisms", una teoría usada en ventas en línea. Una variante de particular interés es "Prophet Secretary", donde la única diferencia es que las relaciones son descubiertas en orden aleatorio. Para esta variante, varios algoritmos logran un rendimiento de 1 − 1/e ≈ 0.63 y recientemente Azar et al. [2] mejoraron este resultado. En cuanto a cotas superiores, se sabe que una jugadora no puede hacerlo mejor que 0.745, en el límite sobre el tamaño de la instancia. En esta tesis se deriva una forma de analizar estrategias que dependen sólo del tiempo: dada una instancia, se calcula una secuencia decreciente de exigencias que son usadas para decidir si parar o no. La jugadora tomará el primer valor que supere la exigencia correspondiente al momento en que fue descubierta. Específicamente, se considera una clase robusta de estrategias que denominamos "blind strategies". Constituyen una generalización de fijar una sola exigencia para todo el proceso y consisten en fijar una función, independiente de la instancia, que determina cómo calcular las exigencias una vez la instancia es conocida. El resultado principal es que la jugadora logra un rendimiento de al menos 0.669, superando el estado del arte (Azar et al. [2]) tanto para "Prophet Secretary" como para la variante en la que la jugadora tiene la libertad de escoger el orden en que descubre las variables (Beyhaghi et al [3]). El análisis se reduce a estudiar la distribución del tiempo de parada inducido por estas estrategias, a través de la teoría de Schur-convexidad. También, se demuestra que este tipo de estrategias no pueden lograr más que 0.675, a través de calcular el rendimiento óptimo de la jugadora contra dos instancias particulares, resolviendo un problema de control óptimo. Finalmente, se demuestra que el conjunto más amplio de estrategias no adaptativas no pueden lograr más de √3 − 1 ≈ 0.73, cota que también mejora el estado del arte en cotas superiores para estrategias simples (Azar et al [2]). Se considera una estrategia como no adaptativa si al decisión de parar depende del valor, la identidad y el tiempo en que fue descubierta la variable, pero no toma en cuenta la identidad de las variables anteriores.