Abstract
We study how to maximize the broker’s (expected)
profit in a two-sided market, where she buys items
from a set of sellers and resells them to a set of
buyers. Each seller has a single item to sell and
holds a private value on her item, and each buyer
has a valuation function over the bundles of the
sellers’ items. We consider the Bayesian setting
where the agents’ values/valuations are independently drawn from prior distributions, and aim at
designing dominant-strategy incentive-compatible
(DSIC) mechanisms that are approximately optimal.
Production-cost markets, where each item has a
publicly-known cost to be produced, provide a platform for us to study two-sided markets. Briefly, we
show how to covert a mechanism for productioncost markets into a mechanism for the broker,
whenever the former satisfies cost-monotonicity.
This reduction holds even when buyers have general combinatorial valuation functions. When the
buyers’ valuations are additive, we generalize an
existing mechanism to production-cost markets in
an approximation-preserving way. We then show
that the resulting mechanism is cost-monotone and
thus can be converted into an 8-approximation
mechanism for two-sided markets