  We consider the problem of designing query strategies for priced information,
introduced by Charikar et al. In this problem the algorithm designer is given a
function $f : \{0,1\}^n \to \{-1,1\}$ and a price associated with each of the
$n$ coordinates. The goal is to design a query strategy for determining $f$'s
value on unknown inputs for minimum cost.
  Prior works on this problem have focused on specific classes of functions. We
analyze a simple and natural strategy that applies to all functions $f$, and
show that its performance relative to the optimal strategy can be expressed in
terms of a basic complexity measure of $f$, its influence. For $\varepsilon \in
(0,\frac1{2})$, writing $\mathsf{opt}$ to denote the expected cost of the
optimal strategy that errs on at most an $\varepsilon$-fraction of inputs, our
strategy has expected cost $\mathsf{opt} \cdot \mathrm{Inf}(f)/\varepsilon^2$
and also errs on at most an $O(\varepsilon)$-fraction of inputs. This
connection yields new guarantees that complement existing ones for a number of
function classes that have been studied in this context, as well as new
guarantees for new classes.
  Finally, we show that improving on the parameters that we achieve will
require making progress on the longstanding open problem of properly learning
decision trees.
