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.
This paper was a portion of the author's dissertation from Northwestern University. The author's committee members: Mark Satterthwaite, Roger Myerson, and Matthew Jackson and, especially his chairman, Stan Reiter, deserve many thanks for their support, guidance, and advice. Gordon Green and Mike Kirschenheiter commented on and improved several early versions of this paper.
Submitted - sswp885.pdf