Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userInteractive Communication in Bilateral Trade
142
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We define a model of interactive communication where two agents with private types can exchange information before a game is played. The model contains Bayesian persuasion as a special case of a one-round communication protocol. We define message complexity corresponding to the minimum number of interactive rounds necessary to achieve the best possible outcome. Our main result is that for bilateral trade, agents dont stop talking until they reach an efficient outcome: Either agents achieve an efficient allocation in finitely many rounds of communication; or the optimal communication protocol has infinite number of rounds. We show an important class of bilateral trade settings where efficient allocation is achievable with a small number of rounds of communication.
rate research
Read More
Bilateral trade, a fundamental topic in economics, models the problem of intermediating between two strategic agents, a seller and a buyer, willing to trade a good for which they hold private valuations. Despite the simplicity of this problem, a classical result by Myerson and Satterthwaite (1983) affirms the impossibility of designing a mechanism which is simultaneously efficient, incentive compatible, individually rational, and budget balanced. This impossibility result fostered an intense investigation of meaningful trade-offs between these desired properties. Much work has focused on approximately efficient fixed-price mechanisms, i.e., Blumrosen and Dobzinski (2014; 2016), Colini-Baldeschi et al. (2016), which have been shown to fully characterize strong budget balanced and ex-post individually rational direct revelation mechanisms. All these results, however, either assume some knowledge on the priors of the seller/buyer valuations, or a black box access to some samples of the distributions, as in D{u}tting et al. (2021). In this paper, we cast for the first time the bilateral trade problem in a regret minimization framework over rounds of seller/buyer interactions, with no prior knowledge on the private seller/buyer valuations. Our main contribution is a complete characterization of the regret regimes for fixed-price mechanisms with different models of feedback and private valuations, using as benchmark the best fixed price in hindsight. More precisely, we prove the following bounds on the regret: $bullet$ $widetilde{Theta}(sqrt{T})$ for full-feedback (i.e., direct revelation mechanisms); $bullet$ $widetilde{Theta}(T^{2/3})$ for realistic feedback (i.e., posted-price mechanisms) and independent seller/buyer valuations with bounded densities; $bullet$ $Theta(T)$ for realistic feedback and seller/buyer valuations with bounded densities; $bullet$ $Theta(T)$ for realistic feedback and independent seller/buyer valuations; $bullet$ $Theta(T)$ for the adversarial setting.
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.
We study the design of revenue-maximizing bilateral trade mechanisms in the correlated private value environment. We assume the designer only knows the expectations of the agents values, but knows neither the marginal distribution nor the correlation structure. The performance of a mechanism is evaluated in the worst-case over the uncertainty of joint distributions that are consistent with the known expectations. Among all dominant-strategy incentive compatible and ex-post individually rational mechanisms, we provide a complete characterization of the maxmin trade mechanisms and the worst-case joint distributions.
The study of interactive proofs in the context of distributed network computing is a novel topic, recently introduced by Kol, Oshman, and Saxena [PODC 2018]. In the spirit of sequential interactive proofs theory, we study the power of distributed interactive proofs. This is achieved via a series of results establishing trade-offs between various parameters impacting the power of interactive proofs, including the number of interactions, the certificate size, the communication complexity, and the form of randomness used. Our results also connect distributed interactive proofs with the established field of distributed verification. In general, our results contribute to providing structure to the landscape of distributed interactive proofs.
We study the bilateral trade problem: one seller, one buyer and a single, indivisible item for sale. It is well known that there is no fully-efficient and incentive compatible mechanism for this problem that maintains a balanced budget. We design simple and robust mechanisms that obtain approximate efficiency with these properties. We show that even minimal use of statistical data can yield good approximation results. Finally, we demonstrate how a mechanism for this simple bilateral-trade problem can be used as a black-box for constructing mechanisms in more general environments.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
