3 years ago

Fixed Price Approximability of the Optimal Gain From Trade.

Bart de Keijzer, Stefano Leonardi, Stefano Turchetta, Paul Goldberg, Riccardo Colini-Baldeschi

Bilateral trade is a fundamental economic scenario comprising a strategically acting buyer and seller, each holding valuations for the item, drawn from publicly known distributions. A mechanism is supposed to facilitate trade between these agents, if such trade is beneficial. It was recently shown that the only mechanisms that are simultaneously DSIC, SBB, and ex-post IR, are fixed price mechanisms, i.e., mechanisms that are parametrised by a price p, and trade occurs if and only if the valuation of the buyer is at least p and the valuation of the seller is at most p. The gain from trade is the increase in welfare that results from applying a mechanism; here we study the gain from trade achievable by fixed price mechanisms. We explore this question for both the bilateral trade setting, and a double auction setting where there are multiple buyers and sellers. We first identify a fixed price mechanism that achieves a gain from trade of at least 2/r times the optimum, where r is the probability that the seller's valuation does not exceed the buyer's valuation. This extends a previous result by McAfee. Subsequently, we improve this approximation factor in an asymptotic sense, by showing that a more sophisticated rule for setting the fixed price results in an expected gain from trade within a factor O(log(1/r)) of the optimal gain from trade. This is asymptotically the best approximation factor possible. Lastly, we extend our study of fixed price mechanisms to the double auction setting defined by a set of multiple i.i.d. unit demand buyers, and i.i.d. unit supply sellers. We present a fixed price mechanism that achieves a gain from trade that achieves for all epsilon > 0 a gain from trade of at least (1-epsilon) times the expected optimal gain from trade with probability 1 - 2/e^{#T epsilon^2 /2}, where #T is the expected number of trades resulting from the double auction.

Publisher URL: http://arxiv.org/abs/1710.08394

DOI: arXiv:1710.08394v1

You might also like
Discover & Discuss Important Research

Keeping up-to-date with research can feel impossible, with papers being published faster than you'll ever be able to read them. That's where Researcher comes in: we're simplifying discovery and making important discussions happen. With over 19,000 sources, including peer-reviewed journals, preprints, blogs, universities, podcasts and Live events across 10 research areas, you'll never miss what's important to you. It's like social media, but better. Oh, and we should mention - it's free.

  • Download from Google Play
  • Download from App Store
  • Download from AppInChina

Researcher displays publicly available abstracts and doesn’t host any full article content. If the content is open access, we will direct clicks from the abstracts to the publisher website and display the PDF copy on our platform. Clicks to view the full text will be directed to the publisher website, where only users with subscriptions or access through their institution are able to view the full article.