Interdependent Bilateral Trade: Information vs Approximation
Shahar Dobzinski, Alon Eden, Kira Goldner, Ariel Shaulker, Thodoris Tsilivis · 2025
Read Interdependent Bilateral Trade: Information vs Approximation by Shahar Dobzinski, Alon Eden, Kira Goldner, Ariel Shaulker, Thodoris Tsilivis (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-23896.txt.
Introduction
Shahar Dobzinski and co-authors study trade between two parties whose values depend on each other in a paper from 2025. In classic bilateral trade, each side privately knows what the good is worth to them. Here, each side's value also shifts with the other's private signal, which tangles incentives.
Honest mechanisms that nearly maximize welfare were known only for the private case. The authors sort information structures by how strongly a signal sways its owner's own value. That measure draws a line between settings where good approximations exist and where they cannot. A natural family of structures gets exact approximation ratios. The map helps mechanism designers know when fairness and efficiency can coexist.
Catalog record
| CREATOR | Shahar Dobzinski, Alon Eden, Kira Goldner, Ariel Shaulker, Thodoris Tsilivis |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 92 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-23896
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Interdependent Bilateral Trade: Information vs Approximation Thanks: The work of S. Dobzinski and A. Shaulker was supported by the BSF-NSF grant (BSF number: 2021655, NSF number: 2127781). The work of A. Eden was supported by the Israel Science Foundation (grant No. 533/23). Alon Eden is the Incumbent of the Harry & \& Abe Sherman Senior Lectureship at the School of Computer Science and Engineering at the Hebrew University. The work of K. Goldner and T. Tsilivis was supported by NSF CAREER Award CCF-2441071. Shahar Dobzinski, Alon Eden, Kira Goldner, Ariel Shaulker, Thodoris Tsilivis 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. 1 Introduction We investigate welfare maximization in bilateral trade. Bilateral trade is the setting with one item, one buyer with value v_{b} , and one seller with value v_{s} . We aim to design mechanisms that satisfy budget-balance and incentive-compatibility (IC) constraints, and that (approximately) maximize expected social welfare. More specifically, in bilateral trade, the aim is to maximize the expected value of the player who retains the item at the end of the process. We explore the extent to which the quality of mechanisms’ approximations is tied with the information that the players hold. Without prior information regarding the value of the other player, it is not hard to see that no mechanism can always guarantee a reasonable approximation to the welfare. Therefore, more information is necessary to achieve good approximations. In particular, consider the following hierarchy of canonical information models: 1. Independent private values. The private value of each player is drawn from a known distribution, independently of the value of the other players. 2. Correlated private values. The private values of the players are drawn from a joint distribution. 3. Interdependent private values. Each player receives a private signal, and their value for the item is a public function of all signals. Thus, a player may not even know their own value, that is, they are not fully informed. Note that this list is not exhaustive, as the models can be further distinguished and refined. For example, interdependent values contain the special case of the common value model, where all players share the same underlying valuation but receive different signals about it. However, the common value model is generally less relevant in our context since the mechanism that never trades the item maximizes social welfare. We can now contextualize welfare maximization in bilateral trade within this hierarchy. For independent private values, the seminal result of Myerson and Satterthwaite 1983 dictates that for bilateral trade there exist no IC (Bayesian or Dominant-Strategy IC), individually rational mechanism that simultaneously maximizes social welfare and maintains budget balance. Mechanisms satisfying all three properties with constant approximation guarantees to the optimal social welfare have been proposed in [ 5 , 13 , 6 , 28 , 30 , 10 ] . For the problem of bilateral trade with correlated values, Dobzinski and Shaulker 2024 provide a constant-factor approximation to the optimal social welfare. Mechanisms for interdependent valuations were studied in both economics and computer science, primarily in the setting of auctions [ 32 , 27 , 14 , 34 , 17 , 18 , 22 , 23 , 19 , 20 , 21 , 12 , 11 ] . In the context of bilateral trade, [ 26 , 25 , 29 ] examined conditions under which an optimal solution exists. Brooks and Du [ 7 ] analyze a setting with the additional assumption that, in every realization, the buyer’s value exceeds the seller’s by at least some known amount. They identify a condition under which there exist information structures where the gains-from-trade can be inapproximable. In contrast, we study a much more general environment, and ask when approximation is even possible. Settings with interdependent values are generally more challenging to analyze. The complexity arises because players have to infer their valuations based on others’ private information, which may lead to complex belief updating and strategic inference [ 2 , 32 ] . To explain this, consider any posted price mechanism. In the independent private values model, incentive compatibility is immediate—each player’s optimal strategy is simply to accept or reject the posted price based on their private valuation. The primary challenge lies, therefore, in proving that the mechanism achieves a good approximation ratio for welfare. However, when values are interdependent, proving incentive compatibility becomes significantly more complex. In fact, an equilibrium does not necessarily exist. To see why, consider a price set by the mechanism designer. Trade occurs only if both players accept the price. Take, for instance, the seller’s perspective. If the buyer rejects the offer, no trade will happen regardless of the seller’s decision. Therefore, the seller should evaluate the offer assuming that the buyer accepts it, leading them to update their belief about their own value for the item. Similarly, the buyer must update their own value assuming that the seller accepts the trade. This process of mutual updating of beliefs might lead to a situation where no equilibrium exists. We discuss this with a concrete example in Appendix A.2 . Our Model We consider a model of bilateral trade where the players’ valuation functions are additively separable in both signals. That is, if x_{s} and x_{b} are the private signals received by the seller and the buyer, respectively, then there exist functions g^{b}_{x_{b}} and g^{b}_{x_{s}} such that the buyer’s value can be expressed as: v_{b}(x_{b},x_{s})=g^{b}_{x_{b}}{}(x_{b})+g^{b}_{x_{s}}(x_{s}) and functions g^{s}_{x_{b}} and g^{s}_{x_{s}} such that the seller’s value can be expressed as: v_{s}(x_{b},x_{s})=g^{s}_{x_{b}}{}(x_{b})+g^{s}_{x_{s}}(x_{s}). We assume that g^{b}_{x_{b}},g^{b}_{x_{s}},g^{s}_{x_{b}},g^{s}_{x_{s}} are non-decreasing 1 1 1 We note that all of our positive results holds without this assumption. and that x_{s},x_{b} are independently drawn from the interval [0,1] . Each tuple of g^{b}_{x_{b}},g^{b}_{x_{s}},g^{s}_{x_{b}},g^{s}_{x_{s}} defines an information structure , as it determines the influence of the buyer and seller’s signals on both the self and the other. As we work in the combination of the interdependent values and two-sided settings, we seek mechanisms that are Bayesian incentive-compatible and interim individually rational. 2 2 2 Indeed, in Appendix A.1 we demonstrate that stronger notions like ex-post incentive compatibility and ex-post individual rationality have little power in our setting. As we will see later, it is not hard to come up with information structures for which there is no Bayesian incentive-compatible mechanism that can achieve a good approximation. Thus, our goal is to obtain a better understanding of which information structures admit a Bayesian incentive-compatible, budget-balanced mechanism that achieves a good approximation to social welfare and which are not. In this paper, our technical contributions take