Despite the importance of matching-double-sided auctions to market design, to date no characterization of truthful matching-double-sided auctions was made. This paper characterizes truthful mechanisms for matching-double-sided auctions by generalizing Roberts' classic result to show that truthful matching-double-sided auctions must "almost" be affine maximizers.

Characterizing truthful matching-double-sided auctions required the creation of a new set of tools, reductions that preserve economic properties. This paper utilizes two such reductions; a truth-preserving reduction and a non-affine preserving reduction. The truth-preserving reduction is used to reduce the matching-double-sided auction to a special case of a combinatorial auction to allow us to make use of the impossibility result proved in Mu’alem and Nisan 2003. Intuitively, our proof shows that truthful matching-double-sided auctions are as hard to design as truthful combinatorial auctions with multi-minded payers.

In addition to the main result the paper develops two important concepts. First, the form of reduction used in this paper is of independent interest as it presents a solution to the question of how to compare mechanism design problems by design difficulty. Second, we define the notion of extension of payments; which is to say that given a set of payments for some players our extension of payments notion finds payments for the remaining players that maintains the truthful and affine maximization properties.

The truthful double-sided auction problem for single parameter players is similar to the truthful combinatorial auction problem for single parameter players where many non affine maximizing solutions exist. McAfee's mechanism provides a non affine maximizing solution for the truthful double-sided auction problem with single parameter players. Our paper focuses on characterizing the case where players are multi minded.

The paper is available at http://www.ricagonen.com/papers/RGonenDSA.pdf.