  We study gains from trade in multi-dimensional two-sided markets.
Specifically, we focus on a setting with $n$ heterogeneous items, where each
item is owned by a different seller $i$, and there is a constrained-additive
buyer with feasibility constraint $\mathcal{F}$. Multi-dimensional settings in
one-sided markets, e.g. where a seller owns multiple heterogeneous items but
also is the mechanism designer, are well-understood. In addition,
single-dimensional settings in two-sided markets, e.g. where a buyer and seller
each seek or own a single item, are also well-understood. Multi-dimensional
two-sided markets, however, encapsulate the major challenges of both lines of
work: optimizing the sale of heterogeneous items, ensuring
incentive-compatibility among both sides of the market, and enforcing budget
balance. We present, to the best of our knowledge, 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.

Computer Science and Game Theory