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 [2] 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 [1] to two-sided markets. We study the problem of maximizing the Gains from Trade (GFT) in two-sided markets. Unlike one-sided markets, such as auctions, the items are owned by a group of selfish agents known as sellers who form one side of the market, and the other side of the market -the buyers wish to purchase the items from the sellers. Sellers and buyers both have values for the items. Both sides are assumed to act strategically to maximize their utilities. Usually, the two-sided market is studied in the Bayesian model, where we assume that both the buyers' and sellers' values are drawn from some known distributions. The goal is to design a mechanism to facilitate trade between the two groups and optimize the expected GFT, which is the difference between the social welfare achieved by the mechanism and the sum of the sellers' values. The simplest two-sided market is usually referred to as the bilateral trading, in which there is a single seller who owns an item and a single buyer who wants to purchase the item. Both the buyer and the seller have quasi-linear utility functions, and the buyer's value for the item b and the seller's value s are drawn independently from two known distributions D B and D S .
Brustle et al. expanded in this direction in REF for arbitrary valuations and downwards closed feasibility constraints over the allocations.
Approximating Gains from Trade in Two-sided Markets via Simple Mechanisms
EC '17
Mathematics Computer Science