p.1293

Simultaneous Search

Hector Chade
Lones Smith

Abstract

We introduce and solve a new class of "downward-recursive" static portfolio choice problems. An individual simultaneously chooses among ranked stochastic options, and each choice is costly. In the motivational application, just one may be exercised from those that succeed. This often emerges in practice, such as when a student applies to many colleges or when a firm simultaneously tries several technologies.We show that such portfolio choice problems quite generally entail maximizing a submodular function of finite sets—which is NP-hard in general. Still, we show that a greedy algorithm finds the optimal set, finding first the best singleton, then the best single addition to it, and so on. We show that the optimal choices are "less aggressive" than the sequentially optimal ones, but "more aggressive" than the best singletons. Also, the optimal set in general contains gaps. We provide some comparative statics results on the chosen set.