A Bottom-Up Efficient Algorithm for Allocating Public Projects with Positive Complementarities

In this paper, we consider the problem of locating an optimal package of public projects from a set of potential projects when the public projects have positive complementarities. We formulate the problem as a discrete nonlinear optimization problem whose domain equals the power set of a finite collection of projects. The main contribution of this paper is the construction of an efficient algorithm, among the set of bottom-up algorithms, for projects with positive and positive uniform complementarities. The restriction to bottom-up algorithms sterns from practical considerations discussed in the paper. We also discuss shortcomings of three natural approaches to addressing the problem: exhaustive search over packages, simultaneous evaluation of projects, and sequential evaluation of projects.