Mechanisms that efficiently verify the optimality of a proposed action

The best known achievement of the literature on resource-allocating mechanisms and their message spaces is the first rigorous proof of the competitive mechanism's informational efficiency. In an exchange economy withN persons andK+1 commodities (including a numeraire), that mechanism announcesK prices as well as aK-compenent trade vector for each ofN−1 persons, making a total ofNK message variables. Trial messages are successively announced and after each announcement each personprivately determines, usingprivate information, whether she finds the proposed trades acceptable at the announced prices. When a message is reached with which all are content, then the trades specified in that message take place, and they satisfy Pareto optimality and individual rationality. The literature shows that no (suitably regular) mechanism can achieve the same thing with fewer thanNK message variables. In the classic proof, all the candidate mechanisms have the privacy property, and the proof uses that property in a crucial way. ‘Non-private’ mechanisms are, however, well-defined. We present a proof that forN>K,NK remains a lower bound even when we permit ‘non-private’ mechanisms. Our new proof does not use privacy at all. But in a non-private mechanism, minimality of the number of message variables can hardly be defended as the hallmark of informational efficiency, since a non-private mechanism requires some persons to know something about the private information of othersin addition to the information contained in the messages. The new proof of the lower boundNK invites a new interpretation of the competitive mechanism's informational efficiency. We provide a new concept of efficiency which the competitive mechanism exhibits and which does rest on privacy even whenN>K. To do so, we first define a class ofprojection mechanisms, wherein some of the message variables are proposed values of the action to be taken, and the rest are auxiliary variables. The competitive mechanism has the projection property, with a trade vector as its action and prices as the auxiliary variables. A projection mechanism proposes an action; for each proposal, the agents then use the auxiliary variables, together with their private information, to verify that the proposed action meets the mechanism's goal (Pareto optimality and individual rationality for the competitive mechanism) if, indeed, it does meet that goal. For a given goal, we seek projection mechanisms for which theverification effort (suitably measured) is not greater than that of any other projection mechanism that achieves the goal. We show the competitive mechanism to be verification-minimal within the class of private projection mechanisms that achieve Pareto optimality and individual rationality; that proofdoes use the privacy of the candidate mechanisms. We also show, under certain conditions, that a verification-minimal projection mechanism achieving a given goal has smallest ‘total communication effort’ (which is locally equivalent to the classic ‘message-space size’) among all private mechanisms that achieve the goal, whether or not they have the projection property.