Profit Maximization in Bilateral Trade against a Smooth Adversary¶

会议: NeurIPS 2026
arXiv: 2605.12664
OpenReview: https://openreview.net/forum?id=MaghUZLEQt
领域: 其他
关键词: 双边贸易, 利润最大化, 平滑对抗环境, 算法链式法则, 机制设计

一句话总结¶

针对双边贸易中非参数化机制空间的在线利润最大化问题，本文提出基于算法链式法则的分层学习算法 Hier-Mech，在 $\sigma$-平滑对抗环境下实现了极小化极大紧致的 $\tilde{O}(\frac{1}{\sigma}\sqrt{T})$ 遗憾界，并证明了与联合广告问题的双向几何规约。

研究背景与动机¶

双边贸易（Bilateral Trade）是微观经济学与算法机制设计中的基准模型，刻画了平台经纪人在持有私有估值的单卖家与单买家之间撮合交易的典型场景。在支配策略激励相容（DSIC）与事前个体理性（IR）的标准博弈论约束下，机制的支付规则完全由配置区域在单调性边界上的迈尔森投影唯一确定。当经纪人的优化目标从经典的社会福利转向商业平台最为关切的“期望利润最大化”时，机制空间由所有向左上方闭合的单调连续区域构成，呈现出本质上的非参数化特征，这与传统基于参数化搜索（如最优保留价、单一挂牌价）的在线拍卖机制形成了鲜明对比。

近期理论研究揭示了该问题在不同数据生成模型下的极端鸿沟：在估值服从未知固定分布的独立同分布（i.i.d.）随机设定下，通过概率链式法则可在多项式时间内达成 $\tilde{O}(\sqrt{T})$ 的快速收敛；然而在不可区分的任意对抗环境下，由于利润函数存在严重的跳跃不连续性，任何在线算法都无法取得次线性遗憾（存在 $\Omega(T)$ 的线性遗憾下界）。这种非平稳与无遗憾不可兼得的绝望困境，迫切需要超越最坏情况分析的理论框架，以回答在线学习能否在非平稳且具备适度规则性的市场环境中实现有效学习。

面对这一挑战，本文引入了 $\sigma$-平滑对抗模型（$\sigma$-Smooth Adversary），允许对抗方在每个时步自适应选取不同的估值联合分布，但要求其概率密度相对于勒贝格测度的尖峰程度被常数 $1/\sigma$ 严格约束。然而，现存的平滑在线学习技术大多依赖于有界的 fat-shattering 维度，而双边贸易利润函数在该维度下在任意尺度上均是无界的，这使得现有的平滑泛化界全部失效；若直接在均匀离散化网格空间上运行标准专家算法（如 Hedge），又会因为动作空间的组合爆炸陷入次优的 $O(T^{2/3})$ 遗憾瓶颈。核心 idea：利用平滑测度推导网格机制在期望意义下的首个一阶 $L^1$ 利润连续性近似界，并在多分辨率网格机制树上构建尺度自适应步长的算法链式随机游走策略，彻底消除非参数化空间与不连续收益造成的方差积累，达成理论最优的 $\tilde{O}(\frac{1}{\sigma}\sqrt{T})$ 遗憾界。

方法详解¶

整体框架¶

算法的核心任务是化解两个理论障碍：一是由于交易是否发生存在硬边界跃变，无法构建确定性的全局 $L^\infty$ 覆盖网络；二是多分辨率网格机制类的空间基数随分辨率呈双重指数级膨胀（在分辨率 $\varepsilon = 2^{-h}$ 下，网格机制数 $|\mathcal{M}_h| = \binom{2^{h+1}}{2^h} \approx (2e)^{2^h}$）。为此，本文提出了名为 Hier-Mech 的分层机制学习算法。

整体框架构建了一棵目标深度为 $H = \frac{1}{2} \lceil \log_2 T \rceil$ 的机制树 $\mathcal{T}$。树的第 $h$ 层由分辨率为 $2^{-h}$ 的网格机制类 $\mathcal{M}_h$ 组成，每个节点与其唯一的粗粒度内逼近父节点 $\phi_{h-1}(M)$ 相连。在运行时，算法并不在叶子节点构成的庞大动作集上做扁平化采样，而是从根节点 $M_\emptyset$ 开始，逐层执行由各层局部专家（Hedge）引导的级联随机游走，自顶向下采样出最终执行的叶子机制 $M^t$。在观察到真实买卖双方估值后，自底向上递归计算各层级联收益差，并独立更新整棵机制树上所有活跃节点的专家权重。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["环境输入：时步 t<br/>估值分布由 σ-平滑对抗方生成"] --> B["机制树构造与自顶向下采样<br/>深度 H = ceil(log2 T)/2 的网格机制树"]
    B --> C["分层专家策略级联决策<br/>从根节点向下运行局部 Hedge 随机游走"]
    C --> D["提出机制 Mt 并观测估值<br/>由叶子机制决定交易与迈尔森支付"]
    D --> E["递归计算残差收益并反向更新<br/>自底向上计算各层残差收益更新 Hedge 权重"]
    E --> F["输出：获得利润并保证全时程紧致遗憾"]

关键设计¶

1. 网格机制的平滑期望 $L^1$ 连续性近似：克服不连续性与无界维度的理论基石 在标准对抗预测中，算法链式法则依赖于假设类的确定性 $L^\infty$-net 保证。然而在双边贸易中，由于收益函数在分配区域边界处的跃变，确定性 $L^\infty$ 甚至有限样本 $L^p$ 网格均无法达成次指数规模（fat-shattering 维度无穷）。本文证明在 $\sigma$-平滑连续密度下，通过内逼近算子 $\phi_\varepsilon(M)$（仅保留完全落在原分配区域 $A_M$ 内的网格方块）可建立严格的期望误差上界： $$\mathbb{E}_{v \sim \mathcal{D}}\left[\left|\text{profit}(M,v) - \text{profit}(\phi_\varepsilon(M),v)\right|\right] \le 6 \cdot \frac{\varepsilon}{\sigma}$$ 该机制的突破性在于将误差精细分解为两部分：第一部分为边界非完全覆盖方块 $A_M \setminus A_\varepsilon$，这类方块至多有 $2/\varepsilon$ 个且面积均为 $\varepsilon^2$，由平滑性其发生概率不超过 $2\varepsilon/\sigma$；第二部分为内部区域 $A_\varepsilon$ 的迈尔森支付偏差，通过将单位正方形切分为行与列，证明买家与卖家支付截断误差的列向/行向总变差均被常数 2 严格限制（$\sum_c \Delta_c \le 2, \sum_r \Delta_r \le 2$），由此首次在非参数化机制空间建立了与网格尺度 $\varepsilon$ 呈一阶线性的平滑连续性保证。

2. 机制树上的局部专家分解与尺度自适应学习率：解决组合爆炸与方差权衡 若直接将细粒度网格机制 $\mathcal{M}_H$ 作为无差别专家池，基数 $|\mathcal{M}_H| \approx (2e)^{2^H}$ 会引入 $\sqrt{T \cdot 2^H}$ 的灾难性遗憾；若步长过粗则离散化偏差过大。本文在机制树 $\mathcal{T}$ 的每个内部节点 $M \in \mathcal{M}_h$ 单独维护一个局部 Hedge 算法 $\mathcal{H}^h(M)$，其动作空间仅为其直接子节点集合 $\mathcal{N}_M \subseteq \mathcal{M}_{h+1}$。更为关键的是，设计了层级相关的自适应学习率： $$\eta_h = \frac{2^h}{\sqrt{T}}$$ 这种配置实现了极致的方差均衡：随着层级 $h$ 增加，子节点分支数上界以 $2^{2^{h+1}}$ 剧烈增长，带来更高的局部探索压力，需要更大的学习率 $\eta_h$ 来惩罚劣势路径；与此同时，由设计 1 可知，更深层级处的真实残差收益幅度按 $\mathcal{O}(2^{-h}/\sigma)$ 几何衰减。两者精确抵消，使得树上每一层沿最优机制路径的局部遗憾恒定被约束在 $\frac{7}{\sigma}\sqrt{T}$ 以内。

3. 递归端到端目标函数与收益回传机制：消除非平稳环境下的历史偏差 在非平稳平滑对抗环境中，历史表现优异的粗粒度机制未来可能极度劣质，因此无法像 i.i.d. 设定那样进行不可逆的候选修剪。本文引入递归展开的目标函数 $\theta_t(M)$：若 $M$ 为叶子则 $\theta_t(M) = M$；若为内部节点，则递归等于其当前被采样的子节点所继续展开的叶子节点 $\theta_t(\mathcal{H}_t^h(M))$。向局部专家反馈的奖励定义为： $$\Delta_t^h(M') = \frac{1}{2} \cdot \left(\text{profit}_t(\theta_t(M')) - \text{profit}_t(M)\right), \quad \forall M' \in \mathcal{N}_M$$ 该设计实质上测量的是“选择子机制 $M'$ 并遵从其下游子树随机游走”相对于“止步于粗粒度机制 $M$”所带来的边缘增益。由于 $\phi_h(\theta_t(M')) = M$，子树叶子机制与父节点 $M$ 之间的几何差异严格受限于 $2^{-h}$ 分辨率，确保了局部反馈信号的方差严格有界，进而通过数学归纳法完成跨层链式收益望远镜级联（Telescoping Chaining）。

损失函数 / 训练策略¶

算法不需要离线预训练，采用纯在线更新策略。超参数唯一由时间跨度 $T$ 确定： 1. 目标分辨率深度设置为 $H = \frac{1}{2} \lceil \log_2 T \rceil$，保证最细网格尺度满足 $2^{-H} \le \frac{1}{\sqrt{T}}$。 2. 树中每个内部节点 $M \in \mathcal{M}_h$ 维护权重分布 $w_t(M')$，依据指数加权更新： $$w_{t+1}(M') = w_t(M') \cdot \exp\left(\eta_h \cdot \Delta_t^h(M')\right), \quad \pi_t^h(M') = \frac{w_t(M')}{\sum_{M'' \in \mathcal{N}_M} w_t(M'')}$$ 3. 总时程遗憾界严密收敛为： $$R_T(\text{Hier-Mech}) \le \sum_{h=0}^{H-1} \frac{14}{\sigma}\sqrt{T} + \frac{6}{\sigma} 2^{-H} T \le \frac{20}{\sigma} \sqrt{T} \log T$$

实验关键数据¶

主实验¶

由于本工作属于纯理论在线学习与机制设计研究，论文的核心验证体现为严密的理论界限确立与极小化极大收敛速率对比。表 1 汇总了双边贸易与联合广告在不同数据生成模型下的理论遗憾界表现：

问题与环境设定	基准方法 / 机制空间	遗憾上界 (Regret Upper Bound)	遗憾下界 (Regret Lower Bound)	紧致性结论
双边贸易 (i.i.d. 随机环境)	Modified FTL (DiGregorio et al. 2025)	$\tilde{O}(\sqrt{T})$	$\Omega(\sqrt{T})$	速率紧致 (多项式时间)
双边贸易 (任意对抗环境)	任意在线学习算法 (DiGregorio et al. 2025)	无次线性界	$\Omega(T)$	线性下界，不可学习
双边贸易 ($\sigma$-平滑对抗环境)	单层网格 Hedge (朴素覆盖)	$O(\frac{1}{\sigma} T^{2/3})$	$\Omega(\sqrt{T})$	次优，存在 $T^{1/6}$ 鸿沟
双边贸易 ($\sigma$-平滑对抗环境)	Hier-Mech (本文算法)	$\mathbf{O(\frac{1}{\sigma} \sqrt{T} \log T)}$	$\mathbf{\Omega(\sqrt{T})}$	极小化极大紧致 (差对数项)
联合广告 ($\sigma$-平滑对抗环境)	Grid-Experts (Aggarwal et al. 2024)	$O(\frac{1}{\sigma} T^{2/3})$	$\Omega(\sqrt{T})$	次优界
联合广告 ($\sigma$-平滑对抗环境)	Hier-Mech + 双向规约 (本文)	$\mathbf{O(\frac{1}{\sigma} \sqrt{T} \log T)}$	$\mathbf{\Omega(\sqrt{T})}$	解决公开猜想，达到紧致

消融实验¶

为定量剖析分层结构与平滑连续性在整体收敛速率中的理论贡献，表 2 总结了关键模块对双边贸易学习遗憾阶数的理论消融分析：

算法架构配置	空间基数 / 局部探索代价	近似偏差 / 累积残差	最终理论遗憾阶数 $R_T$	理论失效 / 退化根因
纯网格离散化 (平坦 Hedge, $\varepsilon = T^{-1/3}$)	$	\mathcal{M}_\varepsilon	\approx (2e)^{T^{1/3}}$	离散化偏差 $O(T^{2/3}/\sigma)$
单层超细网格 (平坦 Hedge, $\varepsilon = T^{-1/2}$)	$	\mathcal{M}_\varepsilon	\approx (2e)^{\sqrt{T}}$	偏差 $O(\sqrt{T}/\sigma)$
分层结构 w/o 自适应步长 ($\eta_h = 1/\sqrt{T}$)	各层分支 $\le (2e)^{2^{h+1}}$	逐层残差 $O(2^{-h}/\sigma)$	$O(\frac{1}{\sigma} \sqrt{T} \cdot 2^{H/2})$	高层探索不足，低层残差未能精准对消
分层结构 w/o 平滑假设 ($\sigma \to 0$ 任意对抗)	保持分层树结构	确定性 $L^1$ 误差退化为常数	$\Omega(T)$	收益函数跳变导致残差下界为常数
Hier-Mech 完整设计 (三模块协同)	局部有效动作集精简	一阶平滑连续性 $\le 6\varepsilon/\sigma$	$\mathbf{\frac{20}{\sigma} \sqrt{T} \log T}$	局部遗憾均一化 ($\frac{7}{\sigma}\sqrt{T}$)，链式完美望远镜对消

关键发现¶

算法链式法则与平滑性的深度结合，首次证明了在非平稳对抗环境下，非参数化机制空间的学习难度在信息论意义上与 i.i.d. 随机环境完全等价（同为 $\tilde{O}(\sqrt{T})$），成功跨越了此前任意对抗下 $\Omega(T)$ 的不可能界限。
自适应步长 $\eta_h = 2^h/\sqrt{T}$ 是抹平层级几何复杂度的核心数学杠杆：它将各层的局部遗憾严格均衡为常数阶 $\frac{7}{\sigma}\sqrt{T}$，避免了误差在树深方向上的乘性级联放大。
双边贸易与联合广告之间存在严格的几何对偶：通过仿射变换 $f(x,y) = (\frac{1-x}{2}, \frac{1+y}{2})$，将联合广告的东北单调区与双边贸易西北单调区建立等度量连接，不仅顺带解决了联合广告领域的遗留猜想，也确立了双边贸易的 $\Omega(\sqrt{T})$ 下界。

亮点与洞察¶

将算法链式法则成功引入经济学非参数机制设计：传统算法链式法则仅用于凸回归或有界标量函数，本文利用迈尔森投影的几何变差有界性，在无界 fat-shattering 维度的非参数化空间中首次实现了基于平滑分布的链式分解。
巧用一维单调投影的总变差有界性克服二维积分维数灾难：在引理 2 的证明中，没有陷入复杂的二维积分几何，而是巧妙地将买家支付和卖家支付沿行列投影降维，借助迈尔森支付函数的单调阶梯性质将总偏差上界压至常数 2。
普适的机制对偶规约框架：建立的双向规约不仅证明了双边贸易中负利润情形可以通过局部限制映射 $[0, 1/2] \times [1/2, 1]$ 予以免疫，也为其他双边/多边非排他性公共品博弈机制的平滑在线学习提供了通用模板。

局限与展望¶

计算复杂度随时间呈次指数增长：虽然 Hier-Mech 实现了最优的信息论统计速率，但在实际运行中需要维护整棵树上数量达 $\exp(O(\sqrt{T}))$ 个局部专家，与 i.i.d. 设定下的多项式时间算法相比存在计算鸿沟。
遗憾界对平滑参数 $\sigma$ 的一阶反比依赖可能不是最优：界限中包含 $1/\sigma$ 因子，在极端尖锐的微平滑环境（$\sigma \to 0$）下退化较快，其极小化极大最优的 $\sigma$ 依赖阶数仍属开放性问题。
未来方向：探索是否存在支持经验风险最小化（ERM）预言机的快速近似求解器，从而在保留 $\tilde{O}(\sqrt{T})$ 统计速率的同时，将运行时间缩减为关于 $T$ 的多项式时间。

评分¶

新颖性: ⭐⭐⭐⭐⭐ 首次将算法链式法则拓展至非参数化经济机制设计，突破了传统平滑学习依赖有限 fat-shattering 维度的理论限制。
实验充分度: ⭐⭐⭐⭐⭐ 理论证明完整严密，主定理、局部遗憾引理、期望连续性定理与双向规约构成完整闭环。
写作质量: ⭐⭐⭐⭐⭐ 概念动机清晰，数学符号与几何对应直观，引理与定理推进条理极其分明。
价值: ⭐⭐⭐⭐⭐ 填补了双边贸易与在线机制设计领域从 i.i.d. 到对抗环境的关键空白，为非平稳机制学习提供了奠基性工具。

算法架构配置	空间基数 / 局部探索代价	近似偏差 / 累积残差	最终理论遗憾阶数 \(R_T\)	理论失效 / 退化根因
纯网格离散化 (平坦 Hedge, \(\varepsilon = T^{-1/3}\))	$	\mathcal{M}_\varepsilon	\approx (2e)^{T^{1/3}}$	离散化偏差 \(O(T^{2/3}/\sigma)\)
单层超细网格 (平坦 Hedge, \(\varepsilon = T^{-1/2}\))	$	\mathcal{M}_\varepsilon	\approx (2e)^{\sqrt{T}}$	偏差 \(O(\sqrt{T}/\sigma)\)
分层结构 w/o 自适应步长 (\(\eta_h = 1/\sqrt{T}\))	各层分支 \(\le (2e)^{2^{h+1}}\)	逐层残差 \(O(2^{-h}/\sigma)\)	\(O(\frac{1}{\sigma} \sqrt{T} \cdot 2^{H/2})\)	高层探索不足，低层残差未能精准对消
分层结构 w/o 平滑假设 (\(\sigma \to 0\) 任意对抗)	保持分层树结构	确定性 \(L^1\) 误差退化为常数	\(\Omega(T)\)	收益函数跳变导致残差下界为常数
Hier-Mech 完整设计 (三模块协同)	局部有效动作集精简	一阶平滑连续性 \(\le 6\varepsilon/\sigma\)	\(\mathbf{\frac{20}{\sigma} \sqrt{T} \log T}\)	局部遗憾均一化 (\(\frac{7}{\sigma}\sqrt{T}\))，链式完美望远镜对消

问题与环境设定	基准方法 / 机制空间	遗憾上界 (Regret Upper Bound)	遗憾下界 (Regret Lower Bound)	紧致性结论
双边贸易 (i.i.d. 随机环境)	Modified FTL (DiGregorio et al. 2025)	\(\tilde{O}(\sqrt{T})\)	\(\Omega(\sqrt{T})\)	速率紧致 (多项式时间)
双边贸易 (任意对抗环境)	任意在线学习算法 (DiGregorio et al. 2025)	无次线性界	\(\Omega(T)\)	线性下界，不可学习
双边贸易 (\(\sigma\)-平滑对抗环境)	单层网格 Hedge (朴素覆盖)	\(O(\frac{1}{\sigma} T^{2/3})\)	\(\Omega(\sqrt{T})\)	次优，存在 \(T^{1/6}\) 鸿沟
双边贸易 (\(\sigma\)-平滑对抗环境)	Hier-Mech (本文算法)	\(\mathbf{O(\frac{1}{\sigma} \sqrt{T} \log T)}\)	\(\mathbf{\Omega(\sqrt{T})}\)	极小化极大紧致 (差对数项)
联合广告 (\(\sigma\)-平滑对抗环境)	Grid-Experts (Aggarwal et al. 2024)	\(O(\frac{1}{\sigma} T^{2/3})\)	\(\Omega(\sqrt{T})\)	次优界
联合广告 (\(\sigma\)-平滑对抗环境)	Hier-Mech + 双向规约 (本文)	\(\mathbf{O(\frac{1}{\sigma} \sqrt{T} \log T)}\)	\(\mathbf{\Omega(\sqrt{T})}\)	解决公开猜想，达到紧致