Abstract
In the study of bilateral trade, the goal is to design mechanisms that facilitate the exchange of goods between a buyer and a seller while satisfying fundamental economic properties: truthfulness, individual rationality, and budget balance. While these mechanisms are well-understood for single-item trades, the multi-unit setting—where a seller holds $k$ identical items—presents new complexities. This paper characterizes the set of mechanisms that are Dominant Strategy Incentive Compatible (DSIC), Strongly Budget Balanced (SBB), and ex-post Individually Rational (IR) for multi-unit trade. We show that for agents with monotone or submodular valuations, these properties restrict the mechanism to simple fixed-price schemes. Furthermore, we establish that these mechanisms can achieve social welfare guarantees that match the best-known bounds for the single-item setting: a 2-approximation for deterministic mechanisms and an $e/(e-1)$ approximation for randomized ones.
Introduction
Bilateral trade is a foundational problem in mechanism design involving a single buyer and a single seller. The challenge lies in creating a set of rules (a mechanism) that encourages both parties to report their true valuations (DSIC), ensures no party is worse off by participating (IR), and requires no external subsidies (SBB).
While the single-item case has been extensively studied, many real-world transactions involve multiple identical units, such as a wholesaler selling a batch of components. In these scenarios, agents often exhibit "diminishing returns," where the marginal value of an additional item decreases as they acquire more. This paper extends the theoretical framework of bilateral trade to these multi-unit settings, exploring how the structure of valuations—specifically submodularity—affects the feasibility and efficiency of trade.
The Multi-Unit Setting
We consider a setting with one seller holding $k$ identical units and one buyer. The mechanism must decide the number of units to transfer and the payment from the buyer to the seller. The agents' preferences are modeled through valuation functions:
- Monotone Valuations: The value is non-decreasing in the number of units.
- Submodular Valuations: The marginal value of an item decreases as the total number of items increases (diminishing returns).
The goal is to maximize Social Welfare, defined as the sum of the buyer's value for the items they receive and the seller's value for the items they retain.
Characterizing Truthful Mechanisms
The paper’s primary theoretical contribution is a characterization theorem for mechanisms satisfying DSIC, SBB, and IR. The authors prove that any such mechanism must essentially function as a sequential posted price mechanism.
In this setup, the mechanism determines a fixed per-unit price $p$ before the trade occurs. The trade then proceeds iteratively: the buyer and seller are asked if they wish to trade one unit at price $p$. If both agree, the unit is transferred, and the process repeats. If either party declines, the process terminates.
Interestingly, the complexity of the valuation function dictates the flexibility of the mechanism:
- For Submodular Valuations: The mechanism can be iterative, allowing for multiple units to be traded one by one until the marginal value for either party no longer justifies the price.
- For General Monotone Valuations: The mechanism is more restricted, often limited to offering a single "take-it-or-leave-it" bundle of items at a fixed total price.
This finding highlights a "power of simplicity": if one insists on the gold standard of economic properties (DSIC, SBB, and IR), complex bidding systems are not only unnecessary but theoretically impossible.
Welfare Approximation Results
Since the mechanism designer does not know the agents' private valuations, they must set prices based on the probability distributions of those values. The paper provides bounds on how much social welfare can be captured compared to an omniscient "first-best" allocation:
- Deterministic Mechanisms: By setting a price where the seller is expected to trade half of their units, the authors prove a 2-approximation guarantee. This ensures that at least 50% of the maximum possible social welfare is realized.
- Randomized Mechanisms: By drawing a price from a specific probability distribution (extending the "Random Quantile" method), the mechanism achieves an $e/(e-1)$ approximation, capturing approximately 63% of the optimal welfare.
Crucially, these results match the best-known bounds for single-item bilateral trade. This suggests that the transition from one item to many identical units does not inherently degrade the efficiency of truthful, budget-balanced trade.
Conclusion and Future Directions
This work provides a complete picture of what is possible in multi-unit bilateral trade under strict fairness and truthfulness constraints. It demonstrates that simple, fixed-price sequential mechanisms are robust and efficient.
However, several avenues for future research remain. The current model assumes items are identical; extending these results to combinatorial settings—where a buyer might value different types of items differently—remains an open problem. Additionally, while this paper focuses on the bilateral (1-on-1) case, extending these tight characterizations to double auctions with multiple buyers and sellers is a significant next step for the field.
Summary updated