A lower bound on computational complexity given by revelation mechanisms

DOI10.1007/BF01213904MaRDI QIDQ1920945zbMATH OpenFDO

Authors Stanley Reiter, Kenneth R. Mount

Publication date 20 October 1996

Published in Economic Theory (Search for Journal in Brave)

zbMATH Keywords

computational complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) General equilibrium theory (91B50) Boolean functions (06E30)

Recommendations

• A lower bound for the dimension of the message space of the decentralized mechanisms realizing a given goal
• Computation and Complexity in Economic Behavior and Organization
• Applications of matrix methods to the theory of lower bounds in computational complexity
• On rational computability and communication complexity
• Distributed Algorithmic Mechanism Design and Algebraic Communication Complexity

Cites work

• scientific article; zbMATH DE number 3980852 (Why is no real title available?)
• scientific article; zbMATH DE number 3461174 (Why is no real title available?)
• scientific article; zbMATH DE number 3214660 (Why is no real title available?)
• scientific article; zbMATH DE number 3307591 (Why is no real title available?)
• scientific article; zbMATH DE number 3367095 (Why is no real title available?)
• scientific article; zbMATH DE number 3402334 (Why is no real title available?)
• scientific article; zbMATH DE number 3055561 (Why is no real title available?)
• A lower bound for the dimension of the message space of the decentralized mechanisms realizing a given goal
• A note on the interrelation of subsets of independent variables of a continuous function with continuous first derivatives
• An Axiomatic Characterization of the Price Mechanism
• Bounded complexity justifies cooperation in the finitely repeated prisoners' dilemma
• Decentralized dynamic processes for finding equilibrium
• Effective Price Mechanisms
• Finite Rationality and Interpersonal Complexity in Repeated Games
• Finite automata play the repeated prisoner's dilemma
• Game Forms with Minimal Message Spaces
• Incentive compatibility and informational requirements
• Lower Bounds on Information Transfer in Distributed Computations
• Necessary and sufficient conditions for the existence of a locally stable message process
• The competitive allocation process is informationally efficient uniquely

Cited in

(3)

• Computational implementation
• A lower bound for the dimension of the message space of the decentralized mechanisms realizing a given goal
• Implementing a generic smooth function

This page was built for publication: A lower bound on computational complexity given by revelation mechanisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1920945)