A lower bound on computational complexity given by revelation mechanisms

DOI10.1007/BF01213904zbMATH Open0854.68045MaRDI QIDQ1920945FDOQ1920945

Authors: Stanley Reiter, Kenneth R. Mount 

Publication date: 20 October 1996

Published in: Economic Theory (Search for Journal in Brave)

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

zbMATH Keywords

computational complexity

Mathematics Subject Classification ID

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

Cites Work

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

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)