El Instituto de Ingeniería Matemática y Computacional (IMC) los saluda atentamente y los invita al seminario que se dictará la próxima semana.
Víctor Verdugo, Instituto de Ingeniería Matemática y Computacional (IMC) y Departamento de Ingeniería Industrial y de Sistemas, Pontificia Universidad Católica de Chile.
Miércoles 9 de octubre de 2024, 13:40 hrs. (Presencial en auditorio Edificio San Agustín; link Zoom disponible escribiendo a Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.)
ABSTRACT
Prophet inequalities are a cornerstone in optimal stopping and online decision-making. Traditionally, they involve the sequential observation of n non-negative independent random variables and face irrevocable accept-or-reject choices. The goal is to provide policies that provide a good approximation ratio against the optimal offline solution that can access all the values upfront -- the so-called prophet value. In the prophet inequality over time problem, the decision-maker can commit to an accepted value for T units of time, during which no new values can be accepted. This creates a trade-off between the duration of commitment and the opportunity to capture potentially higher future values.
In this work we provide optimal approximation guarantees for the IID setting. We show a single-threshold algorithm that achieves an approximation ratio of (1+1/e^2)/2≈0.567, and we prove that no single-threshold algorithm can surpass this guarantee. Then, for each n, we prove it is possible to compute the tight worst-case approximation ratio of the optimal dynamic programming policy for instances with n values by solving a convex optimization program. A limit analysis of the first-order optimality conditions yields a nonlinear differential equation showing that the optimal dynamic programming policy's asymptotic worst-case approximation ratio is ≈0.618. Joint work with Sebastian Pérez-Salazar (Rice University, USA).
