Paper Info
Title
Approximating Gains from Trade in Two-sided Markets via Simple Mechanisms.
Abstract
We design simple mechanisms to approximate the Gains from Trade (GFT) in two-sided markets with multiple unit-supply sellers and multiple unit-demand buyers. A classical impossibility result by Myerson and Satterthwaite showed that even with only one seller and one buyer, no Bayesian Incentive Compatible (BIC), Individually Rational (IR), and Budget-Balanced (BB) mechanism can achieve full GFT (trade whenever buyer's value is higher than the seller's cost). The same paper also proposed the ``second-best'' mechanism that maximizes the GFT subject to BIC, IR, and BB constraints, which is unfortunately rather complex for even the single-seller single-buyer case. Our mechanism is simple, BIC, IR, and BB and achieves 1/2 of the optimal GFT among all BIC, IR, and BB mechanisms. The result holds for arbitrary distributions of the buyers' and sellers' values and can accommodate any downward-closed feasibility constraints over the allocations. The analysis of our mechanism is facilitated by extending the Cai-Weinberg-Devanur duality framework to two-sided markets.
Year
DOI
Venue
2017
10.1145/3033274.3085148
EC
Keywords
DocType
Volume
Bilateral Trading, Double Auction, Two-sided Market, Simple Mechanism, Gains from Trade, Duality
Conference
abs/1706.04637
Citations 
PageRank 
References 
6
0.59
0
Authors
4
Name
Order
Citations
PageRank
Johannes Brustle160.59
Yang Cai233025.53
Fa Wu3424.21
Mingfei Zhao4132.49