Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published August 23, 2017 | Submitted
Report Open

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

Page, Scott E.


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.

Additional Information

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.

Attached Files

Submitted - sswp885.pdf


Files (821.3 kB)
Name Size Download all
821.3 kB Preview Download

Additional details

August 20, 2023
August 20, 2023