This file is part of IDEAS, which uses RePEc data


[ Papers | Articles | Software | Books | Chapters | Authors | Institutions | JEL Classification | NEP reports | Search | New papers by email | Author registration | Rankings | Volunteers | FAQ | Blog | Help! ]

A lower bound on computational complexity given by revelation mechanisms (*)

Author info | Abstract | Publisher info | Download info | Related research | Statistics
Author Info
Kenneth R. Mount
Stanley Reiter

Additional information is available for the following registered author(s):

Abstract

This paper establishes a lower bound on the computational complexity of smooth functions between smooth manifolds. It generalizes one for finite (Boolean) functions obtained (by Arbib and Spira [2]) by counting variables. Instead of a counting procedure, which cannot be used in the infinite case, the dimension of the message space of a certain type of revelation mechanism provides the bound. It also provides an intrinsic measure of the number of variables on which the function depends. This measure also gives a lower bound on computational costs associated with realizing or implementing the function by a decentralized mechanism, or by a game form.

Download Info
To our knowledge, this item is not available for download. To find whether it is available, there are three options:
1. Check below under "Related research" whether another version of this item is available online.
2. Check on the provider's web page whether it is in fact available.
3. Perform a search for a similarly titled item that would be available.

Publisher Info
Article provided by Springer in its journal Economic Theory.

Volume (Year): 7 (1996)
Issue (Month): 2 ()
Pages: 237-266
Download reference. The following formats are available: HTML (with abstract), plain text (with abstract), BibTeX, RIS (EndNote, RefMan, ProCite), ReDIF
Handle: RePEc:spr:joecth:v:7:y:1996:i:2:p:237-266

Contact details of provider:
Web page: http://link.springer.de/link/service/journals/00199/index.htm

Order Information:
Web: http://link.springer.de/orders.htm

For technical questions regarding this item, or to correct its listing, contact: (Christopher F Baum).

Related research
Keywords:

Other versions of this item:

References listed on IDEAS
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
  1. Stefan Reichelstein, 1981. "On the Informational Requirements for the Implementation of Social Choice Rules," Discussion Papers 507, Northwestern University, Center for Mathematical Studies in Economics and Management Science. [Downloadable!]
  2. Chen, Pengyuan, 1992. "A lower bound for the dimension of the message space of the decentralized mechanisms realizing a given goal," Journal of Mathematical Economics, Elsevier, vol. 21(3), pages 249-270. [Downloadable!] (restricted)
  3. Saari, Donald G & Simon, Carl P, 1978. "Effective Price Mechanisms," Econometrica, Econometric Society, vol. 46(5), pages 1097-1125, September. [Downloadable!] (restricted)
  4. Neyman, Abraham, 1985. "Bounded complexity justifies cooperation in the finitely repeated prisoners' dilemma," Economics Letters, Elsevier, vol. 19(3), pages 227-229. [Downloadable!] (restricted)
  5. Jordan, J. S., 1982. "The competitive allocation process is informationally efficient uniquely," Journal of Economic Theory, Elsevier, vol. 28(1), pages 1-18, October. [Downloadable!] (restricted)
  6. Kalai, Ehud & Stanford, William, 1988. "Finite Rationality and Interpersonal Complexity in Repeated Games," Econometrica, Econometric Society, vol. 56(2), pages 397-410, March. [Downloadable!] (restricted)
    Other versions:
  7. Kenneth R. Mount & Stanley Reiter, 1983. "On the Existence of a Locally Stable Dynamic Process With a Statically Minimal Message Space," Discussion Papers 550, Northwestern University, Center for Mathematical Studies in Economics and Management Science. [Downloadable!]
  8. Sonnenschein, Hugo, 1974. "An Axiomatic Characterization of the Price Mechanism," Econometrica, Econometric Society, vol. 42(3), pages 425-33, May. [Downloadable!] (restricted)
  9. Reichelstein, Stefan, 1984. "Incentive compatibility and informational requirements," Journal of Economic Theory, Elsevier, vol. 34(1), pages 32-51, October. [Downloadable!] (restricted)
  10. Mount, Kenneth & Reiter, Stanley, 1974. "The informational size of message spaces," Journal of Economic Theory, Elsevier, vol. 8(2), pages 161-192, June. [Downloadable!] (restricted)
    Other versions:
Full references

Cited by:
(explanations, Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.)

  1. Van Zandt, Timothy, 2003. "Real-Time Hierarchical Resource Allocation with Quadratic Costs," CEPR Discussion Papers 4022, C.E.P.R. Discussion Papers. [Downloadable!] (restricted)
  2. Ehud Kalai, 1995. "Games," Discussion Papers 1141, Northwestern University, Center for Mathematical Studies in Economics and Management Science. [Downloadable!]
Statistics
Access and download statistics

Did you know? Cannot find something on IDEAS? Encourage the publisher to index it! Instructions.

This page was last updated on 2009-11-25.

This information is provided to you by IDEAS at the Department of Economics, College of Liberal Arts and Sciences, University of Connecticut using RePEc data on a server sponsored by the Society for Economic Dynamics.