Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2508.20246 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912752860135424 |
|---|---|
| author | Chawla, Shuchi Christou, Dimitris Dang, Trung |
| author_facet | Chawla, Shuchi Christou, Dimitris Dang, Trung |
| contents | Selection problems with costly information, dating back to Weitzman's Pandora's Box problem, have received much attention recently. We study the general model of Costly Information Combinatorial Selection (CICS) that was recently introduced by Chawla et al. [2024] and Bowers et al. [2025]. In this problem, a decision maker needs to select a feasible subset of stochastic variables, and can only learn information about their values through a series of costly steps, modeled by a Markov decision process. The algorithmic objective is to maximize the total value of the selection minus the cost of information acquisition. However, determining the optimal algorithm is known to be a computationally challenging problem.
To address this challenge, previous approaches have turned to approximation algorithms by considering a restricted class of committing policies that simplify the decision-making aspects of the problem and allow for efficient optimization. This motivates the question of bounding the commitment gap, measuring the worst case ratio in the performance of the optimal committing policy and the overall optimal. In this work, we obtain improved bounds on the commitment gap of CICS through a reduction to a simpler problem of Bayesian Combinatorial Selection where information is free. By establishing a close relationship between these problems, we are able to relate the commitment gap of CICS to ex ante free-order prophet inequalities. As a consequence, we obtain improved efficient approximations for arbitrary instances of the CICS under various feasibility constraints. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_20246 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Commitment Gap via Correlation Gap Chawla, Shuchi Christou, Dimitris Dang, Trung Data Structures and Algorithms Selection problems with costly information, dating back to Weitzman's Pandora's Box problem, have received much attention recently. We study the general model of Costly Information Combinatorial Selection (CICS) that was recently introduced by Chawla et al. [2024] and Bowers et al. [2025]. In this problem, a decision maker needs to select a feasible subset of stochastic variables, and can only learn information about their values through a series of costly steps, modeled by a Markov decision process. The algorithmic objective is to maximize the total value of the selection minus the cost of information acquisition. However, determining the optimal algorithm is known to be a computationally challenging problem. To address this challenge, previous approaches have turned to approximation algorithms by considering a restricted class of committing policies that simplify the decision-making aspects of the problem and allow for efficient optimization. This motivates the question of bounding the commitment gap, measuring the worst case ratio in the performance of the optimal committing policy and the overall optimal. In this work, we obtain improved bounds on the commitment gap of CICS through a reduction to a simpler problem of Bayesian Combinatorial Selection where information is free. By establishing a close relationship between these problems, we are able to relate the commitment gap of CICS to ex ante free-order prophet inequalities. As a consequence, we obtain improved efficient approximations for arbitrary instances of the CICS under various feasibility constraints. |
| title | Commitment Gap via Correlation Gap |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2508.20246 |