BulowKlempererStyle Results for Welfare Maximization in TwoSided Markets We consider the problem of welfare maximization in twosided markets using simple mechanisms that are priorindependent. The seminal impossibility result of Myerson and Satterthwaite 1983 shows that even for bilateral trade, there is no feasible (IR, truthful and budget balanced) mechanism that has welfare as high as the optimalyetinfeasible VCG mechanism, which attains maximal welfare but runs a deficit. On the other hand, the optimal feasible mechanism needs to be carefully tailored to the Bayesian prior, and is extremely complex, eluding a precise description. In this paper we present BulowKlempererstyle results to circumvent these hurdles in doubleauction market settings. We suggest using the Buyer Trade Reduction (BTR) mechanism, a variant of McAfeeu0027s mechanism, that is feasible and simple (in particular, it is deterministic, priorindependent, and anonymous). First, in the setting where the buyersu0027 and sellersu0027 values are sampled i.i.d. from the same distribution, we show that for any such market of any size, BTR with one additional buyer whose value is sampled from the same distribution has expected welfare at least as high as the optimal in the original market. We then move to a more general setting where the buyersu0027 values are sampled from one distribution, and the sellersu0027 from another, focusing on the case where the buyersu0027 distribution firstorder stochastically dominates the sellersu0027 distribution. We present bounds on the number of buyers that, when added, cause BTR in the augmented market to achieve welfare at least as high as the optimal in the original market. Our lower bounds extend to a large class of mechanisms. In addition, we present positive results about the usefulness of pricing at a sample for welfare maximization in twosided markets under the above two settings, which to the best of our knowledge are the first sampling results in this context.

Revenue maximization in a Bayesian double auction market Abstract   We study double auction market design where the market maker wants to maximize its total revenue by buying low from the sellers and selling high to the buyers. We consider a Bayesian setting where buyers and sellers have independent probability distributions on the values of products on the market.  For the simplest setting, each seller has one kind of indivisible good with a bounded (integer) amount that can be sold to a buyer, who may demand a bounded number of copies. We develop a maximum mechanism for the market maker to maximize its own revenue.  For the more general case where each selleru0027s product may be different, we consider a number of variants in terms of constraints on supplies and demands. For each of them, we develop a polynomial time computable truthful mechanism for the market maker to achieve a revenue at least a constant  xcexb1  times the revenue of any other truthful mechanism.