Before revision:  Even worse, it is known that the "second best" mechanism-the mechanism that maximizes social welfare subject to the other constraints-has to be carefully tailored to the Bayesian priors and is extremely complex. In light of this impossibility result it is very natural to seek "simple" mechanisms that are approximately optimal, and indeed a very active line of recent work has established a broad spectrum of constant-factor approximation guarantees, which apply to settings well beyond those for which (implicit) characterizations of the optimal (second best) mechanism are known. In this work, we go one step further and show that for many fundamental two-sided markets-e.g., bilateral trade, double auctions, and combinatorial double auctions-it is possible to design near-optimal mechanisms with provable, constant-factor approximation guarantees with just a{\em   single sample from the priors!
After revision:  Even worse, it is known that the "second best" mechanism-the mechanism that maximizes social welfare subject to the other constraints-has to be carefully tailored to 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 mechanisms with provable, constant-factor approximation guarantees with just a{\em single sample from the priors!