Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRobust Bilateral Trade Mechanisms with Known Expectations
346
0
0.0
(
0
)
Authors
Wanchang Zhang
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
This study examines the mechanism design problem for public-good provision in a large economy with $n$ independent agents. We propose a class of dominant-strategy incentive compatible (DSIC) and ex post individual rational (EPIR) mechanisms which we call the adjusted mean-thresholding (AMT) mechanisms. We show that when the cost of provision grows slower than the $sqrt{n}$ rate, the AMT mechanisms are both asymptotically ex ante budget balanced (AEABB) and asymptotically efficient (AE). When the cost grows faster than the $sqrt{n}$ rate, in contrast, we show that any DSIC, EPIR, and AEABB mechanism must have provision probability converging to zero and hence cannot be AE. Lastly, the AMT mechanisms are more informationally robust when compared to, for example, the second-best mechanism. This is because the construction of AMT mechanisms depends only on the first moments of the valuation distributions.
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 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.
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 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
