A Bottom-Up Efficient Algorithm for Allocating Public Projects with Positive Complementarities
- Creators
- Page, Scott E.
Abstract
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
| Name | Size | Download all |
|---|---|---|
|
md5:695683a7bf42844989cfee779b0f5e74
|
821.3 kB | Preview Download |
Additional details
- Eprint ID
- 80705
- Resolver ID
- CaltechAUTHORS:20170822-154731169
- Created
-
2017-08-23Created from EPrint's datestamp field
- Updated
-
2019-10-03Created from EPrint's last_modified field
- Caltech groups
- Social Science Working Papers
- Series Name
- Social Science Working Paper
- Series Volume or Issue Number
- 885