Approximately efficient bilateral trade
Approximately efficient bilateral trade
复制标题
双边贸易近似有效
DOI：
10.1145/3519935.3520054
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Kangning Wang
中科院分区：
文献类型：
--
作者：
Yuan Deng;Jieming Mao;Balasubramanian Sivan;Kangning Wang
我们研究两个战略代理人之间的双边贸易。Myerson和Satterthwaite的著名结果指出，一般来说，没有激励相容的，个人理性的和弱预算平衡的机制可以是有效的。也就是说，任何具有这些属性的机制都不能保证在买方价值超过卖方成本时进行交易。鉴于此，一个自然的问题是，是否存在一种具有这些属性的机制，该机制保证第一最佳交易收益的恒定比例，即当买方的价值弱于卖方的成本时，可获得的交易收益的恒定比例。在这项工作中，我们积极地解决了这个长期存在的关于常数因子近似的开放问题，在以前的几项工作中提到，使用一个简单的机制，获得了1/8.23 <$0.121的分数的第一个最好的。
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.
影响因子：
1.2
作者：
Colini-Baldeschi, Riccardo;Goldberg, Paul W.;Keijzer, Bart de;Leonardi, Stefano;Roughgarden, Tim;Turchetta, Stefano
通讯作者：
Turchetta, Stefano
DOI：
--
发表时间：
2021
期刊：
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA
影响因子：
--
作者：
Cai, Y.;Goldner, K.;Ma, S.;Zhao, M.
通讯作者：
Zhao, M.
双边贸易中的固定价格近似值
DOI：
10.1137/1.9781611977073.115
发表时间：
2022
期刊：
Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA
影响因子：
--
作者：
Kang, Zi Yang;Pernice, Francisco;Vondrák, Jan
通讯作者：
Vondrák, Jan