Approximately efficient bilateral trade
Authors:
Open Access
- 9 June 2022
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 718-721
Abstract
We study bilateral trade between two strategic agents. The celebrated result of Myerson and Satterthwaite states that in general, no incentive-compatible, individually rational and weakly budget balanced mechanism can be efficient. I.e., no mechanism with these properties can guarantee a trade whenever buyer value exceeds seller cost. Given this, a natural question is whether there exists a mechanism with these properties that guarantees a constant fraction of the first-best gains-from-trade, namely a constant fraction of the gains-from-trade attainable whenever buyer’s value weakly exceeds seller’s cost. In this work, we positively resolve this long-standing open question on constant-factor approximation, mentioned in several previous works, using a simple mechanism that obtains a 1/8.23 ≈ 0.121 fraction of the first-best.Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- Dynamic Double Auctions: Towards First Best2019
- The Best of Both Worlds2018
- Fixed Price Approximability of the Optimal Gain from Trade2017
- Approximately Efficient Two-Sided Combinatorial Auctions2017
- Approximating Gains from Trade in Two-sided Markets via Simple Mechanisms2017
- Approximating Gains-from-Trade in Bilateral Trading2016
- Approximately Efficient Double Auctions with Strong Budget Balance2015
- A dominant strategy double auctionJournal of Economic Theory, 1992
- Efficient allocation with continuous quantitiesJournal of Economic Theory, 1991
- Efficient mechanisms for bilateral tradingJournal of Economic Theory, 1983