Interdependent Bilateral Trade: Information vs Approximation

Shahar Dobzinski, Alon Eden, Kira Goldner, Ariel Shaulker, Thodoris TsilivisarXiv 2025 · DOI · arXiv

Abstract

This paper investigates welfare maximization in bilateral trade settings characterized by interdependent values, where a player's valuation of an item depends on the private information held by others. We introduce a novel framework to classify information structures and demonstrate that while certain boundary conditions allow for efficient welfare approximations, even minor deviations into the interior of the information space can render constant-factor approximations impossible.

Introduction

In classic bilateral trade, a seller possesses an item that a buyer wishes to purchase. The objective is to design a mechanism that maximizes social welfare—ensuring the item is allocated to the party with the highest valuation—without requiring an outside subsidy and ensuring players have no incentive to misrepresent their information. While traditional models assume private values, real-world scenarios often involve interdependent values. For instance, in a used car market, the seller's knowledge of the vehicle's history directly impacts the buyer's valuation. This interdependence introduces the "Winner's Curse" or "Lemons Problem," where strategic inference complicates the design of efficient mechanisms.

Mapping Information Structures

To analyze these complexities, we propose a framework that maps information structures onto a unit square defined by two parameters: $\alpha$ (the seller's informedness) and $\beta$ (the buyer's informedness). These parameters quantify the relative influence of a player's own signal versus their opponent's signal on their valuation.

The unit square $(\alpha, \beta)$ representing the space of information structures in bilateral trade.

As illustrated in the figure above, the corners of this square represent extreme cases:

  • (0,0): Both players are uninformed.
  • (1,0): The seller is fully informed, while the buyer is uninformed.
  • (0,1): The seller is uninformed, while the buyer is fully informed.
  • (1,1): The standard private-values setting.

Key Theoretical Results

Our analysis reveals a stark "threshold phenomenon." While positive results are achievable on the edges of the information square, the interior is largely a "red zone" where efficiency breaks down. We utilize mechanism reduction and lower bound constructions to prove that the possibility of a good trade is highly sensitive to these information levels.

Performance on the Edges

  • The (1, $\beta$) Edge: When the seller is fully informed, we provide a mechanism achieving an $O(1/\beta)$ approximation ratio. Under the "single-crossing" condition—a standard economic assumption—this improves to a constant-factor approximation regardless of the buyer's information level.
  • The (0, $\beta$) Edge: If the seller is entirely uninformed, we achieve an $O(1/(1-\beta))$ approximation. Interestingly, in this regime, the approximation ratio improves as the buyer becomes less informed, suggesting that ignorance can sometimes prevent the strategic signal leakage that disrupts markets.

Polynomial Valuations

For valuations defined by polynomials of degree $k$, we design a mechanism providing an $O(k^2)$ approximation. We also establish a lower bound of $\Omega(k)$, showing that the complexity of the valuation function inherently limits welfare guarantees.

Impossibility in the Interior

The most significant finding is that for almost any point in the interior of the square—where both players possess partial information—no mechanism can guarantee a constant-factor approximation to the optimal welfare. This suggests that the seller's information state is a critical linchpin; unless the seller is at an extreme (fully informed or totally uninformed), they can strategically manipulate the trade to the detriment of social welfare.

Conclusion and Future Work

This work highlights the extreme sensitivity of bilateral trade to information structures. While we have identified mechanisms for boundary cases, the general impossibility of constant-factor approximations in the interior presents a significant challenge. Future research should focus on identifying specific "natural" families of information structures that might allow for better results in the interior or shifting the benchmark from social welfare to "gains from trade," which represents the net value created by the transaction itself.

Summary updated

Abstract

Welfare maximization in bilateral trade has been extensively studied in recent years. Previous literature obtained incentive-compatible approximation mechanisms only for the private values case. In this paper, we study welfare maximization in bilateral trade with interdependent values. Designing mechanisms for interdependent settings is much more challenging because the values of the players depend on the private information of the others, requiring complex belief updates and strategic inference. We propose to classify information structures by quantifying the influence that a player's private signal has on their own valuation. We then paint a picture of where approximations are possible and impossible based on these information structures. Finally, we also study the possible approximation ratios for a natural family of information structures.
BibTeX
@misc{dobzinski2025interdependent,
  author = {Shahar Dobzinski and Alon Eden and Kira Goldner and Ariel Shaulker and Thodoris Tsilivis},
  title = {{Interdependent Bilateral Trade: Information vs Approximation}},
  year = {2025},
  eprint = {2506.23896},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2506.23896},
}
Figure