No Price Tags? No Problem: Query Strategies for Unpriced Information
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915606849126400 |
|---|---|
| author | Nadimpalli, Shivam Qiao, Mingda Rubinfeld, Ronitt |
| author_facet | Nadimpalli, Shivam Qiao, Mingda Rubinfeld, Ronitt |
| contents | The classic *priced query model*, introduced by Charikar et al. (STOC 2000), captures the task of computing a known function on an unknown input when each input variable can only be revealed by paying an associated cost. The goal is to design a query strategy that determines the function's value while minimizing the total cost incurred. However, all prior work in this model assumes complete advance knowledge of the query costs -- an assumption that fails in many realistic settings.
We introduce a variant of the priced query model that explicitly handles *unknown* variable costs. We prove a separation from the traditional priced query model, showing that uncertainty in variable costs imposes an unavoidable overhead for every query strategy. Despite this, we design strategies that essentially match our lower bound and are competitive with the best cost-aware strategies for arbitrary Boolean functions. Our results build on a recent connection between priced query strategies and the analysis of Boolean functions, and draw techniques from online algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_06170 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | No Price Tags? No Problem: Query Strategies for Unpriced Information Nadimpalli, Shivam Qiao, Mingda Rubinfeld, Ronitt Data Structures and Algorithms Computational Complexity The classic *priced query model*, introduced by Charikar et al. (STOC 2000), captures the task of computing a known function on an unknown input when each input variable can only be revealed by paying an associated cost. The goal is to design a query strategy that determines the function's value while minimizing the total cost incurred. However, all prior work in this model assumes complete advance knowledge of the query costs -- an assumption that fails in many realistic settings. We introduce a variant of the priced query model that explicitly handles *unknown* variable costs. We prove a separation from the traditional priced query model, showing that uncertainty in variable costs imposes an unavoidable overhead for every query strategy. Despite this, we design strategies that essentially match our lower bound and are competitive with the best cost-aware strategies for arbitrary Boolean functions. Our results build on a recent connection between priced query strategies and the analysis of Boolean functions, and draw techniques from online algorithms. |
| title | No Price Tags? No Problem: Query Strategies for Unpriced Information |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2511.06170 |