A Lower Bound on Computational Complexity Given by Revelation Mechanisms
This paper establishes an elementary lower bound on the computational complexity of smooth functions between Euclidean spaces(actually, smooth manifolds). The main motivation for this comes from mechanism design theory. The complexity of computations required by a mechanism determines an element of the costs associated with that mechanism. The lower bound presented in this paper is useful in part because it does not require specification in detail of the computations to be performed by the mechanism, but depends only on the goal function that the mechanism is to realize or implement.
Year of publication: |
1994-03
|
---|---|
Authors: | Mount, Kenneth R. ; Reiter, Stanley |
Institutions: | Center for Mathematical Studies in Economics and Management Science (CMS-EMS), Kellogg Graduate School of Management |
Saved in:
freely available
Saved in favorites
Similar items by person
-
Construction of a Continuous Utility Function for a Class of Preferences
Mount, Kenneth R., (1975)
-
Continuous Representation of Preferences
Mount, Kenneth R., (1974)
-
On the Existence of a Locally Stable Dynamic Process With a Statically Minimal Message Space
Mount, Kenneth R., (1983)
- More ...