We study gains from trade in multidimensional twosided 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 constrainedadditive buyer with a feasibility constraint. Multidimensional settings in onesided markets, e.g. where a seller owns multiple heterogeneous items but also is the mechanism designer, are wellunderstood. In addition, singledimensional settings in twosided markets, e.g. where a buyer and seller each seek or own a single item, are also wellunderstood. Multidimensional twosided markets, however, encapsulate the major challenges of both lines of work: optimizing the sale of heterogeneous items, ensuring incentivecompatibility among both sides of the market, and enforcing budget balance. We present, to the best of our knowledge, the first worstcase approximation guarantee for gains from trade in a multidimensional twosided market.
Our first result provides an O(log(1/r))approximation to the firstbest gains from trade for a broad class of downwardclosed 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 secondbest gains from trade. We extend both results for a general constrainedadditive buyer, losing another O(log n)factor enroute.
more »
« less
On MultiDimensional Gains from Trade Maximization
We study gains from trade in multidimensional twosided 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 constrainedadditive buyer with feasibility constraint ℱ. Multidimensional settings in onesided markets, e.g. where a seller owns multiple heterogeneous items but also is the mechanism designer, are wellunderstood. In addition, singledimensional settings in twosided markets, e.g. where a buyer and seller each seek or own a single item, are also wellunderstood. Multidimensional twosided markets, however, encapsulate the major challenges of both lines of work: optimizing the sale of heterogeneous items, ensuring incentivecompatibility among both sides of the market, and enforcing budget balance. We present, to the best of our knowledge, the first worstcase approximation guarantee for gains from trade in a multidimensional twosided market.
Our first result provides an O(log(1/r))approximation to the firstbest gains from trade for a broad class of downwardclosed 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 secondbest gains from trade. We extend both results for a general constrainedadditive buyer, losing another O(log n)factor enroute. The first result is achieved using a fixed posted price mechanism, and the analysis involves a novel application of the prophet inequality or a new concentration inequality. Our second result follows from a stitching lemma that allows us to upper bound the secondbest gains from trade by the firstbest gains from trade from the “likely to trade” items (items with trade probability at least 1/n) and the optimal profit from selling the “unlikely to trade” items. We can obtain an O(log n)approximation to the first term by invoking our O(log(1/r))approximation on the “likely to trade” items. We introduce a generalization of the fixed posted price mechanism—seller adjusted posted price—to obtain an O(log n)approximation to the optimal profit for the “unlikely to trade” items. Unlike fixed posted price mechanisms, not all seller adjusted posted price mechanisms are incentive compatible and budget balanced. We develop a new argument based on “allocation coupling” to show the seller adjusted posted price mechanism used in our approximation is indeed budget balanced and incentivecompatible.
more »
« less
 Award ID(s):
 1903037
 NSFPAR ID:
 10471409
 Publisher / Repository:
 SIAM
 Date Published:
 Journal Name:
 Proceedings of the 2021 ACMSIAM Symposium on Discrete Algorithms (SODA)
 Page Range / eLocation ID:
 1079–1098
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Large fractions of online advertisements are sold via repeated secondprice auctions. In these auctions, the reserve price is the main tool for the auctioneer to boost revenues. In this work, we investigate the following question: how can the auctioneer optimize reserve prices by learning from the previous bids while accounting for the longterm incentives and strategic behavior of the bidders? To this end, we consider a seller who repeatedly sells ex ante identical items via a secondprice auction. Buyers’ valuations for each item are drawn independently and identically from a distribution F that is unknown to the seller. We find that if the seller attempts to dynamically update a common reserve price based on the bidding history, this creates an incentive for buyers to shade their bids, which can hurt revenue. When there is more than one buyer, incentive compatibility can be restored by using personalized reserve prices, where the personal reserve price for each buyer is set using the historical bids of other buyers. Such a mechanism asymptotically achieves the expected revenue obtained under the static Myerson optimal auction for F. Further, if valuation distributions differ across bidders, the loss relative to the Myerson benchmark is only quadratic in the size of such differences. We extend our results to a contextual setting where the valuations of the buyers depend on observed features of the items. When upfront fees are permitted, we show how the seller can determine such payments based on the bids of others to obtain an approximately incentivecompatible mechanism that extracts nearly all the surplus.more » « less

A core tension in the operations of online marketplaces is between segmentation (wherein platforms can increase revenue by segmenting the market into ever smaller submarkets) and thickness (wherein the size of the submarket affects the utility experienced by an agent). An important example of this is in dynamic online marketplaces, where buyers and sellers, in addition to preferences for different matches, also have finite patience (or deadlines) for being matched. We formalize this tradeoff via a novel optimization problem that we term as 'Twosided Facility Location': we consider a market wherein agents arrive at nodes embedded in an underlying metric space, where the distance between a buyer and seller captures the quality of the corresponding match. The platform posts prices and wages at the nodes, and opens a set of virtual clearinghouses where agents are routed for matching. To ensure high matchquality, the platform imposes a distance constraint between an agent and its clearinghouse; to ensure thickness, the platform requires the flow to any clearinghouse be at least a prespecified lower bound. Subject to these constraints, the goal of the platform is to maximize the social surplus subject to weak budget balance, i.e., profit being nonnegative. Our work characterizes the complexity of this problem by providing both hardness results as well as algorithms for this setting; in particular, we present an algorithm that for any constant ε > 0 yields a (1 + ε ) approximation for the gains from trade, while relaxing the match quality (i.e., maximum distance of any match) by a constant factor.more » « less

A single seller faces a sequence of buyers with unit demand. The buyers are forward‐looking and long‐lived. Each buyer has private information about his arrival time and valuation where the latter evolves according to a geometric Brownian motion. Any incentive‐compatible mechanism has to induce truth‐telling about the arrival time and the evolution of the valuation. We establish that the optimal stationary allocation policy can be implemented by a simple posted price. The truth‐telling constraint regarding the arrival time can be represented as an optimal stopping problem that determines the first time at which the buyer participates in the mechanism. The optimal mechanism thus induces progressive participation by each buyer: he either participates immediately or at a future random time.more » « less

We study the menu complexity of optimal and approximatelyoptimal auctions in the context of the ``FedEx'' problem, a socalled ``oneandahalfdimensional'' setting where a single bidder has both a value and a deadline for receiving an item [FGKK 16]. The menu complexity of an auction is equal to the number of distinct (allocation, price) pairs that a bidder might receive [HN 13]. We show the following when the bidder has $n$ possible deadlines: 1) Exponential menu complexity is necessary to be exactly optimal: There exist instances where the optimal mechanism has menu complexity $\geq 2^n1$. This matches exactly the upper bound provided by Fiat et al.'s algorithm, and resolves one of their open questions [FGKK 16]. 2) Fully polynomial menu complexity is necessary and sufficient for approximation: For all instances, there exists a mechanism guaranteeing a multiplicative $(1\epsilon)$approximation to the optimal revenue with menu complexity $O(n^{3/2}\sqrt{\frac{\min\{n/\epsilon,\ln(v_{\max})\}}{\epsilon}}) = O(n^2/\epsilon)$, where $v_{\max}$ denotes the largest value in the support of integral distributions. \item There exist instances where any mechanism guaranteeing a multiplicative $(1O(1/n^2))$approximation to the optimal revenue requires menu complexity $\Omega(n^2)$. Our main technique is the polygon approximation of concave functions [Rote 91], and our results here should be of independent interest. We further show how our techniques can be used to resolve an open question of [DW 17] on the menu complexity of optimal auctions for a budgetconstrained buyer.more » « less