Our main result of characterizing double-sided auctions required the creation of a new set of tools, reductions that preserve economic properties. This paper utilizes two such reductions; a \emph{truth-preserving reduction} and a \emph{non-affine preserving reduction}. The truth-preserving reduction is used to reduce the double-sided auction to a special case of a combinatorial auction to make use of the impossibility result proved in \cite{LMN:03}. 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 provides a means for comparing mechanism design problems by design difficulty. Second, we define the notion of \emph{extension of payments}; which given a set of payments for some players finds payments for the remaining players. The extension payments maintain the truthful and affine maximization properties.