References & Citations
Computer Science > Computer Science and Game Theory
Title: Bilateral Trade with Correlated Values
(Submitted on 19 Aug 2023 (v1), last revised 16 Apr 2024 (this version, v2))
Abstract: We study the bilateral trade problem where a seller owns a single indivisible item, and a potential buyer seeks to purchase it. Previous mechanisms for this problem only considered the case where the values of the buyer and the seller are drawn from independent distributions. In this paper, we study bilateral trade mechanisms when the values are drawn from a joint distribution.
We prove that the buyer-offering mechanism guarantees an approximation ratio of $\frac e {e-1} \approx 1.582$ to the social welfare even if the values are drawn from a joint distribution. The buyer-offering mechanism is Bayesian incentive compatible, but the seller has a dominant strategy. We prove the buyer-offering mechanism is optimal in the sense that no Bayesian mechanism where one of the players has a dominant strategy can obtain an approximation ratio better than $\frac e {e-1}$. We also show that no mechanism in which both sides have a dominant strategy can provide any constant approximation to the social welfare when the values are drawn from a joint distribution.
Finally, we prove some impossibility results on the power of general Bayesian incentive compatible mechanisms. In particular, we show that no deterministic Bayesian incentive-compatible mechanism can provide an approximation ratio better than $1+\frac {\ln 2} 2\approx 1.346$.
Submission history
From: Ariel Shaulker [view email][v1] Sat, 19 Aug 2023 09:44:41 GMT (47kb)
[v2] Tue, 16 Apr 2024 14:42:17 GMT (50kb)
Link back to: arXiv, form interface, contact.