  Mechanism design for one-sided markets has been investigated for several
decades in economics and in computer science. More recently, there has been an
increased attention on mechanisms for two-sided markets, in which buyers and
sellers act strategically. For two-sided markets, an impossibility result of
Myerson and Satterthwaite states that no mechanism can simultaneously satisfy
individual rationality (IR), incentive compatibility (IC), strong
budget-balance (SBB), and be efficient. On the other hand, important
applications to web advertisement, stock exchange, and frequency spectrum
allocation, require us to consider two-sided combinatorial auctions in which
buyers have preferences on subsets of items, and sellers may offer multiple
heterogeneous items. No efficient mechanism was known so far for such two-sided
combinatorial markets. This work provides the first IR, IC and SBB mechanisms
that provides an O(1)-approximation to the optimal social welfare for two-sided
markets. An initial construction yields such a mechanism, but exposes a
conceptual problem in the traditional SBB notion. This leads us to define the
stronger notion of direct trade strong budget balance (DSBB). We then proceed
to design mechanisms that are IR, IC, DSBB, and again provide an
O(1)-approximation to the optimal social welfare. Our mechanisms work for any
number of buyers with XOS valuations - a class in between submodular and
subadditive functions - and any number of sellers. We provide a mechanism that
is dominant strategy incentive compatible (DSIC) if the sellers each have one
item for sale, and one that is bayesian incentive compatible (BIC) if sellers
hold multiple items and have additive valuations over them. Finally, we present
a DSIC mechanism for the case that the valuation functions of all buyers and
sellers are additive.
