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



Trading Prophets
Indexado
Scopus SCOPUS_ID:85168162440
DOI 10.1145/3580507.3597813
Año 2023
Tipo

Citas Totales

Autores Afiliación Chile

Instituciones Chile

% Participación
Internacional

Autores
Afiliación Extranjera

Instituciones
Extranjeras


Abstract



In this work we initiate the study of buy-and-sell prophet inequalities. We start by considering what is arguably the most fundamental setting. In this setting the online algorithm observes a sequence of prices one after the other. At each time step, the online algorithm can decide to buy and pay the current price if it does not hold the item already; or it can decide to sell and collect the current price as a reward if it holds the item.We show that for i.i.d. prices a single-threshold online algorithm achieves at least 1/2 of the expected profit of the the optimal offline algorithm, and that this is the best possible ratio achievable by any online algorithm. For non-i.i.d. prices in random order, where prices are no longer independent, we give a single-threshold online algorithm that achieves at least a 1/16 fraction of the expected profit of the optimal offline algorithm. We also show that for this setting no online algorithm can yield a better than 1/3 approximation, and thus establish a formal separation from the i.i.d. case. On the other hand, we present a threshold-based online algorithm for this setting that yields a 1/2 - o(1) approximation. For non-i.i.d. prices (and arbitrarily correlated distributions) no approximation is possible.We use the results for these base cases to solve a variety of more complex settings. For instance, we show a 1/2 - o(1) approximation for settings where prices are affiliated and the online algorithm has only access to a single sample. We also extend our upper and lower bounds for the single item case to k items, and thus in particular show that unlike in the classic prophet inequality problem with k items it is impossible to achieve 1 - o(1) approximations. We also consider a budgeted version where the online algorithm can buy fractions of an item and re-invest gains, and show that it's possible to achieve constant-factor approximations to the growth rate of the optimal offline algorithm. For a setting with k types of items and streams of prices for each type of item, we show that for the unit-capacity case it is possible to achieve a ω(1/k) approximation, and that this is best possible.

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
Sin Disciplinas
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 CORREA-FONTECILLA, JOSE RAFAEL Hombre Universidad de Chile - Chile
2 Cristi, Andrés Hombre Universidad de Chile - Chile
3 Dütting, Paul Hombre Google LLC - Estados Unidos
4 Hajiaghayi, Mohammad Taghi - University of Maryland, College Park - Estados Unidos
5 Olkowski, Jan - University of Maryland, College Park - Estados Unidos
6 Schewior, Kevin Hombre Syddansk Universitet - Dinamarca

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

Financiamiento



Fuente
National Science Foundation
Danmarks Frie Forskningsfond
Exploratory Research Center on Life and Living Systems, National Institutes of Natural Sciences
DARPA QuICC

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

Agradecimientos



Agradecimiento
This work was initiated during the Fall 2021 Virtual Chair Semester on Prophet Inequalities [Correa et al., 2022]. We would like to thank the organizers and the participants of the semester for their feedback. Kevin Schewior was in part supported by Independent Research Fund Denmark, Natural Sciences under Grant No. DFF-0135-00018B. MohammadTaghi Hajiaghayi and Jan Olkowski are partially supported by DARPA QuICC, NSF AF:Small 2218678, and NSF AF:Small 2114269.

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