在平滑对抗者模型下，设计了能实现近最优收益的双边贸易算法。
Profit Maximization in Bilateral Trade against a Smooth Adversary
- 利用平滑性与分层网络构造，构建可分析的策略空间
- 实现$ ilde{O}(\ oot\of{T})$的损失上界，逼近最优率
- 适用于在线学习中的机制设计，对实际交易系统有指导意义
双边贸易建模了中介商在买卖双方之间促成商品交易的任务。本文从利润最大化中介的角度出发，在在线学习框架下研究该问题，其中买卖双方估值由平滑对抗者生成。我们设计了一种学习算法，保证$ ilde{O}(\sqrt{T})$的遗憾界，该界在时间范围$T$上紧致（仅差多对数因子）。该结果匹配随机独立同分布情形下的极小极大率，且显著区别于无法实现次线性遗憾的全对抗情形。通过将独立同分布情形下的强遗憾保证拓展至平滑对抗者，我们显著扩大了快速收敛率可达成的场景范围，同时填补了这一基础经济问题遗憾谱的重要空白。为应对该对抗者的挑战，我们利用平滑实例的连续性，并结合中介动作空间的分层网络构造，通过算法链技术进行分析。此外，我们展示了这些技术的适用性：在相关的联合广告问题机制设计模型中，也导出了同样紧致的$ ilde{O}(\sqrt{T})$遗憾界。
原文摘要 · Abstract (English)
Bilateral trade models the task of intermediating between two strategic agents, a seller and a buyer, who wish to trade a good. We study this problem from the perspective of a profit-maximizing broker within an online learning framework, where the agents' valuations are generated by a smooth adversary. We devise a learning algorithm that guarantees a $\tilde{O}(\sqrt{T})$ regret bound, which is tight in the time horizon $T$ up to poly-logarithmic factors. This matches the minimax rate for the stochastic i.i.d. case, and is also well separated from the adversarial setting, where sublinear-regret is unattainable. By extending the strong regret guarantees from the i.i.d. case to the smooth adversary, we significantly broaden the scope of settings where such fast rate is achievable, while closing an important gap in the regret landscape of this fundamental economic problem. To overcome the challenges posed by this adversary, we leverage a continuity property of smooth instances and combines this with a hierarchical net-construction of the broker's action space, which is analyzed via algorithmic chaining. We showcase the applicability of these techniques by deriving a similarly tight $\tilde{O}(\sqrt{T})$ regret bound for a related mechanism design model: the joint ads problem.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。