Optimal stopping in mechanism design

Abstract

En este trabajo estudiamos un par de problemas de la teoría de paradas óptimas, y mostramos cómo aplicar estos resultados en el diseño de mecanismos. Consideramos dos versiones modificadas de la famosa desigualdad del profeta [10, 16, 17]: una no-adaptativa donde la regla de parada debe ser decidida de antemano, y una adaptativa --- que corresponde a la configuración clásica de la desigualdad del profeta ---, pero en el caso restringido cuando las distribuciones de las variables aleatorias están idénticamente distribuidas [13]. Para la primera situación, encontramos un factor de garantía para la regla de parada con respecto al máximo esperado de la secuencia de variables aleatorias y demostramos que es la mejor posible; para el segundo, probamos que una conjetura sobre cuál es el mejor factor posible es verdadera [14]. Cerramos esta tesis extendiendo estos resultados para resolver el problema de un vendedor que enfrenta a muchos compradores potenciales y debe diseñar una subasta secuencial para maximizar sus ingresos. El tipo de mecanismos que consideramos para estudiar este problema de pricing son los mecanismos posted price, y los resultados que obtenemos toman la forma de factores de aproximación con respecto al valor de la subasta óptima [19].

In this work we study a pair of problems in optimal stopping theory, and show how to apply these results in mechanism design. We consider two modified versions of the famous prophet inequality [10, 16, 17]: a non-adaptive where the stop rule must be decided beforehand, and an adaptive one --- which corresponds to the classical prophet inequality setting ---, but when the distributions of the random variables are identical [13]. For the first set-up, we find a new factor guarantee with respect to the expected maximum of the random variables sequence and prove it is the best possible; for the second, we prove that a conjecture about the best possible factor achievable is true [14]. We close this dissertation by extending these results to solve the problem of a seller that faces many potential buyers and must design a sequential auction in order to maximize its revenue. The type of mechanisms we consider to study this pricing problem are the posted price mechanisms, and the results we get are in the form of approximation factors guarantees with respect to the optimal auction [19].