Multi-Unit Bilateral Trade

Matthias Gerstgrasser, Paul W. Goldberg, Bart de Keijzer, Philip Lazos, Alexander Skopalik

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:

  1. Monotone Valuations: The value is non-decreasing in the number of units.
  2. 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

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/(1 − e) approximation mechanism, matching the best known bounds for the single-item setting.
BibTeX
@inproceedings{gerstgrasser2019multi,
  author = {Matthias Gerstgrasser and Paul W. Goldberg and Bart de Keijzer and Philip Lazos and Alexander Skopalik},
  title = {{Multi-Unit Bilateral Trade}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  url = {https://openreview.net/forum?id=eSRTRn1oP8},
}
Figure