研究固定价格双边交易的后悔最小化，给出紧致的理论边界。
Tight Regret Bounds for Fixed-Price Bilateral Trade
- 提出分形消除算法应对单比特反馈与独立价值情形。
- 在相关/对抗性价值下，证明了Ω(T^{3/4})的下界，优于之前结果。
- 适用于机制设计、在线学习领域的研究人员，理论价值高。
我们从后悔最小化的视角研究固定价格机制在双边交易中的表现。主要成果有两方面：(i) 对于独立价值情形，针对具有两位/一位反馈的全局预算平衡机制，给出了近似最优的 ildeΘ(T^{2/3})紧致上界；(ii) 对于相关或对抗性价值情形，针对相同机制，建立了Ω(T^{3/4})的下界，优于先前工作[BCCF24]中Ω(T^{5/7})的结果，并在多对数因子内匹配了该工作中获得的 ilde{/mathcal{O}}(T^{3/4})上界。结合此前工作[CCCFL24mor, CCCFL24jmlr, AFF24, BCCF24]，本研究基本厘清了固定价格双边交易中的后悔最小化问题。过程中发展出两项关键技术：(i) 针对单比特反馈与独立价值的新算法范式——分形消除；(ii) 针对全局预算平衡约束与相关价值的新下界构造及证明方法，可能具有独立研究意义。
原文摘要 · Abstract (English)
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Θ(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 $Ω(T^{3/4})$ lower bound for $\textsf{Global Budget Balance}$ fixed-price mechanisms with two-bit/one-bit feedback, which improves the best known $Ω(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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。