Optimal Communication in Truthful Mechanisms

Abstract

This thesis is concerned with efficient preference elicitation in the field of Algorithmic Mechanism Design. More precisely, our goal is to minimize the elicited number of bits from the agents without sacrificing the other desired properties of the mechanism, namely the incentive compatibility guarantee and the social welfare. In this context, our main contribution is twofold. First, we show how to implement a series of well-known mechanisms from Auction Theory with asymptotically optimal communication. Specifically, we initially turn our attention to single-parameter domains, namely single item and multi-unit auctions. For the former, we show that Vickrey's auction can be implemented with an expected communication complexity of at $1 + \epsilon$ bits -- on average -- per bidder, for any $\epsilon > 0$, assuming that the valuations can be represented with a constant number of bits. As a corollary, we provide a compelling method to increment the price in English auctions. Moreover, we design efficient encoding schemes in order to obtain the same asymptotic bound for multi-item auctions with additive bidders and a constant number of items, and for multi-unit auctions with unit demand bidders. Our results follow from simple sampling schemes and do not require any prior knowledge on the agents' parameters. Moreover, we consider Moulin's generalized median mechanism on metric spaces endowed with the $L^1$ norm. This mechanism is of fundamental importance in the realm of Social Choice as it circumvents the Gibbard-Satterthwaite impossibility theorem for the natural setting of single-peaked preferences. We show that a sampling approximation of the median achieves a $1 + \epsilon$ approximation of the optimal social cost, for any $\epsilon > 0$, with a constant sample $c = c(\epsilon)$. Thus, our sampling approximation incurs an arbitrarily small error with an arbitrarily small fraction of the total information. Our main result is established based on the asymptotic characterization of a distribution, and could be of independent interest.