Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.24132 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915520213680128 |
|---|---|
| author | Correa, José Gergatsouli, Evangelia Ziliotto, Bruno |
| author_facet | Correa, José Gergatsouli, Evangelia Ziliotto, Bruno |
| contents | We investigate the role of commitment in optimal stopping by studying all the variants between Prophet Inequality (PI) and Pandora's Box (PB). Both problems deal with a set of variables drawn from known distributions.
In PI the gambler observes an adversarial order of these variables with the goal of selecting one that maximizes the expected value against a prophet who knows the exact values realized. The gambler has to irrevocably decide at each step whether to select the value or discard it (commitment).
On the other hand, in PB the gambler selects the order of inspecting the variables and for each pays an observation cost to see the actual value realized, aiming to choose one to maximize the net cost of the value chosen minus the observation cost paid. The gambler in PB can return and select any variable already seen (no commitment).
For all the variants between these problems that arise by changing parameters such as (1) commitment (2) observation cost (3) order selection, we concisely summarize the known results and fill the gaps of variants not yet studied. We also uncover connections to Ski-Rental, a classic online algorithm problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_24132 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Role of Commitment in Optimal Stopping Correa, José Gergatsouli, Evangelia Ziliotto, Bruno Data Structures and Algorithms We investigate the role of commitment in optimal stopping by studying all the variants between Prophet Inequality (PI) and Pandora's Box (PB). Both problems deal with a set of variables drawn from known distributions. In PI the gambler observes an adversarial order of these variables with the goal of selecting one that maximizes the expected value against a prophet who knows the exact values realized. The gambler has to irrevocably decide at each step whether to select the value or discard it (commitment). On the other hand, in PB the gambler selects the order of inspecting the variables and for each pays an observation cost to see the actual value realized, aiming to choose one to maximize the net cost of the value chosen minus the observation cost paid. The gambler in PB can return and select any variable already seen (no commitment). For all the variants between these problems that arise by changing parameters such as (1) commitment (2) observation cost (3) order selection, we concisely summarize the known results and fill the gaps of variants not yet studied. We also uncover connections to Ski-Rental, a classic online algorithm problem. |
| title | The Role of Commitment in Optimal Stopping |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2509.24132 |