Colección SciELO Chile

Departamento Gestión de Conocimiento, Monitoreo y Prospección
Consultas o comentarios: productividad@anid.cl
Búsqueda Publicación
Búsqueda por Tema Título, Abstract y Keywords



Oracle-Augmented Prophet Inequalities
Indexado
Scopus SCOPUS_ID:85198349201
DOI 10.4230/LIPICS.ICALP.2024.81
Año 2024
Tipo

Citas Totales

Autores Afiliación Chile

Instituciones Chile

% Participación
Internacional

Autores
Afiliación Extranjera

Instituciones
Extranjeras


Abstract



In the classical prophet inequality setting, a gambler is given a sequence of n random variables X1, . . ., Xn, taken from known distributions, observes their values in adversarial order and selects one of them, immediately after it is being observed, aiming to select a value that is as high as possible. The classical prophet inequality shows a strategy that guarantees a value at least half of the value of an omniscience prophet that always picks the maximum, and this ratio is optimal. Here, we generalize the prophet inequality, allowing the gambler some additional information about the future that is otherwise privy only to the prophet. Specifically, at any point in the process, the gambler is allowed to query an oracle O. The oracle responds with a single bit answer: YES if the current realization is greater than the remaining realizations, and NO otherwise. We show that the oracle model with m oracle calls is equivalent to the Top-1-of-(m + 1) model when the objective is maximizing the probability of selecting the maximum. This equivalence fails to hold when the objective is maximizing the competitive ratio, but we still show that any algorithm for the oracle model implies an equivalent competitive ratio for the Top-1-of-(m + 1) model. We resolve the oracle model for any m, giving tight lower and upper bound on the best possible competitive ratio compared to an almighty adversary. As a consequence, we provide new results as well as improvements on known results for the Top-1-of-m model.

Métricas Externas



PlumX Altmetric Dimensions

Muestra métricas de impacto externas asociadas a la publicación. Para mayor detalle:

Disciplinas de Investigación



WOS
Sin Disciplinas
Scopus
Software
SciELO
Sin Disciplinas

Muestra la distribución de disciplinas para esta publicación.

Publicaciones WoS (Ediciones: ISSHP, ISTP, AHCI, SSCI, SCI), Scopus, SciELO Chile.

Colaboración Institucional



Muestra la distribución de colaboración, tanto nacional como extranjera, generada en esta publicación.


Autores - Afiliación



Ord. Autor Género Institución - País
1 Har-Peled, Sariel Hombre Siebel School of Computing and Data Science - Estados Unidos
2 Harb, Elfarouk - Siebel School of Computing and Data Science - Estados Unidos
3 Livanos, Vasilis - Universidad de Chile - Chile

Muestra la afiliación y género (detectado) para los co-autores de la publicación.

Financiamiento



Fuente
National Science Foundation

Muestra la fuente de financiamiento declarada en la publicación.

Agradecimientos



Agradecimiento
Sariel Har-Peled: Work on this paper was partially supported by NSF AF award CCF-2317241. Elfarouk Harb: Work on this paper was partially supported by NSF award CCF-1910149. Vasilis Livanos: Work on this paper was partially supported by NSF award CCF-1750436.

Muestra la fuente de financiamiento declarada en la publicación.