Abstract:We examine fixed-price mechanisms in bilateral trade through the lens of regret minimization. Our main results are twofold. (i) For independent values, a near-optimal $\widetilde{\Theta}(T^{2/3})$ tight bound for $\textsf{Global Budget Balance}$ fixed-price mechanisms with two-bit/one-bit feedback. (ii) For correlated/adversarial values, a near-optimal $\Omega(T^{3/4})$ lower bound for $\textsf{Global Budget Balance}$ fixed-price mechanisms with two-bit/one-bit feedback, which improves the best known $\Omega(T^{5/7})$ lower bound obtained in the work [BCCF24] and, up to polylogarithmic factors, matches the $\widetilde{\mathcal{O}}(T^{3 / 4})$ upper bound obtained in the same work. Our work in combination with the previous works [CCCFL24mor, CCCFL24jmlr, AFF24, BCCF24] (essentially) gives a thorough understanding of regret minimization for fixed-price bilateral trade.
En route, we have developed two technical ingredients that might be of independent interest: (i) A novel algorithmic paradigm, called $\textit{fractal elimination}$, to address one-bit feedback and independent values. (ii) A new $\textit{lower-bound construction}$ with novel proof techniques, to address the $\textsf{Global Budget Balance}$ constraint and correlated values.
| Subjects: | Computer Science and Game Theory (cs.GT); Machine Learning (cs.LG) |
| Cite as: | arXiv:2504.04349 [cs.GT] |
| (or arXiv:2504.04349v3 [cs.GT] for this version) | |
| https://doi.org/10.48550/arXiv.2504.04349 arXiv-issued DOI via DataCite |
From: Yaonan Jin [view email]
[v1]
Sun, 6 Apr 2025 03:56:42 UTC (86 KB)
[v2]
Wed, 5 Nov 2025 02:55:03 UTC (83 KB)
[v3]
Tue, 19 May 2026 12:56:02 UTC (81 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。