Characterizing Truthful Market Design

Опубликовано 7 сентября 2016, 16:46

We characterize the family of truthful double-sided auctions. Despite the importance of double-sided auctions to market design, there is no characterization of truthful double-sided auctions. This paper characterizes the truthful mechanisms for double-sided auctions by generalizing RobertsΓÇÖ theorem, to show that truthful double-sided auctions must almost be affine maximizers. Our main result utilizes a novel form of reduction which we call a truth-preserving reduction. The truth-preserving reduction is used to reduce the double-sided auction to a special case of a combinatorial auction and make use of the impossibility result proven in Lavi, Mualem, and Nisan. Intuitively, our proof shows that truthful double-sided auctions are as hard to design as truthful combinatorial auctions. Two important concepts are developed in addition to the main result. First, the form of reduction used in this paper is of independent interest as it opens the possibility of directly comparing mechanism design problems by their design difficulty. Second, a notion of extension of payments is defined; which given a set of payments for some players finds payments for the remaining players. Several properties of such extensions are shown. Joint work with Mira Gonen and Rica Gonen.