On Multi-Dimensional Gains from Trade Maximization

We study gains from trade maximization in a two-sided market with n heterogeneous items, where each item is owned by a different seller i, and there is a constrained-additive buyer with feasibility constraint F. We present the first worst-case approximation guarantee for gains from trade in a multi-dimensional two-sided market.

Our first result provides an O(log(1/r))-approximation to the first-best gains from trade for a broad class of downward-closed feasibility constraints (such as matroid, matching, knapsack, or the intersection of these). Here r is the minimum probability over all items that a buyer's value for the item exceeds the seller's cost. Our second result removes the dependence on r and provides an unconditional O(log n)-approximation to the second-best gains from trade. We extend both results for a general constrained-additive buyer, losing another O(log n)-factor en-route.

Joint work with Yang Cai, Steven Ma, and Mingfei Zhao.