Comparing finite mechanisms

Summary. This paper obtains finite analogues to propositions that a previous literature obtained about the informational efficiency of mechanisms whose possible messages form a continuum. Upon reaching an equilibrium message, to which all persons “agree”, a mechanism obtains an action appropriate to the organization's environment. Each person's privately observed characteristic (a part of the organization's environment) enters her agreement rule. An example is the Walrasian mechanism in an exchange economy. There a message specifies a proposed trade vector for each trader as well as a price for each non-numeraire commodity. A trader agrees if the price of each non-numeraire commodity equals her marginal utility for that commodity (at the proposed trades) divided by her marginal utility for the numeraire. At an equilibrium message, the mechanism's action consists of the trades specified in that message, and (for classic economies) those trades are Pareto-optimal and individually rational. Even though the space of environments (characteristics) is a continuum, mechanisms with a continuum of possible messages are unrealistic, since transmitting every point of a continuum is impossible. In reality, messages have to be rounded off and the number of possible messages has to be finite. Moreover, reaching a continuum mechanism's equilibrium message typically requires infinite time and that difficulty is absent if the number of possible messages is finite. The question therefore arises whether results about continuum mechanisms have finite counterparts. If we measure a continuum mechanism's communication cost by its message-space dimension, then our corresponding cost measure for a finite mechanism is the (finite) number of possible equilibrium messages. We find that if two continuum mechanisms yield the same action but the first has higher message-space dimension, then a sufficiently fine finite approximation of the first has larger error than an approximation of the second if the cost of the first approximation is no higher than the cost of the second approximation. An approximation's “error” is the largest distance between the continuum mechanism's action and the approximation's action. We obtain bounds on error. We also study the performance of Direct Revelation (DR) mechanisms relative to “indirect” mechanisms, both yielding the same action, when the environment set grows. We find that as the environment-set dimension goes to infinity, so does the extra cost of the DR approximation, if the error of the DR approximation is at least as small as the error of the indirect approximation. While the paper deals with information-processing costs and not incentives, it is related to the incentive literature, since the Revelation Principle is central to much of that literature and one of our main results is the informational inefficiency of finite Direct Revelation mechanisms. Received: May 21, 2001; revised version: December 14, 2001 RID="*" ID="*" Earlier versions of this paper were presented at the Decentralization Conference, Washington University, St Louis, April 2000 and at the Eighth World Congress of the Econometric Society, August 2000. We are grateful for comments received on those occasions. The second author gratefully acknowledges support from National Science Foundation grant #IIS9712131. Correspondence to: T. Marschak