In this paper, lowest cost algorithms are described for finding the value of a Boolean function by sequentially assigning values to variables, in the case when each input variable has an associated price. A corresponding situation is when software agents are purchasing information from various sources, at various prices, and need to know the best strategy for choosing the sequence of questions.

The basic function studied is an and/or tree with the input variables at the ends of the branches. The strategy of the algorithm is to assign values to variables, so as to balance the total price over all variables. This balancing is done by computing in an inductive fashion, with lower bounds on the costs associated with the subtrees emanating from the pertinent variables. The main result is that the computations are time polynomial in the size of the tree. No coding of the algorithm is presented, and the paper does not include empirical results on the effectiveness of the algorithm for reasonable examples.

The “dual” problem is also considered: what set of prices causes every evaluation algorithm to achieve an optimal result? Such a price vector does exist, and can be found efficiently.

A final problem addressed is searching a sorted array to determine if a particular number is contained, when each query has a price associated with it. Elaborate, but reasonable bounds on the effectiveness of the algorithm are reported.

There are elegant mathematics presented in this thorough paper (almost a monograph). It’s not clear when this approach would actually be useful.