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
This content will become publicly available on June 11, 2025
Bilateral Trade with Correlated Values
We study the bilateral trade problem where a seller owns a single indivisible item, and a potential buyer seeks to purchase it. Previous mechanisms for this problem only considered the case where the values of the buyer and the seller are drawn from independent distributions. In contrast, this paper studies bilateral trade mechanisms when the values are drawn from a joint distribution. We prove that the buyeroffering mechanism guarantees an approximation ratio of e/e−1 ≈ 1.582 to the social welfare even if the values are drawn from a joint distribution. The buyeroffering mechanism is Bayesian incentive compatible, but the seller has a dominant strategy. We prove the buyeroffering mechanism is optimal in the sense that no Bayesian mechanism where one of the players has a dominant strategy can obtain an approximation ratio better than e/e−1. We also show that no mechanism in which both sides have a dominant strategy can provide any constant approximation to the social welfare when the values are drawn from a joint distribution. Finally, we prove some impossibility results on the power of general Bayesian incentive compatible mechanisms. In particular, we show that no deterministic Bayesian incentivecompatible mechanism can provide an approximation ratio better than 1+ln2/2≈ 1.346.
more »
« less
 Award ID(s):
 2127781
 NSFPAR ID:
 10525740
 Editor(s):
 Mohar, Bojan; Shinkar, Igor; O'Donnell, Ryan
 Publisher / Repository:
 ACM
 Date Published:
 Subject(s) / Keyword(s):
 bilateral trade, incentive compatibility
 Format(s):
 Medium: X
 Location:
 Vancouver BC Canada
 Sponsoring Org:
 National Science Foundation
More Like this


Naor, Joseph ; Buchbinder, Niv (Ed.)We consider the bilateral trade problem, in which two agents trade a single indivisible item. It is known that the only dominantstrategy truthful mechanism is the fixedprice mechanism: given commonly known distributions of the buyer's value B and the seller's value S, a price p is offered to both agents and trade occurs if S ≤ p ≤ B. The objective is to maximize either expected welfare or expected gains from trade . We improve the approximation ratios for several welfare maximization variants of this problem. When the agents' distributions are identical, we show that the optimal approximation ratio for welfare is . With just one prior sample from the common distribution, we show that a 3/4approximation to welfare is achievable. When agents' distributions are not required to be identical, we show that a previously bestknown (1–1/e)approximation can be strictly improved, but 1–1/e is optimal if only the seller's distribution is known.more » « less

We consider the problem of a single seller repeatedly selling a single item to a single buyer (specifically, the buyer has a value drawn fresh from known distribution $D$ in every round). Prior work assumes that the buyer is fully rational and will perfectly reason about how their bids today affect the seller's decisions tomorrow. In this work we initiate a different direction: the buyer simply runs a noregret learning algorithm over possible bids. We provide a fairly complete characterization of optimal auctions for the seller in this domain. Specifically: 1) If the buyer bids according to EXP3 (or any ``meanbased'' learning algorithm), then the seller can extract expected revenue arbitrarily close to the expected welfare. This auction is independent of the buyer's valuation $D$, but somewhat unnatural as it is sometimes in the buyer's interest to overbid. 2) There exists a learning algorithm $\mathcal{A}$ such that if the buyer bids according to $\mathcal{A}$ then the optimal strategy for the seller is simply to post the Myerson reserve for $D$ every round. 3) If the buyer bids according to EXP3 (or any ``meanbased'' learning algorithm), but the seller is restricted to ``natural'' auction formats where overbidding is dominated (e.g. Generalized FirstPrice or Generalized SecondPrice), then the optimal strategy for the seller is a payyourbid format with decreasing reserves over time. Moreover, the seller's optimal achievable revenue is characterized by a linear program, and can be unboundedly better than the best truthful auction yet simultaneously unboundedly worse than the expected welfare.more » « less

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

Stefano Leonardi (Ed.)We study the communication complexity of dominant strategy implementations of combinatorial auctions. We start with two domains that are generally considered “easy”: multiunit auctions with decreasing marginal values and combinatorial auctions with gross substitutes valuations. For both domains we have fast algorithms that find the welfaremaximizing allocation with communication complexity that is polylogarithmic in the input size. This immediately implies that welfare maximization can be achieved in expost equilibrium with no significant communication cost, by using VCG payments. In contrast, we show that in both domains the communication complexity of any dominant strategy implementation that achieves the optimal welfare is polynomial in the input size. We then move on to studying the approximation ratios achievable by dominant strategy mechanisms. For multiunit auctions with decreasing marginal values, we provide a dominantstrategy communication FPTAS. For combinatorial auctions with general valuations, we show that there is no dominant strategy mechanism that achieves an approximation ratio better than m1−є that uses poly(m,n) bits of communication, where m is the number of items and n is the number of bidders. In contrast, a randomized dominant strategy mechanism that achieves an O(√m) approximation with poly(m,n) communication is known. This proves the first gap between computationally efficient deterministic dominant strategy mechanisms and randomized ones. En route, we answer an open question on the communication cost of implementing dominant strategy mechanisms for more than two players, and also solve some open problems in the area of simultaneous combinatorial auctions.more » « less