Simultaneous selection

We generalize Chade and Smith’s (2006) simultaneous search problem to a class of discrete optimization problems. More precisely, we study the problem of maximizing a weighted sum of utilities of objects minus the sum of costs of acquiring these objects, given the constraint that the sum of weights cannot exceed the value of some submodular function.We show that the problem has a simple solutions in the particular case in which the submodular function depends only on the number of objects. Namely, the optimal set of objects can be found by the greedy algorithm. We provide some economic applications of this result. The particular case studied in the present paper, and the particular case studied by Chade and Smith complement one another, but they do not exhaust all instances of our general discrete optimization problem. We also show that in the general case the problem does not have a simple solution.