  A celebrated impossibility result by Myerson and Satterthwaite (1983) shows
that any truthful mechanism for two-sided markets that maximizes social welfare
must run a deficit, resulting in a necessity to relax welfare efficiency and
the use of approximation mechanisms. Such mechanisms in general make extensive
use of the Bayesian priors. In this work, we investigate a question of
increasing theoretical and practical importance: how much prior information is
required to design mechanisms with near-optimal approximations?
  Our first contribution is a more general impossibility result stating that no
meaningful approximation is possible without any prior information, expanding
the famous impossibility result of Myerson and Satterthwaite.
  Our second contribution is that one {\em single sample} (one number per
item), arguably a minimum-possible amount of prior information, from each
seller distribution is sufficient for a large class of two-sided markets. We
prove matching upper and lower bounds on the best approximation that can be
obtained with one single sample for subadditive buyers and additive sellers,
regardless of computational considerations.
  Our third contribution is the design of computationally efficient blackbox
reductions that turn any one-sided mechanism into a two-sided mechanism with a
small loss in the approximation, while using only one single sample from each
seller. On the way, our blackbox-type mechanisms deliver several interesting
positive results in their own right, often beating even the state of the art
that uses full prior information.
