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.
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