A Lower Bound on Computational Complexity Given by Revelation Mechanisms

Kenneth R. Mount and Stanley Reiter

No 1085, Discussion Papers from Northwestern University, Center for Mathematical Studies in Economics and Management Science

Abstract: 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.

Date: 1994-03
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.kellogg.northwestern.edu/research/math/papers/1085.pdf main text (application/pdf)

Related works:
Journal Article: A lower bound on computational complexity given by revelation mechanisms (*) (1996)
Journal Article: A Lower Bound on Computational Complexity Given by Revelation Mechanisms (1996)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:nwu:cmsems:1085

Ordering information: This working paper can be ordered from

Access Statistics for this paper

More papers in Discussion Papers from Northwestern University, Center for Mathematical Studies in Economics and Management Science Center for Mathematical Studies in Economics and Management Science, Northwestern University, 580 Jacobs Center, 2001 Sheridan Road, Evanston, IL 60208-2014. Contact information at EDIRC.
Bibliographic data for series maintained by Fran Walker ( this e-mail address is bad, please contact ).