在扰动市场中设计了能自适应腐败程度的交易算法，兼顾收益与预算平衡。
Regret Minimization in Bilateral Trade With Perturbed Markets
- 引入扰动市场模型，结合随机与对抗性因素建模真实交易环境。
- 实现 $ ilde{ m O}(T^{3/4}) + m O(C/log(T))$ 的后悔界，优于纯随机或对抗设定。
- 适用于需兼顾长期收益与预算约束的动态交易场景，如平台定价系统。
我们研究在重复买卖双方交易中最大化交易收益（GFT）的问题，受全局预算平衡约束。尽管该问题在纯粹对抗性和随机环境中已有深入理解，但二者存在显著差异：对抗环境允许对最优固定价格机制实现无后悔学习，而随机环境则可对期望预算平衡的价格分布实现无后悔学习。这种差距至关重要，因为期望平衡策略可使GFT提升两倍。本文通过研究扰动市场（即底层随机分布受对抗性扰动 $C$ 影响）来弥合这一鸿沟。我们设计了一种自适应算法，在对抗扰动水平下达到 $ ilde{ m O}(T^{3/4}) + m O(C/log(T))$ 的后悔界，优于最优预算平衡价格分布；同时保持对每轮预算平衡基线的 $ ilde{ m O}(T^{3/4})$ 最坏情况后悔界，确保在完全对抗环境中的最优性。
原文摘要 · Abstract (English)
We address the problem of maximizing Gain from Trade (GFT) in repeated buyer-seller exchanges subject to global budget balance constraints. While this problem is well-understood in purely adversarial and stochastic settings, these environments exhibit a sharp dichotomy: adversarial environments allow for no-regret learning against the best fixed-price mechanism, whereas stochastic environments allow for no-regret learning against the best distribution over prices that is budget balanced in expectation. This gap is significant, as policies balanced in expectation can increase the GFT by a multiplicative factor of two. In this work, we bridge these extremes by studying perturbed markets, where an underlying stochastic distribution is subject to an adversarial corruption $C$. We design an algorithm that adaptively scales with the level of corruption, achieving an $\tilde{\mathcal{O}}(T^{3/4}) + \mathcal{O}(C\log(T))$ regret bound against the best budget-balanced distribution over prices. Simultaneously, our algorithm maintains the worst-case $\tilde{\mathcal{O}}(T^{3/4})$ regret bound relative to a per-round budget-balanced baseline, ensuring optimality even in fully adversarial environments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。