No Price Tags? No Problem: Query Strategies for Unpriced Information
Shivam Nadimpalli, Mingda Qiao, Ronitt Rubinfeld · 2025
Read No Price Tags? No Problem: Query Strategies for Unpriced Information by Shivam Nadimpalli, Mingda Qiao, Ronitt Rubinfeld (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-06170.txt.
Introduction
Shivam Nadimpalli, Mingda Qiao, and Ronitt Rubinfeld revisit a classic model where learning each unknown input bit costs money. In the priced query model, the aim is to compute a known function while paying as little as possible. Every earlier study assumed all prices are known in advance, an assumption real settings often break.
The authors define a variant where variable costs are unknown ahead of time. They prove that this uncertainty forces an unavoidable extra cost on every possible strategy. Even so, their new strategies nearly match that lower bound and rival the best price-aware strategies for arbitrary Boolean functions, drawing on online algorithm techniques.
Catalog record
| CREATOR | Shivam Nadimpalli, Mingda Qiao, Ronitt Rubinfeld |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 137 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-06170
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
No Price Tags? No Problem: Query Strategies for Unpriced Information Shivam Nadimpalli, Mingda Qiao, Ronitt Rubinfeld Abstract The classic priced query model introduced by Charikar et al. (STOC 2000) captures the task of computing a known function on an unknown input, where 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. All prior work in this model, however, assumes complete advance knowledge of these query costs—an assumption that breaks down dramatically in many realistic settings. We introduce a variant of the priced query model designed explicitly to handle 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 are able to give query strategies that essentially match our lower bound and are competitive with the best-known cost-aware strategy for an arbitrary Boolean function. Our results build on a recent connection between priced query strategies and the analysis of Boolean functions, and also draw on techniques from online algorithms. 1 Introduction Information is rarely free, and its value is often revealed only after the cost to acquire it has been paid. A scientist may devote weeks to running an experiment, only to find the results inconclusive; a data analyst may purchase costly annotations that add little insight; a policymaker may commission new surveys, learning only afterward which questions truly mattered. Even in familiar settings—medical diagnostics or crowd-sourced data collection—each “query” carries a cost and a payoff that remain unknown until a response has been obtained. The same tension arises in collective decision-making: for instance, the U.S. Electoral College can be viewed as a “majority of majorities” function, where confident prediction demands focusing effort on the few states whose outcomes remain uncertain. Additionally, costly observations may sometimes yield no new information, whereas a single inexpensive one can sometimes decisively influence the outcome. The same fundamental difficulty runs through all these scenarios: an overall outcome depends on many unknown variables—not all of which may need to be learned—yet revealing each variable carries a cost that is itself unknown in advance. The challenge is to allocate effort strategically: which variables to reveal, and in what order, when each becomes known only once its cost threshold has been met. To capture this problem, we introduce a theoretical model of information acquisition under unknown query costs. Our framework extends the classical priced query model of Charikar, Fagin, Guruswami, Kleinberg and Raghavan [ 9 ] to an “online” setting, where the cost required to reveal a variable is hidden until the cumulative investment surpasses its threshold. We begin by briefly recalling the classical model. Background: Query Strategies for Priced Information. The priced query model introduced in [ 9 ] provides a clean abstraction for decision-making when query costs are known in advance. In this model, the goal is to evaluate a Boolean function f\mathrel{\mathop{\ordinarycolon}}\{0,1\}^{n}\to\{0,1\} on an unknown input x\in\{0,1\}^{n} , where each input bit can only be revealed by paying a specified cost. The challenge is to design query strategies that minimize the total cost incurred by the algorithm. Over the past two decades, there has been substantial work designing priced query strategies for various function classes; an incomplete list includes [ 12 , 13 , 14 , 11 , 15 , 16 , 18 , 1 , 22 , 28 , 5 , 26 , 27 , 21 ] among many others. The work of Charikar et al. [ 9 ] also inspired priced variants of other basic algorithmic tasks such as learning [ 35 ] , optimization [ 41 ] , and search or sorting [ 25 , 34 ] . The problem has also been extensively studied within the operations research community under the label of sequential testing [ 42 ] . This Work: Query Strategies for Unpriced Information. The classical model, however, assumes that the algorithm knows all query costs in advance—an assumption that fails dramatically in many natural settings. In practice, the cost of uncovering information is often uncertain: we discover how expensive a variable is only through the process of revealing it. This brings us to the focus of the present work: Can we design effective query strategies for unpriced information? In other words, we consider the task of designing query strategies in the setting when the variable costs are entirely unknown to the algorithm. We study this problem in the framework of competitive analysis, where our goal is to design query strategies whose total cost is comparable to that of the optimal algorithm that knows the variable costs in advance. Throughout, we refer to this setting as the “online” model, to distinguish it from the “offline” (known-cost) framework of [ 9 ] . We note that our problem bears resemblance to several models in the online algorithms literature, such as threshold queries and Pandora’s box. These online frameworks incorporate uncertainty and sequential revelation, yet they typically do not aim to evaluate a fixed Boolean function; the emphasis there is often on regret or reward objectives rather than computing a prescribed function of the inputs. Conversely, the classical priced-query model assumes complete knowledge of all costs in advance. (We refer the reader to Section 1.2 for a detailed discussion of related work.) Our work bridges these two areas, both conceptually and technically. Algorithmically, we draw on ideas from the query-strategies literature—particularly influence-based techniques from the analysis of Boolean functions, building on a recent connection highlighted by Blanc, Lange, and Tan [ 5 ] —as well as tools from online algorithms, including martingale arguments and testing/consistency checks. In addition to our algorithmic contributions, we establish lower bounds for both specific strategies and general online query algorithms. We believe that the ideas and techniques developed here will find broader applications across these domains. 1.1 Our Results For the sake of readability, we restrict ourselves to our main algorithmic results and lower bounds in the discussion below. We summarize all our results in Table 1 , and give a detailed technical overview in Section 2 . 1.1.1 Problem Setup We start with an informal overview of our setup and refer the reader to Section 3.2 for a precise formulation. Throughout, we assume that the goal is to compute a Boolean function f\mathrel{\mathop{\ordinarycolon}}\{0,1\}^{n}\to\{0,1\} on an unknown input x\in\{0,1\}^{n} . We also denote the fixed (but unknown) vector of costs as c\in\mathbb{R}_{\geq 0}^{n} . At each time step, the algorithm may invest in a single variable; its cumulative investment is maintained as a vector \theta\in\mathbb{R}^{n} . The variable x_{i} is revealed to the algorithm when \theta_{i}\geq c_{i} . We consider both zero-error algorithms (i.e. algorithms that correctly compute f(x) on every input x\in\{0,1\}^{n} ) as well as \varepsilon -error algorithms (i.e. algorithms which are allowed to err in computing f(\boldsymbol{x}) for \varepsilon -fraction of \boldsymbol{x}\sim\{0,1\}^{n} ). We benchmark our algorithms in terms of both the optimal average cost and the worst-case cost among all offline algorithms. For example, \mathrm{opt}^{\mathrm{avg}}_{0}\mathrel{\mathop{\ordinarycolon}}=\mathrm{opt}^{\mathrm{avg}}_{0}(f,c) will denote the optimal expected cost among all zero-error offline algorithms computing f(\boldsymbol{x}) on a uniformly random \boldsymbol{x}\sim\{0,1\}^{n} ; we correspondingly define \mathrm{opt}^{\mathrm{avg}}_{\varepsilon} , \mathrm{opt}^{\mathrm{w}}_{0}