Pandora with Inaccurate Priors
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929700171939840 |
|---|---|
| author | Banihashem, Kiarash Chen, Xiang Hajiaghayi, MohammadTaghi Kim, Sungchul Mahadik, Kanak Rossi, Ryan Yu, Tong |
| author_facet | Banihashem, Kiarash Chen, Xiang Hajiaghayi, MohammadTaghi Kim, Sungchul Mahadik, Kanak Rossi, Ryan Yu, Tong |
| contents | We investigate the role of inaccurate priors for the classical Pandora's box problem. In the classical Pandora's box problem we are given a set of boxes each with a known cost and an unknown value sampled from a known distribution. We investigate how inaccuracies in the beliefs can affect existing algorithms. Specifically, we assume that the knowledge of the underlying distribution has a small error in the Kolmogorov distance, and study how this affects the utility obtained by the optimal algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_03574 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Pandora with Inaccurate Priors Banihashem, Kiarash Chen, Xiang Hajiaghayi, MohammadTaghi Kim, Sungchul Mahadik, Kanak Rossi, Ryan Yu, Tong Data Structures and Algorithms We investigate the role of inaccurate priors for the classical Pandora's box problem. In the classical Pandora's box problem we are given a set of boxes each with a known cost and an unknown value sampled from a known distribution. We investigate how inaccuracies in the beliefs can affect existing algorithms. Specifically, we assume that the knowledge of the underlying distribution has a small error in the Kolmogorov distance, and study how this affects the utility obtained by the optimal algorithm. |
| title | Pandora with Inaccurate Priors |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2502.03574 |