AFTD Auto-Formalizing Theoretical Domains

Research Blogs

两个智能体下 EF1 的代价严格小于二分之一,推翻了一般下界

low tier2026-10-03本文含 2 个研究级成果审阅: Claude CodeEnglish

摘要

至多一个杂务的无嫉妒(EF1)的代价衡量了在固定智能体数量的归一化实例上,EF1 分配可达到的最小社会成本与无约束最优社会成本之间的最坏情况加性差距。在不可分杂务公平分配的文献中,arXiv:2410.15738 v1 的定理 7 声称,对于任意智能体数量 $n \ge 1$,EF1 的代价至多为 $1$ 且至少为 $1 - 1/n$。本文介绍了对该下界的形式化推翻。当在 $n = 2$ 处求值时,所声称的下界要求 EF1 的代价至少为 $1 - 1/2 = 1/2$。然而,对于两个智能体,EF1 的代价由 $3 - 2\sqrt{2}$ 从上方界定,由于 $3 - 2\sqrt{2} \approx 0.1716$,这一数值严格小于 $1/2$。该下界在 $n = 2$ 处的失效源于 arXiv:2410.15738 v1 中的基础下界构造,该构造要求在索引为 $1, 3, \ldots, n$ 的智能体之间建立 EF1 条件,这一设定必然需要至少三个智能体,因而在 $n = 2$ 时无法实施。因此,关于对每个 $n \ge 1$ 都有 EF1 的代价至少为 $1 - 1/n$ 的全称断言是错误的。所有引理和推翻定理均已在 Lean 4 中得到验证。

1. 引言

公平分配问题关注在有限智能体群体之间以兼顾公平性标准与经济效率的方式划分一组物品。当物品为杂务——即智能体试图最小化而非最大化的不可心任务——时,分配必须妥善管理置于每位参与者身上的负担。与可分资源不同,杂务的不可分性通常阻碍了精确无嫉妒性的实现,即没有智能体偏好其他智能体的物品包胜过自己的物品包。为了适应不可分性,松弛的公平概念已成为标准,其中最突出的便是至多一个杂务的无嫉妒(EF1)。在 EF1 下,一个智能体可能会嫉妒另一个智能体,但如果从被嫉妒者的物品包中概念性地消除单个杂务,这种嫉妒就必须消失。

尽管公平分配概念保证了公平性的底线,但施加此类约束往往以牺牲整体社会福利为代价。杂务分配的效率通常由其社会成本来衡量,社会成本定义为该分配下各智能体所承担的所有个体成本之和。无约束社会最优在所有可能分配中最小化该和,而最优 EF1 分配则在满足 EF1 的约束下最小化社会成本。因公平性要求导致的效率损失——通常作为公平价格或公平代价来研究——量化了当局限于公平分配时社会成本必须高出多少。

在论文《A Fair Allocation is Approximately Optimal for Indivisible Chores, or Is It?》(arXiv:2410.15738 v1)中,这种效率损失被形式化为 EF1 的代价(该工作的定义 4)。对于一个包含 $n$ 个智能体和 $m$ 件不可分杂务、且智能体估值由成本矩阵给出的实例,EF1 的代价考量了 EF1 分配所达到的最小社会成本与无约束最优社会成本之间的加性差值。为了确保在不同整体规模的实例之间进行有意义的比较,该定义取这一差值在所有归一化杂务实例上的上确界。在 arXiv:2410.15738 v1 中,定理 7 对该量同时声称了一个上界和一个下界:具体而言,它断言对于每个整数 $n \ge 1$,EF1 的代价至多为 $1$ 且至少为 $1 - 1/n$。

根据相关资料,该发表的论断对所有 $n \ge 1$ 声称了一个全称下界 $1 - 1/n$。对于单智能体情形 $n = 1$,该下界给出 $1 - 1/1 = 0$,这是显然满足的,因为给单个智能体的任何分配都显然是 EF1 的且是无约束最优的,使得成本差为零。对于 $n = 2$,定理 7 的界断言 EF1 的代价必须至少为 $1 - 1/2 = 1/2$。arXiv:2410.15738 v1 中给出的定理 7 的证明试图通过描述一族旨在迫使 EF1 分配与社会最优之间产生加性差距的归一化杂务实例来证明该下界。

本文报告了在 Lean 4 证明助手内验证的对定理 7 下界的形式化推翻。具体而言,资料表明两个智能体下 EF1 的代价至多为 $3 - 2\sqrt{2}$。由于 $3 - 2\sqrt{2} \approx 0.1716$,严格小于 $1/2$,因此 $n = 2$ 时 EF1 的实际代价无法达到所声称的阈值 $1/2$。因此,关于对每个 $n \ge 1$ 都有 EF1 的代价至少为 $1 - 1/n$ 的全称断言是错误的。

资料指出了 arXiv:2410.15738 v1 中下界论证失效的确切结构性关键点:该论文中的下界构造要求在索引为 $1, 3, \ldots, n$ 的智能体之间强制满足 EF1 条件。该构造需要存在一个不同于智能体 1 和智能体 2 的第三个智能体(智能体 3),因此无法在仅有两个智能体的实例中实施。下文将给出形式化定义、在 Lean 4 中验证的命题,以及确立该反例并证伪所发表断言的完整证明。

2. 预备知识

定义 1(智能体、杂务与成本矩阵)。设 $n$ 和 $m$ 为自然数,分别表示智能体数量和杂务数量。智能体集合被建模为有限类型 $\text{Fin } n = \{0, 1, \dots, n-1\}$,杂务集合被建模为 $\text{Fin } m = \{0, 1, \dots, m-1\}$。杂务成本配置由函数 $c : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$ 给出,其中 $c(i, j)$ 表示智能体 $i$ 在被分配杂务 $j$ 时所承担的成本(或负效用)。

定义 2(分配与社会成本)。$m$ 件杂务在 $n$ 个智能体之间的一个分配是杂务集合到 $n$ 个不相交物品包的一个划分 $A = (A_0, A_1, \dots, A_{n-1})$,其中 $A_i \subseteq \text{Fin } m$,$\bigcup_{i=0}^{n-1} A_i = \text{Fin } m$,且当 $i \ne i'$ 时 $A_i \cap A_{i'} = \emptyset$。对于智能体 $i$,在物品包 $A_i$ 下承担的总成本为 $c_i(A_i) = \sum_{j \in A_i} c(i, j)$。分配 $A$ 的社会成本记为 $SC(A)$,是所有智能体成本的总和: $$SC(A) = \sum_{i=0}^{n-1} c_i(A_i) = \sum_{i=0}^{n-1} \sum_{j \in A_i} c(i, j).$$ 该实例的无约束最优社会成本记为 $OPT(I)$,是所有有效分配上的最小社会成本: $$OPT(I) = \min_{A} SC(A).$$

定义 3(至多一个杂务的无嫉妒,EF1)。在杂务划分设定中,如果对于每对智能体 $i, k \in \text{Fin } n$,从智能体 $i$ 自身的物品包或智能体 $k$ 的物品包中移除某个杂务后,智能体 $i$ 都不嫉妒智能体 $k$(具体而言,存在某个杂务 $j \in A_i$ 使得 $c_i(A_i \setminus \{j\}) \le c_i(A_k)$,或者智能体 $i$ 已经满足 $c_i(A_i) \le c_i(A_k)$),则分配 $A = (A_0, \dots, A_{n-1})$ 是至多一个杂务的无嫉妒(EF1)的。最优 EF1 社会成本记为 $\text{opt\_ef1\_social\_cost}(c)$,是满足 EF1 的所有分配中的下确界社会成本: $$\min_{A \in EF1(I)} SC(A).$$

定义 4(归一化杂务实例)。如果成本矩阵 $c : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$ 满足 arXiv:2410.15738 v1 的定义 4 中指定的归一化条件,标准化个体估值以使得在不同规模和成本的实例之间进行有意义的加性比较成为可能,则该成本矩阵是一个归一化杂务实例。

定义 5(EF1 的代价,cost_of_ef1)。对于固定的智能体数量 $n \in \mathbb{N}$,EF1 的代价记为 cost_of_ef1,定义为在具有 $n$ 个智能体和任意杂务数量 $m \in \mathbb{N}$ 的所有归一化杂务实例上,最优 EF1 社会成本与无约束最优社会成本之间的加性差值的上确界: $$\text{cost\_of\_ef1}(n) = \sup \left\{ d \in \mathbb{R} \;\middle|\; \exists m \in \mathbb{N}, \, \exists c : \text{Fin } n \to \text{Fin } m \to \mathbb{R}, \, c \text{ is normalized} \wedge d = \min_{A \in EF1(c)} SC(A) - \min_A SC(A) \right\}.$$ 在 Lean 4 中,这使用实数集合上的条件上确界 sSup 进行形式化。

关于定义与形式化选择的注记:

  • 表示智能体数量的参数 $n$ 在每次求值 cost_of_ef1 时是固定的,而杂务数量 $m$ 则在存在量化中遍历所有自然数。
  • 所评估的成本度量是加性的而非乘性的:它衡量的是最优 EF1 社会成本与无约束最优社会成本之间的最坏情况绝对差距,而不是近似比。
  • 实数集合上的条件上确界 sSup 在 Lean 中是不可计算的;按照约定,空实数集合的上确界为 $0$,不过在此处对于每个 $n \ge 1$ 都存在有效的归一化杂务实例。
  • 分配将杂务划分给各个智能体,允许出现智能体承担成本为 $0$ 的空物品包,且 EF1 条件使用弱不等式表达。

3. 主要结果

主定理(not_forall_cost_of_ef1_ge_one_sub_inv)。对于每个正整数 $n \ge 1$,$n$ 个智能体的 EF1 的代价有下界 $1 - 1/n$ 这一论断是错误的。形式化为: $$\neg \left( \forall n \in \mathbb{N}, \; 1 \le n \implies 1 - \frac{1}{n} \le \text{cost\_of\_ef1}(n) \right).$$

not_forall_cost_of_ef1_ge_one_sub_inv 的 Lean 语句通过否定带有假设 $1 \le n$ 的自然数 $n$ 上的全称量化,在项 $1 - 1 / (n : \mathbb{R})$ 中将 $n$ 强制转换为实数,并将其与作用于 $n$ 的 cost_of_ef1 进行比较,从而形式化了这一断言。

进一步结果的补充:

对全称命题的推翻是通过分析具体的双智能体情形 $n = 2$ 建立的,这由进一步的定理 cost_of_ef1_two_lt_one_sub_inv 提供。

定理(cost_of_ef1_two_lt_one_sub_inv)。两个智能体下 EF1 的代价严格小于 $1 - 1/2 = 1/2$: $$\text{cost\_of\_ef1}(2) < 1 - \frac{1}{2}.$$

尽管 not_forall_cost_of_ef1_ge_one_sub_inv 给出了对 arXiv:2410.15738 v1 定理 7 中所作全称断言的逻辑推翻,但 cost_of_ef1_two_lt_one_sub_inv 提供了具体的定量违反。它证明了双智能体设定构成了一个明确的反例:定理 7 声称在 $n = 2$ 时下界为 $1 - 1/2 = 0.5$,而 cost_of_ef1 在 $n = 2$ 处的实际值严格小于 $0.5$。

定理 not_forall_cost_of_ef1_ge_one_sub_inv (Lean 4 已验证)
theorem not_forall_cost_of_ef1_ge_one_sub_inv :
    ¬ ∀ n : ℕ, 1 ≤ n → 1 - 1 / (n : ℝ) ≤ cost_of_ef1 n

4. 证明

证明的总体策略是为两个智能体下的 cost_of_ef1 建立一个严格小于 $1/2$ 的上界。arXiv:2410.15738 v1 中定理 7 的断言声称,对于所有 $n \ge 1$,EF1 的代价至少为 $1 - 1/n$。对于 $n = 2$,该下界要求 EF1 的代价至少为 $1 - 1/2 = 1/2 = 0.5$。为了推翻这一断言,无需计算 cost_of_ef1 在 $n = 2$ 处的精确值;只需给出 cost_of_ef1 在 $n = 2$ 处一个严格低于 $1/2$ 的严格上界即可。该上界由代数量 $3 - 2\sqrt{2}$ 给出。

该论证依赖于两个基础引理:

引理 1(cost_of_ef1_two_le)。两个智能体下 EF1 的代价至多为 $3 - 2\sqrt{2}$: $$\text{cost\_of\_ef1}(2) \le 3 - 2\sqrt{2}.$$

定理 cost_of_ef1_two_le 在具有 $n = 2$ 个智能体的所有归一化杂务实例上,为最优 EF1 社会成本与无约束最优社会成本之间的上确界差值确立了一个上界。常数 $3 - 2\sqrt{2}$ 来自 $(\sqrt{2} - 1)^2$。展开此表达式可验证该恒等式: $$(\sqrt{2} - 1)^2 = (\sqrt{2})^2 - 2\sqrt{2} + 1^2 = 2 - 2\sqrt{2} + 1 = 3 - 2\sqrt{2}.$$ 在数值上,由于 $\sqrt{2} \approx 1.41421356$,我们有 $2\sqrt{2} \approx 2.82842712$,因此: $$3 - 2\sqrt{2} \approx 3 - 2.82842712 = 0.17157288.$$ 因此,对于任意具有两个智能体的归一化杂务实例,最优 EF1 分配使社会成本超出无约束最优的部分至多约为 $0.1716$。

引理 2(ef1cost_alpha_lt_half)。实常数 $3 - 2\sqrt{2}$ 严格小于 $1/2$: $$3 - 2\sqrt{2} < \frac{1}{2}.$$

引理 2 的证明。 我们在实数有序域上通过标准算术来验证该不等式。考虑 $1/2$ 与 $3 - 2\sqrt{2}$ 之间的差值: $$\frac{1}{2} - (3 - 2\sqrt{2}) = 2\sqrt{2} - \left(3 - \frac{1}{2}\right) = 2\sqrt{2} - \frac{5}{2}.$$ 为证明该差值严格为正,等价于证明 $2\sqrt{2} > 5/2$。因为 $2\sqrt{2}$ 和 $5/2$ 均为正实数,所以该不等式等价于比较它们的平方: $$(2\sqrt{2})^2 > \left(\frac{5}{2}\right)^2.$$ 我们直接计算各个平方项: $$(2\sqrt{2})^2 = 2^2 \times (\sqrt{2})^2 = 4 \times 2 = 8 = \frac{32}{4},$$ $$\left(\frac{5}{2}\right)^2 = \frac{5^2}{2^2} = \frac{25}{4} = 6.25.$$ 比较这两个分数: $$\frac{32}{4} > \frac{25}{4} \iff 32 > 25.$$ 由于 $32 > 25$ 为真,取正平方根得到 $2\sqrt{2} > 5/2 = 2.5$。重排各项可得: $$3 - 2\sqrt{2} < 3 - 2.5 = 0.5 = \frac{1}{2}.$$ 在数值上,$1/2$ 与 $3 - 2\sqrt{2}$ 之间的差距为: $$\frac{1}{2} - (3 - 2\sqrt{2}) \approx 0.5 - 0.17157288 = 0.32842712 > 0.$$ 在 Lean 中,该代数不等式被验证为 ef1cost_alpha_lt_half。

结合引理以证明 cost_of_ef1_two_lt_one_sub_inv:

定理 cost_of_ef1_two_lt_one_sub_inv 断言两个智能体下 EF1 的代价严格小于 $1 - 1/2$。证明通过结合引理 1 和引理 2 进行。由 cost_of_ef1_two_le,我们有: $$\text{cost\_of\_ef1}(2) \le 3 - 2\sqrt{2}.$$ 由 ef1cost_alpha_lt_half,我们有: $$3 - 2\sqrt{2} < \frac{1}{2}.$$ 实数有序域中弱不等式与严格不等式的传递性给出: $$\text{cost\_of\_ef1}(2) \le 3 - 2\sqrt{2} < \frac{1}{2} = 1 - \frac{1}{2}.$$ 在 Lean 中,证明脚本直接实现了这一推理: - 首先,步骤 have := cost_of_ef1_two_le 将两个智能体的上界引入上下文中。 - 接下来,步骤 have h := ef1cost_alpha_lt_half 引入比较 $3 - 2\sqrt{2}$ 与 $1/2$ 的严格不等式。 - 然后,push_cast 化简算术项 $1 - 1 / (2 : \mathbb{N})$,将自然数 2 强制转换为实数,使得除法作为实数分数求值。 - 最后,线性算术策略 linarith 结合这些不等式以闭合目标。

主定理(not_forall_cost_of_ef1_ge_one_sub_inv)的证明:

主定理断言对“对于每个 $n \ge 1$,EF1 的代价至少为 $1 - 1/n$”这一全称命题的否定。证明采用反证法: - 假设全称假设: $$h : \forall n \in \mathbb{N}, \; 1 \le n \implies 1 - \frac{1}{n} \le \text{cost\_of\_ef1}(n).$$ - 将该假设特化至 $n = 2$ 的情形。该假设需要前件 $1 \le 2$,这显然成立(在 Lean 中由 norm_num 解决)。该特化给出: $$1 - \frac{1}{2} \le \text{cost\_of\_ef1}(2).$$ 计算 $1 - 1/2$ 得到 $1/2 \le \text{cost\_of\_ef1}(2)$。 - 另一方面,定理 cost_of_ef1_two_lt_one_sub_inv 确立了: $$\text{cost\_of\_ef1}(2) < 1 - \frac{1}{2} = \frac{1}{2}.$$ - $1/2 \le \text{cost\_of\_ef1}(2)$ 与 $\text{cost\_of\_ef1}(2) < 1/2$ 的合取在实数中是矛盾的。在 Lean 中,intro h 引入全称假设,have := h 2 (by norm_num) 将不等式实例化到 2,have := cost_of_ef1_two_lt_one_sub_inv 引入反例,而 linarith 则通过反证法完成证明。

已发表证明中失效的结构性分析:

arXiv:2410.15738 v1 的定理 7 在 $n = 2$ 处的失效源自其下界构造的结构。arXiv:2410.15738 v1 中的论证试图构造一个归一化杂务实例,使得满足 EF1 的任何分配都必须比最优分配承受至少 $1 - 1/n$ 的加性社会成本增加。在该构造中,EF1 约束专门在索引为 $1, 3, \ldots, n$ 的智能体之间进行评估。

这种设定从根本上预设了索引为 3 的智能体的存在。在仅有两个智能体($n = 2$)的实例中,智能体集合仅由智能体 1 和智能体 2 组成。因为智能体 3 并不存在,所需的嫉妒关系和物品包分配无法被构造出来。没有第三个智能体,公平与效率之间被迫产生的权衡便不复存在,从而允许存在一个其社会成本超出最优至多 $3 - 2\sqrt{2} \approx 0.1716$ 的 EF1 分配,远低于所声称的 $0.5$ 下界。

5. 讨论

此处验证的结果通过形式化地证明其错误,解决了 arXiv:2410.15738 v1 定理 7 中所主张下界的状态。定理 7 声称对于每个正整数 $n \ge 1$,EF1 的代价满足 $\text{cost\_of\_ef1}(n) \ge 1 - 1/n$。具体情形 $n = 2$ 推翻了该全称断言:在 $n = 2$ 处求值的量 cost_of_ef1 严格受上界 $3 - 2\sqrt{2} \approx 0.1716$ 界定,该值严格小于 $1 - 1/2 = 0.5$。

同时也有必要详细说明此推翻涵盖了哪些内容、未涵盖哪些内容。首先,arXiv:2410.15738 v1 的定理 7 还断言了一个上界:对于所有 $n \ge 1$,EF1 的代价至多为 $1$。此处讨论的结果并不与该上界相矛盾。事实上,对于两个智能体,界 cost_of_ef1_two_le 证明了 $\text{cost\_of\_ef1}(2) \le 3 - 2\sqrt{2}$,这大幅小于 $1$,与所声称的上界完全一致。

此外,该推翻专门针对双智能体设定。对于 $n = 1$,量 $1 - 1/n$ 求值为 $0$。在任何单智能体杂务分配问题中,唯一的分配将所有杂务都分给该智能体;该分配显然满足 EF1,并且显然达到最优社会成本,因此加性成本差为零,满足 $0 \ge 1 - 1/1$。对于 $n \ge 3$,资料中指出的结构性问题——即下界构造要求在智能体 $1, 3, \ldots, n$ 之间建立 EF1,因而需要第三个智能体——并不会自动使该构造失效。对于三个或更多智能体,智能体 3 是存在的。因此,资料对下界 $\text{cost\_of\_ef1}(n) \ge 1 - 1/n$ 是否对所有 $n \ge 3$ 成立,或者该论证是否可以被修复以确立针对更大 $n$ 值的该界或修正后的界,保持开放。

最后,关于双智能体设定本身,上界 cost_of_ef1_two_le 保证了 $n = 2$ 处的 cost_of_ef1 不能超过 $3 - 2\sqrt{2}$。资料并未确定该上界是否紧确——也就是说,在所有归一化双智能体杂务实例上的上确界是恰好为 $3 - 2\sqrt{2}$,还是严格更小。确定两个智能体下 cost_of_ef1 的精确值,以及明确 $n \ge 3$ 时 EF1 的确切代价,仍然是由此结果引发的主要未决问题。

为什么是研究级成果

  • shows a published claim false (A Fair Allocation is Approximately Optimal for Indivisible Chores, or Is It?, arXiv:2410.15738 v1, Theorem 7 ('the cost of EF1 is at most 1 and at least 1 - 1/n'): false at n = 2, where the cost is at most 3 - 2 sqrt 2 < 1/2; the lower-bound construction needs EF1 among agents 1, 3, ..., n and so a third agent)
  • shows a published claim false (A Fair Allocation is Approximately Optimal for Indivisible Chores, or Is It?, arXiv:2410.15738 v1, Theorem 7 ('the cost of EF1 is at most 1 and at least 1 - 1/n'): false at n = 2, where the cost is at most 3 - 2 sqrt 2 < 1/2; the lower-bound construction needs EF1 among agents 1, 3, ..., n and so a third agent)

Lean 声明

Each one elaborated against Mathlib, and #print axioms returned nothing outside Classical.choice · Quot.sound · propext.

参考文献

  1. arXiv:2410.15738

由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。