Maximizing Gains From Trade in Two-Sided Markets

In a two-sided market, we maximize the gains from trade: the sum over, for each buyer-seller pair that trades, the buyer's value minus the seller's cost. Unfortunately, it is impossible to achieve the optimal gains from trade with a mechanism that satisfies the natural budget, truthfulness, and individual rationality constraints [Myerson Satterthwaite '83], so our goal is instead approximation. Further, approximating the gains from trade objective is more difficult than both approximating welfare in a two-sided market and approximating revenue in a one-sided market.

In one approach, we use a simple mechanism on an augmented market in which we've recruited additional buyers to fully beat the optimal gains from trade in the original market. In a second approach, we use simple mechanisms to obtain the first approximation in a multidimensional setting. All of the mechanisms used are in fact quite simple. We prove their guarantees with ideas from probability and optimization.

Joint work with (1) Moshe Babaioff and Yannai Gonczarowski and (2) Yang Cai, Steven Ma, and Mingfei Zhao.