Search for: All records

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 a feasibility constraint. 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. 

We consider the black-box reduction from multi-dimensional revenue maximization to virtual welfare maximization. Cai et al. [12, 13, 14, 15] show a polynomial-time approximation-preserving re-duction, however, the mechanism produced by their reduction is only approximately Bayesian incentive compatible (ε-BIC). We provide two new polynomial time transformations that convert anyε-BICmechanism to an exactly BIC mechanism with only a negligible revenue loss. (i) Our first transformation applies to any mechanism design setting with downward-closed outcome space and only requires sample accessto the agents’ type distributions. (ii) Our second transformation applies to the fully general outcome space, removing the downward-closed assumption, but requires full access to the agents’ type distributions. Both transformations only require query access to the originalε-BIC mechanism. Otherε-BIC to BICtransformations for revenue exist in the literature but all require exponential time to run in either of the settings we consider. As an application of our transformations, we improve the reduction by Cai et al. to generate an exactly BIC mechanism.