TY - GEN
T1 - Improved Approximation Ratios of Fixed-Price Mechanisms in Bilateral Trades
AU - Liu, Zhengyang
AU - Ren, Zeyu
AU - Wang, Zihe
N1 - Publisher Copyright:
© 2023 ACM.
PY - 2023/6/2
Y1 - 2023/6/2
N2 - We continue the study of the performance for fixed-price mechanisms in the bilateral trade problem, and improve approximation ratios of welfare-optimal mechanisms in several settings. Specifically, in the case where only the buyer distribution is known, we prove that there exists a distribution over different fixed-price mechanisms, such that the approximation ratio lies within the interval of [0.71, 0.7381]. Furthermore, we show that the same approximation ratio holds for the optimal fixed-price mechanism, when both buyer and seller distributions are known. As a result, the previously best-known (1-1/e+0.0001)-approximation can be improved to 0.71. Additionally, we examine randomized fixed-price mechanisms when we receive just one single sample from the seller distribution, for both symmetric and asymmetric settings. Our findings reveal that posting the single sample as the price remains optimal among all randomized fixed-price mechanisms.
AB - We continue the study of the performance for fixed-price mechanisms in the bilateral trade problem, and improve approximation ratios of welfare-optimal mechanisms in several settings. Specifically, in the case where only the buyer distribution is known, we prove that there exists a distribution over different fixed-price mechanisms, such that the approximation ratio lies within the interval of [0.71, 0.7381]. Furthermore, we show that the same approximation ratio holds for the optimal fixed-price mechanism, when both buyer and seller distributions are known. As a result, the previously best-known (1-1/e+0.0001)-approximation can be improved to 0.71. Additionally, we examine randomized fixed-price mechanisms when we receive just one single sample from the seller distribution, for both symmetric and asymmetric settings. Our findings reveal that posting the single sample as the price remains optimal among all randomized fixed-price mechanisms.
KW - Bilateral Trade
KW - Fixed-Price Mechanism
KW - Social Welfare
UR - http://www.scopus.com/inward/record.url?scp=85163083018&partnerID=8YFLogxK
U2 - 10.1145/3564246.3585160
DO - 10.1145/3564246.3585160
M3 - Conference contribution
AN - SCOPUS:85163083018
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 751
EP - 760
BT - STOC 2023 - Proceedings of the 55th Annual ACM Symposium on Theory of Computing
A2 - Saha, Barna
A2 - Servedio, Rocco A.
PB - Association for Computing Machinery
T2 - 55th Annual ACM Symposium on Theory of Computing, STOC 2023
Y2 - 20 June 2023 through 23 June 2023
ER -