Pandora's Box Problem With Time Constraints
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911267075129344 |
|---|---|
| author | Amanatidis, Georgios Berger, Ben Ezra, Tomer Feldman, Michal Fusco, Federico Reiffenhäuser, Rebecca Tsikiridis, Artem |
| author_facet | Amanatidis, Georgios Berger, Ben Ezra, Tomer Feldman, Michal Fusco, Federico Reiffenhäuser, Rebecca Tsikiridis, Artem |
| contents | The Pandora's Box problem models the search for the best alternative when evaluation is costly. In the simplest variant, a decision maker is presented with $n$ boxes, each associated with a cost of inspection and a hidden random reward. The decision maker inspects a subset of these boxes one after the other, in a possibly adaptive order, and gains the difference between the largest revealed reward and the sum of the inspection costs. Although this classic version is well understood (Weitzman 1979), there is a flourishing recent literature on variants of the problem. Here we introduce a general framework -- the Pandora's Box Over Time problem -- that captures a wide range of variants where time plays a role, e.g., by constraining the schedules of exploration and influencing costs and rewards. In our framework, boxes have time-dependent rewards and costs, whereas inspection may require a box-specific processing time. Moreover, once a box is inspected, its reward may deteriorate over time. Our main result is an efficient constant-factor approximation to the optimal strategy for the Pandora's Box Over Time problem, which is generally NP-hard to compute. We further obtain improved results for the natural special cases where boxes have no processing time, boxes are available only in specific time slots, or when costs and reward distributions are time-independent (but rewards may still deteriorate after inspection). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_15261 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Pandora's Box Problem With Time Constraints Amanatidis, Georgios Berger, Ben Ezra, Tomer Feldman, Michal Fusco, Federico Reiffenhäuser, Rebecca Tsikiridis, Artem Computer Science and Game Theory Data Structures and Algorithms Probability The Pandora's Box problem models the search for the best alternative when evaluation is costly. In the simplest variant, a decision maker is presented with $n$ boxes, each associated with a cost of inspection and a hidden random reward. The decision maker inspects a subset of these boxes one after the other, in a possibly adaptive order, and gains the difference between the largest revealed reward and the sum of the inspection costs. Although this classic version is well understood (Weitzman 1979), there is a flourishing recent literature on variants of the problem. Here we introduce a general framework -- the Pandora's Box Over Time problem -- that captures a wide range of variants where time plays a role, e.g., by constraining the schedules of exploration and influencing costs and rewards. In our framework, boxes have time-dependent rewards and costs, whereas inspection may require a box-specific processing time. Moreover, once a box is inspected, its reward may deteriorate over time. Our main result is an efficient constant-factor approximation to the optimal strategy for the Pandora's Box Over Time problem, which is generally NP-hard to compute. We further obtain improved results for the natural special cases where boxes have no processing time, boxes are available only in specific time slots, or when costs and reward distributions are time-independent (but rewards may still deteriorate after inspection). |
| title | Pandora's Box Problem With Time Constraints |
| topic | Computer Science and Game Theory Data Structures and Algorithms Probability |
| url | https://arxiv.org/abs/2407.15261 |