在保持物品包完整的同时通过两个具有任意内部排序的全局较小物品扩展完全EFX分配
low tier2026-11-01OP-7审阅: Claude CodeEnglish
摘要
在离散公平分配中,对于具有可加效用的四名或更多主体,是否存在至多任一物品的无嫉妒(EFX)分配仍然是一个未决问题。尽管现有文献提供了插入单个全局最小物品的技术,但当主体对多个物品持有冲突偏好时,通过这些物品扩展分配会带来困难。我们证明,对于具有非负可加效用的 $n$ 名主体间的 $m$ 个不可分物品的任意完全EFX分配,只要每位主体对两个新增物品中每一个的估值都弱小于所有原始 $m$ 个物品,就可以将其扩展为 $m+2$ 个物品的完全EFX分配。各主体无需对这两个新增物品之间的相对排序达成一致。该构造将每个原始物品包作为一个完整单元保留,在主体之间置换这些物品包,并将每个新物品分配给一名主体(两者可能分配给同一主体),从而使每位主体的效用都弱增加。所需置换和接收者对的存在性源于带有两个可加向量红利的实效用矩阵的一个指派原理。迭代该结果可以在任意数量的主体和物品下给出完全EFX分配,只要所有主体对连续物品对的顺序达成一致,而允许在每个物品对内部存在分歧。所有定义、引理和主要扩展定理均已在 Lean 4 中形式化并得到验证。
1. 引言
在一组主体之间公平分配不可分物品是离散公平分配中的经典设定。在可加效用模型中,每位主体 $i \in \{1, \dots, n\}$ 对每个物品 $g$ 赋予一个非负实数值 $v_i(g) \ge 0$,且对子集 $S$ 的估值为 $v_i(S) = \sum_{g \in S} v_i(g)$。分配是一个分配了所有物品的有序划分 $A = (A_1, \dots, A_n)$。消除至多任一物品的无嫉妒(EFX)这一公平性质在 DOI:10.1145/3355902 中被引入:如果对于每一对不同主体 $i \ne j$ 以及每个物品 $g \in A_j$,主体 $i$ 都满足 $v_i(A_i) \ge v_i(A_j \setminus \{g\})$,则该分配是EFX的。在EFX下,假设从另一位主体的物品包中删除任意单个物品后,没有任何主体会嫉妒该物品包。虽然对于不可分物品并不能总是实现完全无嫉妒,但EFX已成为衡量公平性的基准。正如 arXiv:2208.08782(第4.1节,未决问题2)中所综述的,对于具有可加效用的 $n \ge 4$ 名主体是否总是存在完全EFX分配仍然是一个未决问题,其中 $n = 4$ 是最小的未决情形。
先前的研究梳理了EFX存在性在不同参数和效用类别下的图景。对于 $n = 2$ 名主体,通过“我分你选”(cut-and-choose)总是存在EFX分配(arXiv:1707.04769)。对于具有可加效用的 $n = 3$ 名主体,文献('EFX Exists for Three Agents')确立了存在性,并在至少一种效用为可加或最大最小份额(MMS)可行时推广至三名主体。当允许未分配物品时,对于 $n = 4$ 名主体存在至多留下一个未分配物品的EFX分配,且在一般情况下存在至多舍弃 $n - 2$ 个物品的EFX分配。对于受限数量的物品,借助计算机辅助方法也已验证了完全EFX分配的存在性:当 $m \le n + 3$ 时,以及对于 $n = 4$ 当 $m \le 9$ 时。获得积极结果的其他设定包括至多三种效用类型的情形('EFX Exists for Three Types of Agents', EC 2025)、四名主体的松弛版本 EF2X,以及多重图实例上的分配。消极方面,对于具有单调次模效用的三名主体以及具有可加负效用物品(chores)的四名或更多主体,EFX分配可能不存在。目前尚无已知的可加正效用物品反例。
公平分配中的一种标准构造性方法是归纳物品插入。环路消除和公共序插入是标准方法(arXiv:1707.04769v3,引理6.1和附录B):在消除嫉妒环后,存在某个未被嫉妒的物品包,将一个每位主体对其估值都弱小于每个已分配物品的物品添加到该物品包中,不会破坏EFX性质。当所有主体对物品的排序相同时,从最有价值到最无价值逐个插入物品即可得到完全EFX分配。当主体对两个新物品的比较存在分歧时,该单物品步骤无法连续应用两次:因为对于每位主体而言,第二个物品并不一定弱小于第一个物品。此外,尽管 arXiv:2504.03951 分析了具有 $n + 2$ 个物品的分配,但它并未提供保持现有物品包完整的归纳保持定理。
本文介绍了在 Lean 4 中经过验证的定理 efx_exists_of_two_universal_small_goods_ir,该定理解决了在对内任意排序下两个全局较小物品的插入问题。具体而言,假设 $m$ 个物品已经在 $n$ 名主体之间划分成一个完全EFX分配。假定引入两个新增物品,使得每位主体对这两个物品的估值都弱小于所有原始 $m$ 个物品。两个新物品之间不假定存在公共排序:主体对该物品对的偏好可以是完全任意的。我们证明,存在所有 $m + 2$ 个物品的完全EFX分配,它保持每个原始物品包完整,相对于初始分配弱提高了每位主体的效用,并将每个新物品分配给一名主体(两者可能分配给同一主体)。
2. 预备知识
我们考虑在一个有限主体集之间对一个不可分物品的有限集进行的公平分配。在 Lean 形式化中,对于正整数 $n$,主体由有限类型 $\text{Fin } n = \{0, 1, \dots, n-1\}$ 索引,而对于整数 $m$,物品由 $\text{Fin } m = \{0, 1, \dots, m-1\}$ 索引。估值表示为函数 $u : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$,其中 $u(i, g) \ge 0$ 表示主体 $i$ 从物品 $g$ 获得的效用。
定义 1 (additive_valuation)。给定物品效用函数 $u : \text{Fin } m \to \mathbb{R}$,由 $u$ 诱导的可加估值是将任意物品有限子集 $S \subseteq \text{Fin } m$ 映射为其元素效用之和的函数: $$ \text{additive\_valuation}(u)(S) = \sum_{g \in S} u(g). $$ 当 $S = \emptyset$ 时,空和的值为 $0$。
定义 2 (bundle_of)。分配表示为函数 $\sigma : \text{Fin } m \to \text{Fin } n$,它将每个物品 $g$ 映射到接收它的主体 $\sigma(g)$。对于任意主体 $i \in \text{Fin } n$,在 $\sigma$ 下分配给 $i$ 的物品包是映射到 $i$ 的物品集合: $$ \text{bundle\_of}(\sigma)(i) = \{ g \in \text{Fin } m \mid \sigma(g) = i \}. $$ 在该表示下,每个物品恰好分配给一名主体,确保了分配是完全的,且各个物品包构成物品集合 $\text{Fin } m$ 的一个划分。若某主体未收到任何物品,则物品包可以为空。
定义 3 (is_efx_goods)。给定效用函数组 $u : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$ 和分配 $\sigma : \text{Fin } m \to \text{Fin } n$,若对于每一对满足 $i \ne j$ 的不同主体 $i, j \in \text{Fin } n$,以及对于每个物品 $g \in \text{bundle\_of}(\sigma)(j)$,主体 $i$ 对自身物品包的估值都至少与主体 $j$ 移除 $g$ 后的物品包估值一样大,则该分配是EFX的: $$ \text{is\_efx\_goods}(u, \sigma) \iff \forall i, j \in \text{Fin } n, i \ne j \implies \forall g \in \text{bundle\_of}(\sigma)(j), $$ $$ \text{additive\_valuation}(u(i))(\text{bundle\_of}(\sigma)(j) \setminus \{g\}) \le \text{additive\_valuation}(u(i))(\text{bundle\_of}(\sigma)(i)). $$
关于定义选择的注记: Lean 形式化中 is_efx_goods 的定义包含了离散公平分配中标准的若干具体建模选择:
- 不等式约定:该定义要求弱不等式($\le$)。若 $i$ 的物品包价值至少与 $j$ 去除 $g$ 后的物品包价值相同,则消除了对 $j$ 削减后物品包的嫉妒。
- 零值物品的删除:该条件对每个物品 $g \in \text{bundle\_of}(\sigma)(j)$ 进行全称量化,无论 $u(i, g) > 0$ 还是 $u(i, g) = 0$。在部分文献中,EFX 的表述仅对主体 $i$ 具有正估值的物品进行量化;在此处,零估值物品在被移除时也必须满足该不等式。
- 空物品包:若 $\text{bundle\_of}(\sigma)(j) = \emptyset$,则对 $g \in \emptyset$ 的全称量化显然成立,这意味着没有主体会嫉妒空物品包。
- 类型与索引:在具有 $m + 2$ 个物品的设定中,原始 $m$ 个物品通过类型转换映射嵌入到 $\text{Fin } (m+2)$ 中,而两个新增物品由索引 $m$ 和 $m+1$ 表示。
3. 主要结果
在 Lean 中形式化的主要结果是 efx_exists_of_two_universal_small_goods_ir。它证明了当两个新增物品对所有主体而言都是全局较小时,任意 $m$ 个物品的完全EFX分配都可以扩展为 $m+2$ 个物品的完全EFX分配,且不需要主体对这两个新增物品之间的大小比较达成任何一致。
定理(efx_exists_of_two_universal_small_goods_ir)。 设 $m, n \in \mathbb{N}$ 且 $n > 0$。设 $u : \text{Fin } n \to \text{Fin } (m+2) \to \mathbb{R}$ 为满足对所有 $i \in \text{Fin } n$ 和 $g \in \text{Fin } (m+2)$ 均有 $u(i, g) \ge 0$ 的估值函数组。假定索引为 $m$ 和 $m+1$ 的两个新增物品相对于原始 $m$ 个物品是全局较小的: - 对于每位主体 $i \in \text{Fin } n$ 和每个原始物品 $g \in \text{Fin } m$, $$ u(i, m) \le u(i, g). $$ - 对于每位主体 $i \in \text{Fin } n$ 和每个原始物品 $g \in \text{Fin } m$, $$ u(i, m+1) \le u(i, g). $$ 设 $\sigma : \text{Fin } m \to \text{Fin } n$ 是在受限估值 $g \mapsto u(i, g)$ 下原始 $m$ 个物品的任意完全EFX分配。则存在所有 $m+2$ 个物品的完全分配 $\tau : \text{Fin } (m+2) \to \text{Fin } n$,满足以下三个性质:
1. 完全EFX:$\tau$ 在 $u$ 下是所有 $m+2$ 个物品的EFX分配,即 is_efx_goods u τ。 2. 个人理性(IR):每位主体 $i \in \text{Fin } n$ 获得的效用至少与其在 $\sigma$ 下的原始效用一样大: $$ \text{additive\_valuation}(u(i))(\text{bundle\_of}(\sigma)(i)) \le \text{additive\_valuation}(u(i))(\text{bundle\_of}(\tau)(i)). $$ 3. 保持物品包:在 $\sigma$ 下分配给同一主体的任意两个原始物品,在 $\tau$ 下仍然分配给同一主体: $$ \forall g, h \in \text{Fin } m, \quad \sigma(g) = \sigma(h) \implies \tau(g) = \tau(h). $$
efx_exists_of_two_universal_small_goods_ir 的 Lean 语句直接形式化了这一点:在自然数 $m$ 和 $n$ 以及假设 $0 < n$、效用 $u$ 的非负性、两个较小性假设以及满足 is_efx_goods 的初始分配的量化下,它断言存在满足 is_efx_goods、所有主体效用弱提升以及对所有原始物品保持物品包的扩展分配 $\tau$。
该结果带来的增益: 除了将分配扩展两个物品之外,该定理还给出了以下性质:
- 原始物品包的保持:原始物品包绝不会被拆分或重新整理;它们仅仅通过主体置换在主体之间重新分配。这种保持性使得该扩展能够模块化地应用于任何预先存在的EFX分配。
- 效用弱提升:在引入并分配两个新物品后,没有任何主体的总效用遭受损失。
- 公共对实例的迭代EFX:从空分配出发并逐对应用该定理,作为在 Lean 中同样证明的推论,可以为任意数量的主体 $n \ge 1$ 和任意数量的物品 $m$ 给出完全EFX分配,只要对于每位主体,$\lfloor g/2 \rfloor < \lfloor h/2 \rfloor$ 蕴含 $u(i,h) \le u(i,g)$:即所有主体都认同较早物品对中的每个物品都弱优于较晚物品对中的每个物品,同时允许对每个物品对内部的两个物品进行任意排序。对于奇数 $m$,最后一个块是单个物品,通过单物品步骤添加。
theorem efx_exists_of_two_universal_small_goods_ir {m n : ℕ} (hn : 0 < n) (u : Fin n → Fin (m+2) → ℝ) (hu : ∀ i g, 0 ≤ u i g) (hsmall₀ : ∀ (i : Fin n) (g : Fin m), u i (Fin.last m).castSucc ≤ u i g.castSucc.castSucc) (hsmall₁ : ∀ (i : Fin n) (g : Fin m), u i (Fin.last (m+1)) ≤ u i g.castSucc.castSucc) (σ : Fin m → Fin n) (hσ : is_efx_goods (fun i g => u i g.castSucc.castSucc) σ) : ∃ τ : Fin (m+2) → Fin n, is_efx_goods u τ ∧ (∀ i, additive_valuation (fun g : Fin m => u i g.castSucc.castSucc) (bundle_of σ i) ≤ additive_valuation (u i) (bundle_of τ i)) ∧ (∀ g h : Fin m, σ g = σ h → τ g.castSucc.castSucc = τ h.castSucc.castSucc)
4. 证明
证明思路: 该证明将两个全局较小物品的插入归约到带有两个向量红利的实矩阵上的指派问题。设 $w(i, j) = \text{additive\_valuation}(u(i))(\text{bundle\_of}(\sigma)(j))$ 为现有分配 $\sigma$ 下的估值矩阵,其中行 $i$ 表示主体 $i$ 对这 $n$ 个物品包的估值。设 $a(i) = u(i, m)$ 和 $b(i) = u(i, m+1)$ 表示对两个新物品的估值,它们是非负向量。 我们寻求一个主体置换 $p$(它将现有物品包 $\text{bundle\_of}(\sigma)(p(j))$ 重新指派给主体 $j$)以及物品 $m$ 和 $m+1$ 各自的接收者 $r, s \in \text{Fin } n$(两者可能重合)。在该方案下,从主体 $i$ 的视角来看,主体 $j$ 的新物品包估值为 $$ v_i(\text{bundle\_of}(\tau)(j)) = w(i, p(j)) + [j = r] a(i) + [j = s] b(i) $$ 为了使该分配满足EFX和个人理性:
- 每位主体 $i$ 必须弱偏好其新物品包胜过其旧物品包:$w(i, i) \le v_i(\text{bundle\_of}(\tau)(i))$。
- 若另一主体 $i \ne r$ 嫉妒物品包 $r$,则移除物品 $m$(即减去 $a(i)$)必须消除该嫉妒。
- 若另一主体 $i \ne s$ 嫉妒物品包 $s$,则移除物品 $m+1$(即减去 $b(i)$)必须消除该嫉妒。
- 对于属于物品包 $j$ 的任意原始物品 $g_0 \in \text{Fin } m$,较小性假设保证了 $u(i, g_0) \ge a(i)$(若 $j = r$)以及 $u(i, g_0) \ge b(i)$(若 $j = s$)。因此,移除 $g_0$ 扣除的效用至少与移除红利物品一样多,从而削减后的物品包价值绝不会超过自身估值。
- 若 $j \ne r$ 且 $j \ne s$,则物品包 $j$ 不包含红利,嫉妒消除由 $\sigma$ 的初始EFX性质保证。
矩阵引理 finite_two_bonus_ordered_assignment 保证了满足条件 (1)、(2) 和 (3) 的置换 $p$ 及索引 $r, s$ 的存在性。
支持引理: 该证明依赖于库中的五个引理。
引理 1 (additive_valuation_erase_of_mem)。设 $u : \text{Fin } m \to \mathbb{R}$ 为物品估值函数,$S \subseteq \text{Fin } m$ 为有限子集,且 $g \in S$。则 $$ \text{additive\_valuation}(u)(S \setminus \{g\}) = \text{additive\_valuation}(u)(S) - u(g). $$ Lean 中的证明:利用有限和的消除恒等式将 $S$ 上的求和重写为 $S \setminus \{g\}$ 上的求和加上 $u(g)$,并在两边同时减去 $u(g)$ 即可完成证明。
引理 2 (bundle_of_permute_agents)。设 $\sigma : \text{Fin } m \to \text{Fin } n$ 为分配,且 $p$ 为主体置换($p \in \text{Equiv.Perm}(\text{Fin } n)$)。定义置换后的分配 $\tau_0(g) = p^{-1}(\sigma(g))$。则对于每位主体 $i \in \text{Fin } n$, $$ \text{bundle\_of}(\tau_0)(i) = \text{bundle\_of}(\sigma)(p(i)). $$ Lean 中的证明:根据定义,$\text{bundle\_of}(\tau_0)(i) = \{ g \mid p^{-1}(\sigma(g)) = i \}$。应用置换等价关系 $p^{-1}(x) = i \iff x = p(i)$,过滤条件变为 $\sigma(g) = p(i)$,这正是 $\text{bundle\_of}(\sigma)(p(i))$ 的定义。
引理 3 (additive_valuation_bundle_last_cases)。设 $u : \text{Fin } (m+1) \to \mathbb{R}$,$\sigma : \text{Fin } m \to \text{Fin } n$,以及 $s, j \in \text{Fin } n$。考虑将最后一个元素映射到主体 $s$ 并在原始 $m$ 个元素上限制为 $\sigma$ 的扩展分配。则 $$ \text{additive\_valuation}(u)(\text{bundle\_of}(\text{Fin.lastCases}(s, \sigma))(j)) = \text{additive\_valuation}(u \circ \text{Fin.castSucc})(\text{bundle\_of}(\sigma)(j)) + [s = j] u(\text{Fin.last } m). $$ Lean 中的证明:利用有限和分解以及 Fin.lastCases 的定义,将有限和拆分为 $\text{Fin } m$ 转换后元素上的求和与单个最后元素上的值即可完成证明。
引理 4 (is_efx_goods_all_pairs)。设 $u : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$ 取非负值,且设 $\sigma$ 为EFX分配(is_efx_goods u σ)。则对所有主体 $i, j \in \text{Fin } n$(包括 $i = j$)以及每个 $g \in \text{bundle\_of}(\sigma)(j)$, $$ \text{additive\_valuation}(u(i))(\text{bundle\_of}(\sigma)(j) \setminus \{g\}) \le \text{additive\_valuation}(u(i))(\text{bundle\_of}(\sigma)(i)). $$ Lean 中的证明:当 $i \ne j$ 时,该不等式即为 is_efx_goods 的定义。当 $i = j$ 时,从 $\text{bundle\_of}(\sigma)(i)$ 中消除 $g$ 会减去 $u(i, g) \ge 0$,因此该值只会弱变小,满足不等式。
引理 5 (finite_two_bonus_ordered_assignment)。设 $\alpha$ 为有限、非空、可判定的类型。对于任意实矩阵 $w : \alpha \to \alpha \to \mathbb{R}$ 和非负向量 $a, b : \alpha \to \mathbb{R}$,存在置换 $p \in \text{Equiv.Perm}(\alpha)$ 和两个索引 $r, s \in \alpha$,使得:
1. 对所有 $i \in \alpha$, $$ w(i, i) \le w(i, p(i)) + [i = r] a(i) + [i = s] b(i). $$ 2. 对所有满足 $i \ne r$ 的 $i \in \alpha$, $$ w(i, p(r)) + [r = s] b(i) \le w(i, p(i)) + [i = r] a(i) + [i = s] b(i). $$ 3. 对所有满足 $i \ne s$ 的 $i \in \alpha$, $$ w(i, p(s)) + [s = r] a(i) \le w(i, p(i)) + [i = r] a(i) + [i = s] b(i). $$
Lean 中的证明:考虑仅指派了两个红利之一的状态:置换 $p$、接收者 $r$ 以及 $r$ 持有哪一个红利的选择,使得每位主体相对 $w(i,i)$ 都弱改善,且在 $r$ 的红利下没有任何主体嫉妒旧列 $p(r)$。这样的状态存在(消除嫉妒环,然后将红利给予未被嫉妒的列),Lean 证明选取使自身总效用最大化的状态。若可以将另一个红利给予某主体 $s$ 使得条件 (1)-(3) 成立,则证明完成。否则,在极大状态上的嫉妒环论证表明,除 $r$ 之外的每一列都被嫉妒,且 $r$ 所在的列未被嫉妒,因此 $r$ 所在的列是唯一的源点;并且若 $r$ 改为持有另一个红利,则某主体 $i \ne r$ 将会嫉妒 $r$ 所在的列。随后列交换引理表明,旧列之间的嫉妒环,或者经过 $r$ 所在列且切换红利的环,在保持可行性的同时严格增加了总效用,与极大性矛盾。
整合各步骤完成主证明: efx_exists_of_two_universal_small_goods_ir 的 Lean 证明按以下步骤进行:
步骤 1(设定):由于 $n > 0$,$\text{Fin } n$ 非空。我们将实矩阵实例化为 $w(i, j) = \text{additive\_valuation}(u(i) \circ \text{cast})(\text{bundle\_of}(\sigma)(j))$,向量实例化为 $a(i) = u(i, m)$ 以及 $b(i) = u(i, m+1)$。由于 $u \ge 0$,$a$ 和 $b$ 均为非负向量。
步骤 2(调用引理 5):对 $w, a, b$ 应用 finite_two_bonus_ordered_assignment,得到满足条件 (1)、(2) 和 (3) 的置换 $p$ 以及索引 $r, s \in \text{Fin } n$,在 Lean 证明中分别记为 $h_I$、$h_A$ 和 $h_B$。
步骤 3(构造分配):
- 首先,通过 $\tau_0(g) = p^{-1}(\sigma(g))$ 定义 $\tau_0 : \text{Fin } m \to \text{Fin } n$。
- 其次,通过将物品 $m$ 分配给主体 $r$ 来定义 $\tau_1 : \text{Fin } (m+1) \to \text{Fin } n$:$\tau_1 = \text{Fin.lastCases}(r, \tau_0)$。
- 最后,通过将物品 $m+1$ 分配给主体 $s$ 来定义 $\tau : \text{Fin } (m+2) \to \text{Fin } n$:$\tau = \text{Fin.lastCases}(s, \tau_1)$。
步骤 4(评估物品包):两次应用引理 3 并应用引理 2,对于所有 $i, j \in \text{Fin } n$,我们获得: $$ \text{additive\_valuation}(u(i))(\text{bundle\_of}(\tau)(j)) = w(i, p(j)) + [j = r] a(i) + [j = s] b(i). $$
步骤 5(个人理性):对于每位主体 $i$,引理 5 中的条件 (1) 给出 $$ w(i, i) \le w(i, p(i)) + [i = r] a(i) + [i = s] b(i) = \text{additive\_valuation}(u(i))(\text{bundle\_of}(\tau)(i)). $$
步骤 6(削减界): - 对于 $i \ne r$,由条件 (2) 及物品包估值, $$ \text{additive\_valuation}(u(i))(\text{bundle\_of}(\tau)(r)) - a(i) = w(i, p(r)) + [r = s] b(i) \le \text{additive\_valuation}(u(i))(\text{bundle\_of}(\tau)(i)). $$ - 对于 $i \ne s$,由条件 (3) 及物品包估值, $$ \text{additive\_valuation}(u(i))(\text{bundle\_of}(\tau)(s)) - b(i) = w(i, p(s)) + [s = r] a(i) \le \text{additive\_valuation}(u(i))(\text{bundle\_of}(\tau)(i)). $$
步骤 7(EFX 验证):设 $i, j \in \text{Fin } n$ 且 $i \ne j$,并设 $g \in \text{bundle\_of}(\tau)(j)$。由引理 1,消除 $g$ 后的价值为 $\text{additive\_valuation}(u(i))(\text{bundle\_of}(\tau)(j)) - u(i, g)$。我们对 $g$ 进行分情况讨论:
- 情况 $g = m+1$(最后一个物品):此时 $j = s$。由于 $i \ne j$,故 $i \ne s$。被移除的效用为 $u(i, m+1) = b(i)$。剩余价值由步骤 6 控制界限。
- 情况 $g = m$(倒数第二个物品):此时 $j = r$。由于 $i \ne j$,故 $i \ne r$。被移除的效用为 $u(i, m) = a(i)$。剩余价值由步骤 6 控制界限。
- 情况 $g = g_0$ 为原始物品 $g_0 \in \text{Fin } m$:
- 若 $j = r$,则 $i \ne r$。由假设 $hsmall_0$,$a(i) \le u(i, g_0)$。因此,减去 $u(i, g_0)$ 至少减去了 $a(i)$。由于由步骤 6 移除 $a(i)$ 已能控制物品包界限,故移除 $g_0$ 保持了该不等式。
- 若 $j = s$,则 $i \ne s$。由假设 $hsmall_1$,$b(i) \le u(i, g_0)$。减去 $u(i, g_0)$ 至少减去了 $b(i)$,且步骤 6 控制了剩余价值的界限。
- 若 $j \ne r$ 且 $j \ne s$,则两个红利均未分配给 $j$。$j$ 的物品包仅为 $\text{bundle\_of}(\sigma)(p(j))$。由应用于 $\sigma$ 的引理 4,主体 $i$ 对消除 $g_0$ 后的该物品包的估值至多为 $w(i, i)$。由步骤 5,$w(i, i) \le \text{additive\_valuation}(u(i))(\text{bundle\_of}(\tau)(i))$,完成证明。
步骤 8(保持物品包):对于满足 $\sigma(g) = \sigma(h)$ 的任意原始物品 $g, h \in \text{Fin } m$,有 $\tau(g) = p^{-1}(\sigma(g)) = p^{-1}(\sigma(h)) = \tau(h)$。
5. 讨论
在 efx_exists_of_two_universal_small_goods_ir 中确立的结果扩展了EFX的归纳分配方法,但并未解决 arXiv:2208.08782 中综述的无限制四主体EFX存在性问题。
范围以及与未决问题的关系: 一般性问题探讨的是,对于具有 $n \ge 4$ 名主体和可加物品的每一个实例,无论物品估值具有何种结构,是否都存在EFX分配。此处给出的定理对两个新加入的物品施加了结构性条件:它们必须是全局较小的,即每位主体对这两个物品中每一个的估值都弱小于所有先前已分配的物品。 作为对这一限制的回报,该定理得出了以下结构性质:
- 任意对内排序:与 arXiv:1707.04769v3 附录B 中要求跨物品具有公共排序的基线单物品插入技术不同,此处的两个新增物品在不同主体之间可以具有完全不一致的排序。一名主体可能严格偏好索引为 $m$ 的物品,而另一名主体严格偏好索引为 $m+1$ 的物品。
- 完全保持物品包:在 $\tau$ 下,所有原本分配在一起的原始物品仍然分配在一起。现有的物品包被视为刚性物品,并在主体之间进行置换。arXiv:2504.03951(第3节)中针对 $n+2$ 个物品的计数和存在性结果并不是从具有任意多旧物品的任意EFX分配出发,也没有陈述这种保持性质。
- 弱帕累托改善:随着物品对的添加,每位主体的效用单调弱提升。
在公共对实例上的归纳应用: 作为 efx_exists_of_two_universal_small_goods_ir 的推论,对于具有任意数量主体 $n$ 的一个无限实例族,完全EFX分配均存在:即物品可以划分为若干对 $P_1, P_2, \dots, P_k$,使得所有主体都认同 $P_t$ 中的每个物品都弱优于 $P_{t+1}$ 中的每个物品,即便主体对每个物品对 $P_t$ 内部的两个物品的排序可能完全相反。从空分配(显然是EFX的)出发,对 $t = 1, \dots, k$ 反复应用该定理,即可构造所有 $2k$ 个物品的完全EFX分配;当物品数量为奇数时,最后一个块为单个物品,通过单物品步骤完成。该推论在 Lean 中同样得到了证明。它涵盖了完全相同排序的情形(即完全不允许存在分歧的情形)。
开放方向: 基于该形式化提出了几个直接的问题:
- 更大的较小物品包:该结果能否从一对全局较小物品推广到三元组,或者推广到具有任意内部偏好分布的 $k \ge 3$ 个全局较小物品的集合?一个自然的问题是
finite_two_bonus_ordered_assignment的类似结论对于 $k \ge 3$ 个向量红利是否成立。 - 一般四主体可加EFX:在任意实例上解决具有可加效用的 $n = 4$ 名主体EFX分配的存在性仍然是未决的。尽管计算机辅助验证已解决了直至 $m \le 9$ 个物品的情形,并且已知 $n = 4$ 时 EF2X 成立,但针对不受限实例的存在性证明或反例仍属未知。
- 估值边界:对于具有单调次模效用的三名主体以及具有可加负效用物品的四名或更多主体,EFX可能会失败。刻画EFX从保证存在性转变为不存在的精确边界,仍是离散公平分配中一个未决的问题。
为什么是研究级成果
- Extends common least-good insertion to two universally small goods with arbitrary within-pair rankings, preserving every old bundle and weakly improving all own utilities; iteration gives complete EFX for any number of agents and goods ordered in common pairs
Lean 声明
- efx_exists_of_two_universal_small_goods_irLet m and n be natural numbers with n positive. There are m+2 goods with nonnegative real additive values for n agents. Each agent values…
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
- is_efx_goodsAn allocation is EFX if for every pair of distinct agents i and j, and every good g in j's bundle, agent i values her own bundle at least…
- finite_two_bonus_ordered_assignmentFor any finite nonempty real matrix w and two nonnegative agent-dependent bonuses a and b, there is a permutation of the old columns, a…
- additive_valuation_erase_of_memRemoving a good belonging to a finite bundle subtracts exactly its item value from the additive value of that bundle.
- bundle_of_permute_agentsReassigning every good by the inverse of an agent permutation makes the bundle of agent i equal to the old bundle of the permuted agent.
- additive_valuation_bundle_last_casesAssigning the additional last good to agent s adds exactly its value to the old bundle value of s and leaves every other bundle value…
- is_efx_goods_all_pairsFor nonnegative additive values, the EFX inequalities also hold when the observer and the target agent coincide.
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
参考文献
- arXiv:2208.08782 — Fair Division of Indivisible Goods: Recent Progress and Open Questions
- arXiv:1707.04769
- arXiv:2504.03951
由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。