💻 computer science

Profit Maximization in Bilateral Trade against a Smooth Adversary

本文提出了一种针对双边贸易中平滑对手且以利润最大化为目标的经纪人的学习算法，该算法通过利用平滑实例的连续性以及分层网构建技术，实现了紧致的 $\tilde{O}(\sqrt{T})$ 遗憾界，从而弥合了随机设定与完全对抗设定之间的性能差距。

原作者： Simone Di Gregorio, Paul Dütting, Federico Fusco, Chris Schwiegelshohn

发布于 2026-05-14

📖 1 分钟阅读☕ 轻松阅读

CC BY 4.0

原作者： Simone Di Gregorio, Paul Dütting, Federico Fusco, Chris Schwiegelshohn

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你是一位经营繁忙市场的媒人。每天，都会有一位新卖家和一位新买家出现，他们心中各自藏着一个秘密价格：卖家希望至少以 $X$ 的价格出售，而买家希望至多支付 $Y$ 的价格。

你的任务是制定交易规则。你希望获得尽可能多的利润（即买家支付金额与卖家所得金额之间的差额），但你必须保持公平：

你不能诱骗他们谎报价格。
他们参与交易不应遭受损失。

挑战在于：你无法提前知晓他们的秘密价格。你必须通过试错，随时间推移学习出最佳规则。

三种类型的“对手”

在本文中，作者研究了在面对三种不同类型的“对手”（即生成价格的人）时，学习这些规则的难易程度：

随机者（随机/独立同分布）： 想象价格是从一个固定不变的配方中抽取的（就像掷骰子）。这种情况很容易学习。你只需保持一个运行平均值，就能很快变得非常擅长。
诡计者（对抗性）： 想象一位精通你策略的幕后黑手，他故意挑选价格来迷惑你，使你失败。在这种最坏的情况下，论文证实了一个已知事实：你无法学习。无论你的算法多么聪明，你永远无法追上最佳策略。
平滑对抗者（新英雄）： 这是中间地带。对手每天仍然可以更改价格来干扰你，但他们不被允许过于“尖锐”。他们不能瞬间从$0.01 $的价格切换到$ 0.99$。他们的变化必须是“平滑”的，就像温柔的波浪，而不是锯齿状的闪电。

核心问题： 我们能否有效地向这位“平滑对抗者”学习？作者回答是，并证明了这一点。

解决方案：“阶梯”策略（HIER-MECH）

主要的困难在于，你可以设定的“规则”极其复杂。你不仅仅是在挑选一个单一的价格（比如“以$5$出售”）。你是在挑选一张复杂的地图，它根据买家和卖家的价格来决定何时发生交易。这张地图就像画在一张正方形纸上的形状。

如果你试图通过测试每一种可能的版本来猜测这个形状，你需要测试无限多个形状。这是不可能的。

作者发明了一种巧妙的算法，称为HIER-MECH（分层机制）。其工作原理如下，使用阶梯类比：

粗阶梯（横档）： 想象一个横档间距很远的梯子。在底部，你有非常简单、块状的形状（比如一个大正方形）。这些形状的数量很少。
细阶梯（横档）： 随着你向上攀登，横档变得越来越近。形状变得更加详细和精确。
策略： 算法不是试图立即找到完美的形状，而是在这个梯子上玩一场“猜测与验证”的游戏。
- 它从底部开始，测试那些巨大而简单的形状。
- 它使用一种智能的投注系统（称为HEDGE）来决定哪条向上的路径看起来最有希望。
- 它不仅仅选择一个形状；它在梯子上构建一条“随机游走”路径。它实际上是在说：“我有 90% 的把握答案在这个大致区域，所以我接下来将测试该区域内稍微更详细的形状。”

通过一步步攀登这个阶梯，算法在不过载的情况下学会了复杂的形状。它在“过于简单”的代价（错失利润）与“过于复杂”的代价（需要过多数据来学习）之间取得了平衡。

结果：完美的平衡

论文证明，这种阶梯策略极其高效。

速度： 算法的学习速度约为 $\sqrt{T}$ （其中 $T$ 是天数）。
对比： 这与从“随机者”（简单情况）学习的速度相同。
突破： 这是一个巨大的成就，因为直到目前，人们认为只有当数据是随机的时，你才能以这种速度学习。作者表明，即使面对“平滑对抗者”（他们试图迷惑你，只是不太激进），你也能像一切随机时那样快速学习。

他们还表明，这一结果是紧确的。你无法做到比 $\sqrt{T}$ 更好；这是该问题可能的最快速度。

一个支线任务：“联合广告”问题

作者还表明，他们的阶梯策略适用于一个相关的问题，称为联合广告。

场景： 想象两位广告商希望共同购买一个广告位。要么两人都得到它，要么谁都得不到。
联系： 作者证明了这个问题在数学上类似于双边贸易问题。通过将“联合广告”问题翻译成他们的“双边贸易”框架，他们可以使用相同的阶梯算法。
结果： 他们提高了该广告问题之前的最佳已知学习速度，使其与贸易问题一样快。

总结

简而言之，这篇论文解决了一个经济学谜题：“当客户棘手但并非不可能对付时，你如何学习在市场中最赚钱？”

答案是不再试图一次性猜出完美的规则。相反，使用分层阶梯先测试简单的规则，然后逐渐完善它们。这种方法允许经纪人以与世界完全随机时相同的速度进行学习，即使世界正试图变得困难，只要这种困难不是过于“锯齿状”。

技术摘要：针对平滑对手的双边贸易利润最大化

问题陈述
本文探讨了在线学习框架下双边贸易中的利润最大化问题。在该设定中，一名经纪人作为中介，连接一位卖家和一位买家，双方各自拥有关于商品的私有估值。经纪人必须设计一种机制（包含分配规则和支付函数），在满足**占优策略激励相容（DSIC）和事后个体理性（IR）**的同时，最大化期望利润。

学习环境由 $\sigma$ -平滑对手定义。与估值从固定分布中独立同分布（i.i.d.）抽取的标准随机设定，或估值可以任意选取的标准对抗设定不同， $\sigma$ -平滑对手在每个时间步选择的分布受到“不过于尖锐”的约束（即，其在任何博雷尔集上的概率质量被该集合的勒贝格测度除以 $\sigma$ 所界定）。

核心挑战在于动作空间的非参数性质。有效机制的集合是无限且复杂的；一个机制由单位正方形 $[0,1]^2$ 中的单调分配区域及相关的迈尔森支付定义。这使得该问题区别于通常关注参数化设定（例如，学习单一保留价格）的标准在线机制设计文献。先前的工作已证实，在一般对抗设定中次线性遗憾是不可能的，但在 i.i.d.设定中是可以实现的。开放性问题在于，平滑对手模型能否弥合这两个极端之间的“差距”。

方法论
作者提出了一种名为HIER-MECH的学习算法，实现了 $\tilde{O}(\frac{1}{\sigma}\sqrt{T})$ 的遗憾界。该方法论依赖于三个关键技术组件：

网格机制与 $L_1$ -网保证：
作者使用 $\epsilon$ -网格机制对连续机制空间进行离散化，其中分配区域是步长为 $\epsilon$ 的均匀网格中瓦片的并集。关键在于，他们证明了针对该问题的新颖 $L_1$ -网保证（引理 2）。他们表明，对于任何机制 $M$ ，都存在一个网格近似 $\phi_\epsilon(M)$ ，使得期望利润差异的界限为 $O(\epsilon/\sigma)$ 。该界限依赖于对手的平滑性以及双边贸易支付的具体几何结构（向分配边界的投影）。与依赖确定性 $L_\infty$ 网（该假设类中不存在此类网）的先前工作不同，这种概率界限足以支持分析。
算法链式结构：
为了克服标准“跟随领导者”（Follow-the-Leader）或“ Hedge"方法的局限性（这些方法在非平稳设定中失效，或直接应用于网格时产生次优速率如 $O(T^{2/3})$ ），作者采用了算法链式结构。
- 他们构建了一棵机制树，其中层级 $h$ 的节点代表 $2^{-h}$ -网格机制。
- 该算法维护多个HEDGE 算法的局部实例（树中每个内部节点对应一个）。
- 在每个时间步，算法在树上执行随机游走，根据局部 HEDGE 分布选择一个叶子机制。
- 这种分层结构在对抗环境中模拟了概率链式结构（用于随机设定）的效果。它使算法能够实现"Dudley 型”界限，优于标准的 $\sqrt{T \log N}$ 专家界限（其中 $N$ 为专家数量）。
联合广告问题的归约：
本文建立了从联合广告问题（两个代理合作购买一种不可排他商品）到双边贸易的形式化归约。通过将双边贸易域限制在特定的子矩形并应用坐标变换，他们将联合广告问题映射到双边贸易设定。该归约有两个目的：
- 它将 $\tilde{O}(\frac{1}{\sigma}\sqrt{T})$ 上界转移到联合广告问题，优于先前的 $O(T^{2/3})$ 界限。
- 它为双边贸易提供了 $\Omega(\sqrt{T})$ 的下界，证明了 HIER-MECH 算法的速率是紧的（在多项式对数因子范围内）。

关键结果

遗憾界：HIER-MECH 算法针对 $\sigma$ -平滑对手实现了 $O(\frac{1}{\sigma}\sqrt{T} \log T)$ 的遗憾界。
紧性：该速率与随机 i.i.d.情况下的极小极大速率相匹配，并与一般对抗情况（其中次线性遗憾不可能）区分开来。 $\Omega(\sqrt{T})$ 下界证实了对 $T$ 的依赖是最优的。
联合广告：该归约为联合广告问题产生了紧的 $\tilde{O}(\frac{1}{\sigma}\sqrt{T})$ 遗憾界，解决了先前文献中的一个开放性问题。

意义与主张
本文声称显著拓宽了在经济机制设计中可实现快速学习速率的设定范围。通过将强遗憾保证从 i.i.d.设定扩展到 $\sigma$ -平滑对手，作者证明了平滑性是克服经济问题中对抗性不可能结果的有效工具。

这项工作代表了算法链式结构在非参数机制设计问题中的首次应用，超越了其在在线回归中的传统用途。作者强调，虽然实现了统计速率（ $\sqrt{T}$ ），但仍存在计算差距：HIER-MECH 的运行时间按 $\exp(\sqrt{T})$ 缩放，而 i.i.d.设定允许多项式时间算法。缩小这一计算差距并收紧对平滑参数 $\sigma$ 的依赖被确定为主要的开放问题。

总之，本文刻画了针对平滑对手进行双边贸易学习的信息论极限，表明从统计角度来看，尽管需要根本不同的算法技术，平滑对手与 i.i.d.设定“一样容易”。

三种类型的“对手”

解决方案：“阶梯”策略（HIER-MECH）

结果：完美的平衡

一个支线任务：“联合广告”问题

总结

技术摘要：针对平滑对手的双边贸易利润最大化

类似论文