2017/06/14 by Johannes Brustle, Yang Cai, Brustle, Johannes +5 · 4 citations
Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Computer Science and Game Theory (cs.GT) #Economic Policies and Impacts #Economic theories and models #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1706.04637
openalex publication_date 2017/06/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Individually Rational (IR), Bayesian Incentive Compatible (BIC) and Budget-Balanced (BB) mechanism can achieve full GFT (trade whenever buyer's value is higher than the seller's cost). On the other hand, they proposed the "second-best" mechanism that maximizes the GFT subject to IR, BIC and BB constraints, which is unfortunately rather complex for even the single-seller single-buyer case. Our mechanism is simple, IR, BIC and BB, and achieves (1)/(2) of the optimal GFT among all IR, BIC and BB mechanisms. Our 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.