One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts

基本信息

• 论文ID: 2511.20110
• 标题: One Action Too Many: Inapproximability of Budgeted Combinatorial Contracts
• 作者: Michal Feldman, Yoav Gal-Tzur, Tomasz Ponitka, Maya Schlesinger (Tel Aviv University)
• 分类: cs.GT (Game Theory)
• 发表时间/会议: ITCS 2026 (预印本版本：2025年11月26日)
• 论文链接: https://arxiv.org/abs/2511.20110

摘要

本文研究带预算约束的多智能体组合行动合约设计问题，针对包括利润、奖励和福利在内的广泛目标函数类。主要结果包括：(1) 强不可近似性：对于次模奖励函数，即使有需求预言机访问，任何随机多项式时间算法都无法在任何有限因子内近似最优预算可行值；(2) 正面结果：对于总替代(gross substitutes)奖励函数（次模函数的严格子类），存在确定性多项式时间O(1)-近似算法，仅需值查询；(3) FPTAS：对于加性奖励函数，在任意预算下都存在FPTAS，这也是多智能体组合行动设置下的首个FPTAS。研究首次明确区分了预算约束与非预算约束设置，并确定了总替代性质作为可处理的边界。

研究背景与动机

1. 研究问题

本文研究多智能体组合行动合约设计问题，核心挑战是：当委托人(principal)面临预算约束时，如何设计激励合约使多个智能体(agents)选择合适的行动组合，以优化委托人的目标（利润、奖励或福利）。

2. 问题重要性

• 理论意义：合约理论是微观经济学的核心领域，2016年诺贝尔经济学奖授予Hart和Hölmstrom表明其重要性
• 实践价值：广泛应用于现代计算市场，如：
  • 初创公司通过股权激励工程师团队
  • 众包平台设计任务奖励机制
  • 项目外包中的合约设计

3. 现有方法的局限性

文献中存在两类正面结果：

• (i) 无预算约束 + 组合行动：DEFK25对次模函数给出常数因子近似
• (ii) 有预算约束 + 二元行动：FGPS25, AHT25对次模函数给出常数因子近似

但两者结合（预算约束 + 组合行动）的可近似性未知。

4. 研究动机

关键观察：二元行动设置中的最佳响应单调性(best-response monotonicity)在组合行动下失效。当智能体可选择行动子集时，其他智能体减少行动可能导致该智能体也减少行动，这一非单调性是复杂性的根源。

核心贡献

1. 不可近似性定理（Theorem 3.1）：
   • 对于次模奖励函数，在任意预算B ∈ (0,1)下，任何随机多项式时间算法（即使有需求预言机访问）都无法在任何有限因子内近似BEST目标
   • 硬度结果是紧的：即使n-1个智能体只有二元行动，剩余1个智能体仅有一个额外行动
2. 总替代函数的常数因子近似（Theorem 4.1 & Corollary 4.2）：
   • 对于总替代奖励函数，存在确定性多项式时间O(1)-近似算法
   • 仅需值查询（不需要需求预言机）
   • 适用于任意预算和所有BEST目标
3. 加性函数的FPTAS（Theorem 5.1）：
   • 对于加性奖励函数，利润、奖励和福利目标均存在FPTAS
   • 这是多智能体组合行动设置下的首个FPTAS（即使在无预算约束情况下）
4. 理论分离：
   • 首次明确区分预算约束与非预算约束设置在组合合约中的复杂性
   • 首次区分次模函数与总替代函数在预算合约中的可近似性

方法详解

任务定义

实例：⟨A, {Ti}i∈A, f, c⟩

• A：n个智能体集合
• Ti：智能体i的可用行动集合，智能体可选择任意子集Si ⊆ Ti
• f: 2^T → 0,1：奖励函数，映射行动组合到成功概率
• c = {cj}j∈T：行动成本向量

合约：α = (α1,...,αn) ∈ 0,1^n，其中αi是项目成功时支付给智能体i的比例

预算约束：∑i∈A αi ≤ B

目标：找到预算可行的合约α和纳什均衡S，最大化目标函数φ(α,S)，其中φ属于BEST目标类：

• 利润：uP(α,S) = (1 - ∑αi)f(S)
• 奖励：f(S)
• 福利：f(S) - c(S)

不可近似性构造（Section 3）

核心思想

构造一个参数化实例族I(A')，其中A' ⊆ n且|A'| = n/2：

智能体设置：

• n个二元行动智能体（行动i或不行动）
• 1个特殊智能体（n+1）有两个行动：G（"好"）和B（"坏"）

奖励函数设计：f^(A')(S) = f1(S) + f2(S) - f3(S,A')，其中：

f1(S) = max(1/2 · 1[G∈S], ε · 1[B∈S])
f2(S) = ε · min(|S\{G}|, n/2+1)
f3(S,A') = (ε/2) · 1[S = {B}∪A']

参数选择：ε < min((1-B)/(K(n)·(n+4)), 4n/B)

关键性质

1. f^(A')是次模的（Lemma 3.4）：通过验证单调性和次模性
2. 需求查询可用值查询模拟（Lemma 3.5）：任何需求查询可用12次值查询计算
3. 存在好均衡（Lemma 3.6）：存在预算可行合约激励A'∪{G}，奖励≥1/2
4. 其他均衡奖励低（Lemma 3.7）：对于S ≠ A'∪{G}的任何预算可行均衡，f(S) ≤ (n/2+2)ε

证明策略

步骤1：证明获得好近似需要激励G

• 包含G的集合：f(S) ≥ 1/2
• 不含G的集合：f(S) ≤ (n/2+2)ε ≈ 0

步骤2：证明激励G需要同时激励恰好A'

• 通过f3项，B的边际奖励在S-{n+1} = A'时降低
• 预算约束使得只有激励正确的n/2个智能体才能激励G

步骤3：信息论下界

• 候选集合A'有(n choose n/2) = 2^Ω(n)个
• 多项式次查询无法以非可忽略概率识别A'
• 使用Yao原理：对均匀分布的A'，任何确定性算法期望性能差

总替代函数的正面结果（Section 4）

关键性质：最佳响应单调性

Lemma 4.3（最佳响应单调性）：对于总替代函数f，如果S是合约α的均衡，对于任意智能体i和S'{-i} ⊆ S{-i}，存在S'_i ⊇ S_i使得S'i是i对S'{-i}的最佳响应。

证明思路：

1. 将最佳响应问题转化为需求束问题
2. 定义价格向量p和q，使得：
   • S_i是对S_{-i}的最佳响应 ⟺ S是关于p的需求束
   • S'i是对S'{-i}的最佳响应 ⟺ S'是关于q的需求束
3. 由于S'{-i} ⊆ S{-i}，有p ≤ q（坐标级）
4. 应用总替代性质：存在需求束S' ⊇ S且S'{-i} = S'{-i}

降维引理（Lemma 4.5）

给定(α,S) ∈ C(B)和参数M ≥ 3，可在多项式时间内找到(α',S') ∈ C(B)使得：

• f(S') ≥ f(S)/(2M-2)
• ∑α'_i ≤ (5/M)∑αi 或 存在i使得α' = α|_i

算法（Algorithm 2）：

1. 识别高支付智能体集合Z = {i: αi > p/M}
2. 如果某个i∈Z单独贡献大，返回单智能体合约
3. 否则，将剩余智能体分组，每组总支付≤p/M
4. 找到奖励足够的组U
5. 应用倍增引理（Lemma 2.2）构造新合约

等价性定理（Theorem 4.1）

分解引理（Lemma 4.8）：

Max-φ(B) ≤ 2·Max-Reward-Bounded(B) + max_i Best-Single_i-φ(B)

归约链：

1. Max-φ(B) → Max-Reward-Bounded(B)（Lemma 4.10）
2. Max-Reward-Bounded(B) → Max-φ(B')（Lemma 4.11）
3. 单智能体问题可精确求解（Lemma 4.9）

加性函数的FPTAS（Section 5）

动态规划方法

离散化：

• 设δ = ε/|T|
• 定义f̃(S) = ∑_{a∈S} ⌊f({a})/(δb)⌋(δb)

DP表定义：

A^(φ)(j,x) = min_{S,α} {∑αi | f̃(S) ≥ x, S ∈ NE(α), S ⊆ T1∪...∪Tj}

关键观察（加性函数）：

• 智能体i的最佳响应是前缀：包含所有满足c_a ≤ αi·f({a})的行动
• DP转移：A^(φ)(j,x) = min_{ℓ} {A(j-1, x-f̃({a1,...,aℓ})) + c_{aℓ}/f({aℓ})}

近似保证：

f̃(S*) ≥ (1-ε)f(S*)

因此返回的合约达到(1-ε)-近似。

实验设置

本文是纯理论论文，不包含实验部分。所有结果均为数学证明。

理论验证方法

1. 构造性证明：通过显式构造硬实例证明不可近似性
2. 算法设计：提供具体算法（Algorithm 1, 2）并证明性能保证
3. 复杂性分析：分析算法的时间复杂性和查询复杂性

实验结果

不适用（纯理论工作）

相关工作

1. 组合合约（Combinatorial Contracts）

二元行动模型：

• BFN06a, BFNW12：引入组合智能体模型
• DEFK23：XOS函数的常数因子近似
• FGPS25, AHT25：预算约束下的二元行动

组合行动模型：

• DEFK21：单智能体组合行动，总替代函数可处理
• DEFK25：多智能体组合行动，次模函数O(1)-近似（无预算）

2. 线性合约（Linear Contracts）

• Car15：线性合约的鲁棒性
• DRT19：线性合约的近似保证
• DFPS24：歧义性证明

3. 预算约束下的合约

• HG24：独立任务的预算约束
• DASSTC25：智能体预算约束
• FGPS25：BEST目标的等价性

4. 本文相对优势

结论与讨论

主要结论

1. 三维障碍：不可近似性仅在三个属性同时存在时出现：
   • 次模奖励函数
   • 预算约束
   • 组合行动 任意两个属性的组合都允许常数因子近似（Figure 1）
2. 总替代边界：总替代性质是预算组合合约的可处理边界
3. 加性函数特殊性：完全多项式时间近似方案存在

局限性

1. 不可近似性的紧性：
   • 仅需n-1个二元智能体 + 1个有3个行动的智能体
   • 但构造高度人工，实际应用中可能不常见
2. 总替代假设：
   • 比次模更强的假设
   • 许多实际应用可能不满足
3. BEST目标限制：
   • FPTAS仅适用于利润、奖励、福利
   • 不适用于所有BEST目标
4. 单一预算：
   • 仅考虑总预算约束
   • 未考虑个体预算约束

未来方向

1. 计算复杂性：
   • 总替代函数下是否存在PTAS/FPTAS？
   • 单智能体问题的精确复杂性
2. 更丰富的模型：
   • 多项目设置ACC+25
   • 公平性约束CCL25b
   • 私有信息ADT21
3. 学习视角：
   • 在线合约设计ZBY+23
   • 样本复杂性DFPS25
4. 实证研究：
   • 实际应用中的函数类特征
   • 启发式算法的性能

深度评价

优点

1. 理论深度：
   • 首次建立预算约束下的不可近似性
   • 紧的硬度结果（最小化硬实例）
   • 完整的复杂性刻画（Figure 1的三角形）
2. 技术创新：
   • 最佳响应非单调性的精确刻画作为硬度来源
   • 巧妙的硬度构造：通过f3项实现"隐藏集合"
   • 总替代函数的最佳响应单调性证明
3. 结果完整性：
   • 负面结果（不可近似性）
   • 正面结果（总替代、加性）
   • 算法和下界的匹配
4. 写作清晰：
   • 动机明确（启动公司例子）
   • 技术路线清晰
   • Figure 1直观展示主要结果

不足

1. 实用性考虑：
   • 硬度构造高度人工
   • 总替代假设在实践中的适用性未讨论
   • 缺乏实际应用案例分析
2. 技术局限：
   • FPTAS仅适用于部分BEST目标
   • 常数因子近似的具体常数未给出
   • 单智能体FPTAS需要需求预言机
3. 理论空白：
   • 总替代与次模之间的中间类？
   • 个体预算约束的复杂性
   • 随机合约的可能性
4. 证明复杂性：
   • 某些证明较技术性（如Lemma 3.7）
   • 需求预言机模拟的必要性不够直观

影响力

理论贡献：

• 首次明确区分预算/非预算设置
• 确立总替代作为可处理边界
• 为后续研究提供基准

方法论价值：

• 最佳响应单调性分析框架
• 降维引理的设计模式
• 硬度构造技术

实用价值：

• 指导合约设计实践：识别可处理情况
• 警示过度简化模型的风险
• 为近似算法设计提供理论界限

适用场景

适合应用：

1. 总替代场景：
   • 技能互补的团队（不同专长）
   • 资源分配问题
   • 市场设计
2. 加性场景：
   • 独立任务的众包
   • 简单激励机制

不适合应用：

1. 强互补性任务（违反总替代）
2. 无预算约束的情况（已有更好算法）
3. 需要精确解的场景

参考文献（关键文献）

1. DEFK25 Dütting et al., "Multi-agent combinatorial contracts", SODA 2025
   • 本文直接扩展的工作
2. FGPS25 Feldman et al., "Budget-feasible contracts", EC 2025
   • 二元行动下的预算合约
3. DEFK21 Dütting et al., "Combinatorial contracts", FOCS 2021
   • 单智能体组合行动基础
4. Car15 Carroll, "Robustness and linear contracts", AER 2015
   • 线性合约理论基础
5. Pae17 Paes Leme, "Gross substitutability: An algorithmic survey", GEB 2017
   • 总替代性质综述

总结

这是一篇理论深度出色的博弈论论文，通过精确刻画预算约束组合合约的复杂性边界，做出了重要的理论贡献。论文的核心洞察是最佳响应非单调性作为复杂性来源，并通过紧的硬度构造和匹配的正面算法完整地刻画了问题的可处理性。总替代性质被确立为预算组合合约的可处理边界，这一发现对后续研究具有指导意义。尽管缺乏实证研究，但其理论价值和方法论贡献使其成为算法合约理论领域的重要工作。