Optimal Allocation of Very Limited Search Resources

Abstract

This paper presents a probabilistic model for studying the question: given n search resources, where in the search tree should they be expended? Specifically, a least-cost root-to-leaf path is sought in a random tree. The tree is known to be binary and complete to depth N. Arc costs are independently set either to 1 (with probability p) or to 0 (with probability 1-p). The cost of a leaf is the sum of the arc costs on the path from the root to that leaf. The searcher (scout) can learn n arc values. How should these scarce resources be dynamically allocated to minimize the average cost of the leaf selected? A natural decision rule for the scout is to allocate resources to arcs that lie above leaves whose current expected cost is minimal. The bad-news theorem says that situations exist for which this rule is nonoptimal, no matter what the value of n. The good-news theorem counters this: for a large class of situations, the aforementioned rule is an optimal decision rule if p ≤ 0.5 and within a constant of optimal if p > 0.5. This report discusses the lessons provided by these two theorems and presents the proof of the bad-news theorem.