Abstract
We characterise the set of dominant strategy incentive compatible (DSIC), strongly budget balanced (SBB), and ex-post individually rational (IR) mechanisms for the multi-unit bilateral trade setting. In such a setting there is a single buyer and a single seller who holds a finite number $k$ of identical items. The mechanism has to decide how many units of the item are transferred from the seller to the buyer and how much money is transferred from the buyer to the seller. We consider two classes of valuation functions for the buyer and seller: Valuations that are increasing in the number of units in possession, and the more specific class of valuations that are increasing and submodular. Furthermore, we present some approximation results about the performance of certain such mechanisms, in terms of social welfare: For increasing submodular valuation functions, we show the existence of a deterministic 2-approximation mechanism and a randomised $e/(e-1)$ approximation mechanism, matching the best known bounds for the single-item setting.
Introduction
In traditional auction theory, the seller is often viewed as a passive auctioneer whose primary goal is to design a mechanism that extracts maximum value from strategic buyers. However, many real-world markets are "two-sided," where both the buyer and the seller act strategically based on private information. This is the core of bilateral trade.
While the single-item bilateral trade problem is a cornerstone of mechanism design, many practical scenarios—such as a wholesaler selling a batch of components to a manufacturer—involve multiple identical units. This paper extends the bilateral trade framework to a multi-unit setting, investigating the structural constraints and performance limits of mechanisms that must satisfy three fundamental properties:
- Dominant Strategy Incentive Compatibility (DSIC): Agents maximize their utility by reporting their true valuations, regardless of the other agent's actions.
- Strong Budget Balance (SBB): The mechanism neither requires external subsidies nor generates a surplus; all money transferred by the buyer is received by the seller.
- Individual Rationality (IR): Participation is voluntary; no agent is worse off after the trade than they were before.
Theoretical Framework and Characterization
The fundamental challenge in bilateral trade is the impossibility of achieving perfect efficiency. The Myerson-Satterthwaite theorem establishes that no mechanism can be simultaneously DSIC, SBB, IR, and fully efficient (maximizing social welfare in every instance). Consequently, research focuses on characterizing the set of feasible mechanisms and finding those that approximate the optimal social welfare.
The Fixed Price Constraint
A central finding of this research is the "tyranny of fixed prices." The authors prove that any mechanism satisfying DSIC, SBB, and IR in a multi-unit setting must rely on fixed per-unit prices. The mechanism cannot dynamically adjust prices based on the agents' reported valuations; instead, prices must be set a priori or based solely on the underlying probability distributions of the agents' values.
Valuation Classes
The paper distinguishes between two types of agent preferences:
- Monotonically Increasing Valuations: The agent's total value increases with the number of items, but no other assumptions are made about the rate of increase.
- Submodular Valuations: The agent experiences diminishing marginal returns (e.g., the first unit is worth more than the second).
The authors show that submodularity is the key to granularity. If valuations are submodular, the mechanism can offer items sequentially at a fixed price. If valuations are merely increasing, the mechanism is restricted to offering a single "take-it-or-leave-it" bundle of items to maintain truthfulness and budget balance.
Approximation Results
Given the impossibility of perfect efficiency, the authors evaluate mechanisms based on their approximation ratio—the ratio of the maximum possible social welfare to the expected social welfare produced by the mechanism. They utilize a Bayesian framework, assuming valuations are drawn from known distributions.
Deterministic Mechanisms
The authors propose a deterministic mechanism that sets a price $p$ such that the seller is expected to part with half of their units. This approach yields a 2-approximation, meaning the mechanism is guaranteed to capture at least 50% of the optimal social welfare. This result is significant because it demonstrates that the complexity of handling $k$ items does not degrade the performance compared to the single-item case.
Randomized Mechanisms
By introducing randomness, the approximation can be further improved. The authors employ a "Generalized Random Quantile Mechanism," which selects a price from a specific probability distribution. This achieves an approximation ratio of $e/(e-1) \approx 1.58$. This matches the best-known theoretical bounds for single-item bilateral trade, proving that multi-unit settings are no less tractable than their single-unit counterparts.
Conclusion and Future Directions
This work provides a complete characterization of feasible mechanisms for multi-unit bilateral trade, establishing that fixed-price mechanisms are the only viable path forward under standard constraints. By matching the approximation bounds of the single-item setting, the authors demonstrate the robustness of these mechanisms across scales.
Future research remains open in several areas. First, while the upper bounds match the single-item case, there are currently no non-trivial lower bounds for the multi-unit setting, leaving the possibility of even more efficient mechanisms. Second, for general monotone valuations that lack submodularity, the current best approximation is approximately 2.58, suggesting a gap that future algorithms might close. Finally, extending these results to "double auctions" involving multiple buyers and sellers remains a major frontier in algorithmic game theory.
Summary updated