Prophet Inequalities with Linear Correlations and Augmentations
In a classical online decision problem, a decision-maker who is trying to maximize her value inspects a sequence of arriving items to learn their values (drawn from known distributions), and decides when to stop the process by taking the current item. The goal is to prove a "prophet inequality": tha...
Zapisane w:
| Główni autorzy: | , , |
|---|---|
| Format: | Artykuł |
| Wydane: |
2020
|
| Hasła przedmiotowe: | |
| Dostęp online: | https://arxiv.org/abs/2001.10600 http://arxiv.org/abs/2001.10600 |
| Etykiety: |
Nie ma etykietki, Dołącz pierwszą etykiete!
|
| _version_ | 1879172274661097472 |
|---|---|
| author | Immorlica, Nicole Singla, Sahil Waggoner, Bo |
| author_browse | Immorlica, Nicole Singla, Sahil Waggoner, Bo |
| author_facet | Immorlica, Nicole Singla, Sahil Waggoner, Bo |
| author_sort | Immorlica, Nicole |
| building | arXiv |
| collection | Acceso abierto |
| description | In a classical online decision problem, a decision-maker who is trying to maximize her value inspects a sequence of arriving items to learn their values (drawn from known distributions), and decides when to stop the process by taking the current item. The goal is to prove a "prophet inequality": that she can do approximately as well as a prophet with foreknowledge of all the values. In this work, we investigate this problem when the values are allowed to be correlated. Since non-trivial guarantees are impossible for arbitrary correlations, we consider a natural "linear" correlation structure introduced by Bateni et al. [ESA 2015] as a generalization of the common-base value model of Chawla et al. [GEB 2015].
A key challenge is that threshold-based algorithms, which are commonly used for prophet inequalities, no longer guarantee good performance for linear correlations. We relate this roadblock to another "augmentations" challenge that might be of independent interest: many existing prophet inequality algorithms are not robust to slight increase in the values of the arriving items. We leverage this intuition to prove bounds (matching up to constant factors) that decay gracefully with the amount of correlation of the arriving items. We extend these results to the case of selecting multiple items by designing a new $(1+o(1))$ approximation ratio algorithm that is robust to augmentations. |
| first_indexed | 2026-10-15T23:38:51Z |
| format | Article |
| fullrecord | <oai_dc:dc xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/" xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/ https://www.openarchives.org/OAI/2.0/oai_dc.xsd"><identifier>arxiv-2001.10600</identifier><datestamp>2020-05-26</datestamp>
<dc:title>Prophet Inequalities with Linear Correlations and Augmentations</dc:title>
<dc:creator>Immorlica, Nicole</dc:creator>
<dc:creator>Singla, Sahil</dc:creator>
<dc:creator>Waggoner, Bo</dc:creator>
<dc:subject>Data Structures and Algorithms</dc:subject>
<dc:subject>Computer Science and Game Theory</dc:subject>
<dc:description>In a classical online decision problem, a decision-maker who is trying to maximize her value inspects a sequence of arriving items to learn their values (drawn from known distributions), and decides when to stop the process by taking the current item. The goal is to prove a "prophet inequality": that she can do approximately as well as a prophet with foreknowledge of all the values. In this work, we investigate this problem when the values are allowed to be correlated. Since non-trivial guarantees are impossible for arbitrary correlations, we consider a natural "linear" correlation structure introduced by Bateni et al. [ESA 2015] as a generalization of the common-base value model of Chawla et al. [GEB 2015].
A key challenge is that threshold-based algorithms, which are commonly used for prophet inequalities, no longer guarantee good performance for linear correlations. We relate this roadblock to another "augmentations" challenge that might be of independent interest: many existing prophet inequality algorithms are not robust to slight increase in the values of the arriving items. We leverage this intuition to prove bounds (matching up to constant factors) that decay gracefully with the amount of correlation of the arriving items. We extend these results to the case of selecting multiple items by designing a new $(1+o(1))$ approximation ratio algorithm that is robust to augmentations. </dc:description>
<dc:description>31 pages. Appears in EC 2020</dc:description>
<dc:date>2020-01-28</dc:date>
<dc:date>2020-05-23</dc:date>
<dc:type>text</dc:type>
<dc:identifier>https://arxiv.org/abs/2001.10600</dc:identifier>
<dc:identifier>http://arxiv.org/abs/2001.10600</dc:identifier>
</oai_dc:dc> |
| id | arxiv-2001.10600 |
| institution | arXiv |
| last_indexed | 2026-10-15T23:38:51Z |
| publishDate | 2020 |
| publishDateRange | 2020 |
| publishDateSort | 2020 |
| record_format | oai_dc |
| spelling | arxiv-2001.106002020-05-26 Prophet Inequalities with Linear Correlations and Augmentations Immorlica, Nicole Singla, Sahil Waggoner, Bo Data Structures and Algorithms Computer Science and Game Theory In a classical online decision problem, a decision-maker who is trying to maximize her value inspects a sequence of arriving items to learn their values (drawn from known distributions), and decides when to stop the process by taking the current item. The goal is to prove a "prophet inequality": that she can do approximately as well as a prophet with foreknowledge of all the values. In this work, we investigate this problem when the values are allowed to be correlated. Since non-trivial guarantees are impossible for arbitrary correlations, we consider a natural "linear" correlation structure introduced by Bateni et al. [ESA 2015] as a generalization of the common-base value model of Chawla et al. [GEB 2015]. A key challenge is that threshold-based algorithms, which are commonly used for prophet inequalities, no longer guarantee good performance for linear correlations. We relate this roadblock to another "augmentations" challenge that might be of independent interest: many existing prophet inequality algorithms are not robust to slight increase in the values of the arriving items. We leverage this intuition to prove bounds (matching up to constant factors) that decay gracefully with the amount of correlation of the arriving items. We extend these results to the case of selecting multiple items by designing a new $(1+o(1))$ approximation ratio algorithm that is robust to augmentations. 31 pages. Appears in EC 2020 2020-01-28 2020-05-23 text https://arxiv.org/abs/2001.10600 http://arxiv.org/abs/2001.10600 |
| spellingShingle | Data Structures and Algorithms Computer Science and Game Theory Immorlica, Nicole Singla, Sahil Waggoner, Bo Prophet Inequalities with Linear Correlations and Augmentations |
| title | Prophet Inequalities with Linear Correlations and Augmentations |
| title_full | Prophet Inequalities with Linear Correlations and Augmentations |
| title_fullStr | Prophet Inequalities with Linear Correlations and Augmentations |
| title_full_unstemmed | Prophet Inequalities with Linear Correlations and Augmentations |
| title_short | Prophet Inequalities with Linear Correlations and Augmentations |
| title_sort | prophet inequalities with linear correlations and augmentations |
| topic | Data Structures and Algorithms Computer Science and Game Theory |
| url | https://arxiv.org/abs/2001.10600 http://arxiv.org/abs/2001.10600 |
| work_keys_str_mv | AT immorlicanicole prophetinequalitieswithlinearcorrelationsandaugmentations AT singlasahil prophetinequalitieswithlinearcorrelationsandaugmentations AT waggonerbo prophetinequalitieswithlinearcorrelationsandaugmentations |