Discrete allocation mechanisms: Dimensional requirements for resource- allocation mechanisms when desired outcomes are unbounded (Q1083342)

This paper develops techniques for constructing informationally efficient privacy-preserving resource allocation mechanisms for the case where desired-outcome functions are unbounded on the set of possible environments and the message space is infinite although not continuous. This is an extension of an earlier paper by the same authors, which considered the case where the mechanisms are continuous and desired- outcome functions are bounded. Efficiency is defined with regard to the message-space size measures. An error is the maximum distance between the Pareto-optimal and the equilibrium outcomes over all economies. A desired-outcome function assigns a set of desired outcomes to each environment. The paper shows that for the class \((E^*)\) of (parameterized) two- person, two-commodity linear-quadratic exchange economies with integers as permissible outcomes, a lower bound of error is 1/2. Although there does not exist one that is capable of attaining the lower bound of exact 1/2 as its error, one can find a mechanism with error arbitrarily close to the lower bound of 1/2 at least for large subsets of \(E^*\). Such a mechanism is obtained by using a discrete mechanism which (i) has a two tuple message space, (ii) approximates the continuum Walrasian mechanism in a ''round-off'' manner, and (iii) rescales every message (divide it by a suitable constant) in forming response. Moreover, the rescaled Walrasian mechanism has minimal message-space size among all pseudo-Lipschitzian (smooth) integer-outcome mechanisms defined over \(E^*\) which have errors arbitrarily close to the lower bound implied by integer outcomes.