通过可控预算违规，实现双边交易中更优的后悔率。
Better Regret Rates in Bilateral Trade via Sublinear Budget Violation
- 允许全局预算约束有小幅度违反，设计新算法降低后悔率。
- 当预算违规不超过 $T^β$ 时，后悔率可达 $ ilde O(T^{1 - β/3})$。
- 首次完整刻画后悔率与预算违规的权衡关系，适合机制设计研究者。
双边交易是算法经济学的核心问题。近期工作尝试用无后悔学习算法设计交易机制，但在每步都需满足预算平衡时，无后悔学习不可能实现。Bernasconi 等人 [Ber+24] 通过放宽预算平衡约束为仅在所有时间步上全局成立，解决了该难题，提出算法达到 $ ilde O(T^{3/4})$ 回悔率，并给出 $Ω(T^{5/7})$ 的下界。本文在此基础上，研究最优后悔率如何随允许的全局预算违规程度变化。具体地，我们设计了一种算法，在预算违规不超过 $T^β$（任意 $βig[ rac{3}{4}, rac{6}{7}ig]$）的前提下，实现 $ ilde O(T^{1 - β/3})$ 的后悔率。我们进一步提供匹配下界，完全刻画了后悔率与预算违规之间的权衡。结果表明，Bernasconi 等人提出的 $ ilde O(T^{3/4})$ 上界和 $Ω(T^{5/7})$ 下界均为紧致。
原文摘要 · Abstract (English)
Bilateral trade is a central problem in algorithmic economics, and recent work has explored how to design trading mechanisms using no-regret learning algorithms. However, no-regret learning is impossible when budget balance has to be enforced at each time step. Bernasconi et al. [Ber+24] show how this impossibility can be circumvented by relaxing the budget balance constraint to hold only globally over all time steps. In particular, they design an algorithm achieving regret of the order of $\tilde O(T^{3/4})$ and provide a lower bound of $Ω(T^{5/7})$. In this work, we interpolate between these two extremes by studying how the optimal regret rate varies with the allowed violation of the global budget balance constraint. Specifically, we design an algorithm that, by violating the constraint by at most $T^β$ for any given $β\in [\frac{3}{4}, \frac{6}{7}]$, attains regret $\tilde O(T^{1 - β/3})$. We complement this result with a matching lower bound, thus fully characterizing the trade-off between regret and budget violation. Our results show that both the $\tilde O(T^{3/4})$ upper bound in the global budget balance case and the $Ω(T^{5/7})$ lower bound under unconstrained budget balance violation obtained by Bernasconi et al. [Ber+24] are tight.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。