A Caltech Library Service

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

Page, Scott E. (1994) A Bottom-Up Efficient Algorithm for Allocating Public Projects with Positive Complementarities. Social Science Working Paper, 885. California Institute of Technology , Pasadena, CA. (Unpublished)

[img] PDF (sswp 885 - May 1994) - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Report or Paper (Working Paper)
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.
Group:Social Science Working Papers
Series Name:Social Science Working Paper
Issue or Number:885
Record Number:CaltechAUTHORS:20170822-154731169
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:80705
Deposited By: Jacquelyn Bussone
Deposited On:23 Aug 2017 17:04
Last Modified:03 Oct 2019 18:34

Repository Staff Only: item control page