Fixed Price Approximability of the Optimal Gain From Trade

22^nd November 2017, 13:00
Bart De Keijzer
University of Liverpool

Abstract

In the classical bilateral trade scenario, a buyer and a seller are present, both with quasi-linear utility functions, and randomly and independently drawn valuations. The seller holds an item, and a mechanism determines whether trade happens, and at which price. For this fundamental setting, it is known that the only mechanisms that are simultaneously dominant strategy incentive compatible, strongly budget balanced, and ex-post individually rational are fixed price mechanisms. Such mechanisms are parameterized 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* of a mechanism is defined as the expected amount by which the mechanism increases total utility. McAfee has shown that if the median of the distribution of the seller's valuation is less than the median of the distribution of the buyer's valuation, then there is a fixed price mechanism for which the gain from trade is at least half of the optimal gain from trade.
- I will first discuss an extension this result by identifying a fixed-price mechanism that achieves a gain from trade of at least r/2 times the optimum, where r is the probability that the seller's valuation does not exceed the buyer's valuation.
- Next, I will show how to 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.
- Finally, I will discuss a more general two sided market setting with multiple buyers and sellers with independently drawn valuations, and present a sequential posted price mechanism that offers all agents a unique fixed price, and guarantees a constant approximation to the optimal gain from trade in case at least a constant expected number of trades occur (or equivalently: when the number of agents exceeds a certain threshold).

Joint work with Riccardo Colini-Baldeschi, Paul Goldberg, Stefano Leonardi, and Stefano Turchetta

To appear in WINE 2017.