eduzhai > Applied Sciences > Computer Science >

Bulow-Klemperer-Style Results for Welfare Maximization in Two-Sided Markets

  • KanKan
  • (0) Download
  • 20210425
  • Save

... pages left unread,continue reading

Document pages: 51 pages

Abstract: We consider the problem of welfare maximization in two-sided markets usingsimple mechanisms that are prior-independent. The Myerson-Satterthwaiteimpossibility theorem shows that even for bilateral trade, there is no feasible(IR, truthful, budget balanced) mechanism that has welfare as high as theoptimal-yet-infeasible VCG mechanism, which attains maximal welfare but runs adeficit. On the other hand, the optimal feasible mechanism needs to becarefully tailored to the Bayesian prior, and is extremely complex, eluding aprecise description.We present Bulow-Klemperer-style results to circumvent these hurdles indouble-auction markets. We suggest using the Buyer Trade Reduction (BTR)mechanism, a variant of McAfee s mechanism, which is feasible and simple (inparticular, deterministic, truthful, prior-independent, anonymous). First, inthe setting where buyers and sellers values are sampled i.i.d. from the samedistribution, we show that for any such market of any size, BTR with oneadditional buyer whose value is sampled from the same distribution has expectedwelfare at least as high as the optimal in the original market.We then move to a more general setting where buyers values are sampled fromone distribution and sellers from another, focusing on the case where thebuyers distribution first-order stochastically dominates the sellers . Wepresent bounds on the number of buyers that, when added, guarantees that BTR inthe augmented market have welfare at least as high as the optimal in theoriginal market. Our lower bounds extend to a large class of mechanisms, andall of our results extend to adding sellers instead of buyers. In addition, wepresent positive results about the usefulness of pricing at a sample forwelfare maximization in two-sided markets under the above two settings, whichto the best of our knowledge are the first sampling results in this context.

Please select stars to rate!


0 comments Sign in to leave a comment.

    Data loading, please wait...