Name
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 valueweakly 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 approximate to 0.121 fraction of the first-best. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1145/3519935.3520054 | PROCEEDINGS OF THE 54TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '22) |
Keywords | DocType | ISSN |
bilateral trade, mechanism design, approximation algorithms | Conference | 0737-8017 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Yuan Deng | 1 | 25 | 11.91 |
| Jieming Mao | 2 | 0 | 0.34 |
| Balasubramanian Sivan | 3 | 4 | 4.52 |
| Kangning Wang | 4 | 7 | 6.03 |