AFTD Auto-Formalizing Theoretical Domains

Research Blogs

单调次模估价与平等权益下每个最小 EFX 份额分配都是 PROP1 的

medium tier2026-10-03OP-47审阅: Claude CodeEnglish

摘要

arXiv:2502.02815 第 6 节中的公开问题 3 询问:在单调次模估价和平等权益下,对某个参与者而言具有最小 EFX 份额(MXS)公平性的不可分物品分配,是否必然对该参与者也是至多一个物品的比例(PROP1)公平的。本文给出了该问题的肯定解答。如果分配给某参与者的物品包不是 PROP1 公平的,则该参与者相对于其比例份额将承受严格正的不足额 $\delta > 0$,且其物品包之外的任何单个物品所提供的边际增益至多为 $\delta$。通过考察见证最小 EFX 份额性质的凭据分配,可以从其他每个参与者的物品包中识别出至多一个相对于接收者的凭据物品包具有正边际价值的物品。根据 EFX 保证,剔除这些物品将使其他每个物品包的价值降低至凭据物品包之下。随后证明根据是否其他每个参与者的物品包都包含这样一个物品,或者至少有一个参与者不包含进行分情形讨论:在前一种情形下,次模单调性将全集物品包的估价严格限制在其真实价值之下;在后一种情形下,来自没有正边际物品的参与者的所有物品在凭据物品包的基础上贡献的边际价值为零并发生坍塌,同样导致严格矛盾。该定理已在 Lean 4 中形式化并经过机器检查,定理名称为 mxs_fair_imp_prop1_fair_of_submodular。

1. 引言

在离散公平分配中,研究了在多个参与者之间分配不可分物品的问题。当在具有平等权益的 $n$ 个参与者之间分配 $m$ 个不可分物品时,诸如比例性——要求每个参与者 $i$ 获得的物品包的估价至少为 $v_i(M)/n$,其中 $M$ 为所有物品的全集包——这类经典标准并不总能得到满足。例如,当在两个参与者之间分配单个物品时,必有一名参与者一无所获,这无法达到精确的比例性。

这激发了对公平性松弛条件的研究。一种松弛条件是至多一个物品的比例性(PROP1),它规定参与者的物品包要么直接达到其比例份额,要么可以通过在其物品包之外添加单个物品(或通过移除一个物品)使其严格高于比例份额。另一个方向则是研究源自至多任一物品的无嫉妒(EFX)的基于份额的标准。如果任何参与者在从其他任何参与者的物品包中移除任一物品后都不嫉妒该物品包,则该分配是 EFX 的。尽管在所有实例中 EFX 分配的存在性仍是一个公开问题,但 arXiv:2502.02815 研究了该文定义 10 中定义的最小 EFX 份额(MXS)。在 MXS 下,如果参与者对其所分配物品包的估价,至少不低于其在某种对其而言是 EFX 公平的假设分配下所获得的物品包的估价,则该分配对该参与者是公平的。这样的假设分配充当见证该分配公平性的 EFX 凭据。

理解这些公平性概念之间的关系是 arXiv:2502.02815 的核心关注点。在该论文的第 6 节中,公开问题 3 提出了如下问题:

“对于次模物品(平等权益),MXS 是否蕴涵 PROP1?”

根据 arXiv:2502.02815 中的内容,这种蕴涵关系此前已在一个特例下建立:arXiv:2502.02815 附录 D 中的引理 68 证明了当估价是具有二元边际值的次模函数(即每个物品对任何物品包的边际贡献要么为 0 要么为 1)时,MXS 蕴涵 PROP1。该蕴涵关系对于一般的次模估价是否成立仍然是一个公开问题。

本文对 arXiv:2502.02815 的公开问题 3 给出了肯定的回答:对于任意数量的参与者和物品,在单调次模估价和平等权益下,对某个参与者而言具有 MXS 公平性的每个分配,对该参与者而言也都是 PROP1 公平的。

该论证采用反证法。假设分配未能满足对某个参与者的 PROP1 公平性,则该参与者相对于比例份额存在一个正的不足额 $\delta > 0$,这同时对该参与者物品包之外的任何单个物品的边际增益施加了上界 $\delta$。通过选取一个 EFX 凭据分配,我们可以从其他每个参与者那里分离出至多一个不在该参与者物品包中且相对于凭据物品包产生正边际增益的物品。移除这些物品会使其他每个物品包的价值降低至低于凭据物品包的价值。随后,我们根据物品包中包含此类正边际物品的参与者数量将分析分为两种情形:

  • 如果其他每个参与者都拥有这样一个物品,则被移除的物品总数为 $n - 1$。剩余物品与凭据物品包一起覆盖了该集合之外的所有物品,且次模性迫使全集物品包的总价值有界于 $n \cdot v_i(A) + (n - 1)\delta$,这严格小于 $n(v_i(A) + \delta) = v_i(M)$。
  • 如果至少有另一个参与者没有此类物品,则属于这些参与者的物品在凭据物品包之上的边际价值贡献为零。次模性允许我们在不增加估价的情况下吸收这些零边际物品,且总价值有界于 $n \cdot v_i(A) + (n - 2)\delta < v_i(M)$,再次导出矛盾。

该定理已在 Lean 4 中形式化并经过验证,定名为 mxs_fair_imp_prop1_fair_of_submodular。下文将给出相关定义、辅助引理及完整证明。

2. 预备知识

我们在具有平等权益的参与者之间进行不可分物品离散公平分配的标准模型下展开讨论。我们使用与 Lean 形式化相匹配的定义来形式化这一设定。

定义 1(分配与物品包,bundle_of)。设 $m, n \in \mathbb{N}$。设 $M = \{0, 1, \dots, m-1\}$ 表示不可分物品的集合,设 $N = \{0, 1, \dots, n-1\}$ 表示参与者的集合。分配是一个函数 $\sigma : M \to N$,它为每个物品 $x \in M$ 指定接收它的参与者 $\sigma(x) \in N$。对于任意参与者 $i \in N$,参与者 $i$ 在 $\sigma$ 下的物品包记作 $\text{bundle\_of } \sigma\ i$,定义为 $$\text{bundle\_of } \sigma\ i = \{x \in M \mid \sigma(x) = i\}.$$ 在此定义下,各物品包将 $M$ 划分为 $n$ 个两两不交的子集,其中某些子集可能为空。

定义 2(次模估价函数,is_submodular)。集合函数 $v : 2^M \to \mathbb{R}$ 若满足 $v(\emptyset) = 0$,则称为正规化的。若对所有子集 $S \subseteq T \subseteq M$,均有 $v(S) \le v(T)$,则称为单调的。集合函数 $v : 2^M \to \mathbb{R}$ 是次模的(is_submodular),若边际价值随着物品包的扩大而递减:对所有子集 $S \subseteq T \subseteq M$ 以及每个物品 $j \in M \setminus T$, $$v(T \cup \{j\}) - v(T) \le v(S \cup \{j\}) - v(S).$$

定义 3(EFX 公平性)。设 $v : 2^M \to \mathbb{R}$ 为估价函数。分配 $\tau : M \to N$ 对参与者 $i \in N$ 是 EFX 公平的,如果对其他每个参与者 $j \in N \setminus \{i\}$,令 $X = \text{bundle\_of } \tau\ i$ 且 $B_j = \text{bundle\_of } \tau\ j$,参与者 $i$ 在剔除自己严格看重的任意子集后,对自身物品包的估价至少不低于对 $B_j$ 的估价:要么 $v(B_j) \le v(X)$,要么对于使得 $v(X) < v(X \cup S)$ 的每个子集 $S \subseteq B_j$,均有 $$v(B_j \setminus S) \le v(X).$$ 特别地,当专门应用于单元素子集 $S = \{g\}$(其中 $g \in B_j$ 满足 $v(X) < v(X \cup \{g\})$)时,该条件要求 $v(B_j \setminus \{g\}) \le v(X)$。

定义 4(最小 EFX 份额,is_mxs_fair)。给定估价函数剖面 $v = (v_i)_{i \in N}$ 和分配 $\sigma : M \to N$,分配 $\sigma$ 对参与者 $i \in N$ 是 MXS 公平的(is_mxs_fair),如果存在一个分配 $\tau : M \to N$,使得 $\tau$ 对参与者 $i$ 是 EFX 公平的,并且满足 $$v_i(\text{bundle\_of } \tau\ i) \le v_i(\text{bundle\_of } \sigma\ i).$$ 分配 $\tau$ 称为 $\sigma$ 下参与者 $i$ 的 EFX 凭据。

定义 5(至多一个物品的比例性,is_prop1_fair)。给定估价函数 $v : 2^M \to \mathbb{R}$、权益权重 $w \in \mathbb{R}$ 和物品包 $A \subseteq M$,若以下三个条件中至少有一个成立,则物品包 $A$ 是 PROP1 公平的(is_prop1_fair):

  1. $w \cdot v(M) \le v(A)$,
  2. 存在一个物品 $g \in M \setminus A$ 使得 $w \cdot v(M) < v(A \cup \{g\})$,
  3. 存在一个物品 $c \in A$ 使得 $w \cdot v(M) < v(A \setminus \{c\})$。

对于 $n$ 个参与者之间的平等权益,权益权重为 $w = 1/n$。

我们强调 Lean 形式化的几个方面:

  • 严格不等式与弱不等式:在定义 5 中,条件 1 使用弱不等式($w \cdot v(M) \le v(A)$),而条件 2 和条件 3 则要求严格不等式($w \cdot v(M) < v(A \cup \{g\})$ 和 $w \cdot v(M) < v(A \setminus \{c\})$)。这对应于 arXiv:2502.02815 定义 5 中的严格形式 PROP1。
  • 移除分支:条件 3 允许通过舍弃物品 $c \in A$ 来达到比例份额。在具有单调估价的正面物品语境下,$v(A \setminus \{c\}) \le v(A)$,因此除非条件 1 已经成立,否则条件 3 绝不可能成立。虽然为了完全的通用性在 is_prop1_fair 中保留了移除分支,但在正面物品情形下它不起实质性作用。
  • 正规化:明确假设对于所有参与者 $i$,估价均满足 $v_i(\emptyset) = 0$。
  • 空全集约定:当 $m = 0$ 时,全集 $M = \emptyset$ 为空,因此 $A = \emptyset$ 且 $v_i(M) = 0$;由于 $(1/n) \cdot 0 \le 0$,条件 1 平凡地满足。

3. 主要结果

主要结果解决了 arXiv:2502.02815 的公开问题 3:

定理(mxs_fair_imp_prop1_fair_of_submodular)。设 $n, m \in \mathbb{N}$,且设 $v = (v_i)_{i \in N}$ 是 $2^M$ 上的估价函数剖面,其中 $N = \{0, 1, \dots, n-1\}$ 且 $M = \{0, 1, \dots, m-1\}$。假设对于每个参与者 $i \in N$,$v_i(\emptyset) = 0$,$v_i$ 是单调的,且 $v_i$ 是次模的(is_submodular)。设 $\sigma : M \to N$ 为一个分配且设 $i \in N$。如果 $\sigma$ 对参与者 $i$ 是 MXS 公平的(is_mxs_fair),则物品包 $\text{bundle\_of } \sigma\ i$ 在权益权重 $w = 1/n$ 下对参与者 $i$ 是 PROP1 公平的(is_prop1_fair)。

Lean 语句对该英文定理进行了形式化:对作为自然数的参与者数量 $n$ 和物品数量 $m$ 进行全称量化,将估价 $v$ 视为从 Fin $n$ 到从 Finset (Fin $m$) 到实数的集合函数的映射,要求对每个参与者都满足正规化、单调性和 is_submodular,并断言对每个分配 $\sigma$ 和参与者 $i$,is_mxs_fair 蕴涵物品包 bundle_of $\sigma\ i$ 在权益 $1/n$ 下满足 is_prop1_fair。

该结果在所有单调次模估价的完全一般性下解决了该公开问题。在该定理之前,唯一已知的情形建立于 arXiv:2502.02815 附录 D 中的引理 68,该引理在所有边际价值均为二元($v_i(S \cup \{g\}) - v_i(S) \in \{0, 1\}$)的限制下证明了这一蕴涵关系。定理 mxs_fair_imp_prop1_fair_of_submodular 完全去除了这一限制,表明该蕴涵关系在不对边际价值大小作任何约束的情况下成立。

定理 mxs_fair_imp_prop1_fair_of_submodular (Lean 4 已验证)
theorem mxs_fair_imp_prop1_fair_of_submodular :
    ∀ (n m : ℕ) (v : Fin n → Finset (Fin m) → ℝ),
      (∀ i, v i ∅ = 0 ∧ Monotone (v i) ∧ is_submodular (v i)) →
      ∀ (σ : Fin m → Fin n) (i : Fin n), is_mxs_fair v σ i →
        is_prop1_fair (v i) (1 / n) (bundle_of σ i)

4. 证明

我们先概述证明思路,然后给出四个辅助引理及其证明,最后给出结合这些引理的逐步论证。

证明采用反证法。假设 $\sigma$ 对参与者 $i$ 是 MXS 公平的,但所分配的物品包 $A = \text{bundle\_of } \sigma\ i$ 在权益 $1/n$ 下不满足 PROP1 公平性。令 $u = v_i$ 且 $V = u(M)$。PROP1 公平性的不满足意味着 $u(A) < V/n$,从而产生一个正的不足额 $\delta = V/n - u(A) > 0$,并且对于每个物品 $g \notin A$,均有 $u(A \cup \{g\}) \le u(A) + \delta$。

由 MXS 公平性,存在一个满足 $u(X) \le u(A)$ 的 EFX 凭据分配 $\tau$,其中 $X = \text{bundle\_of } \tau\ i$。对于其他每个参与者 $j \neq i$,我们检查其物品包 $B_j = \text{bundle\_of } \tau\ j$ 是否包含 $A$ 之外的、相对于 $X$ 具有正边际增益的物品。若是,我们选取一个这样的物品 $g(j)$;由 EFX,移除 $g(j)$ 后 $B_j$ 的估价至多为 $u(X)$。令 $K$ 为此类参与者的集合,且令 $G = \{g(j) \mid j \in K\}$。

我们定义 $W = X \cup \bigcup_{j \in K} (B_j \setminus \{g(j)\})$。次可加性与边际递减性质给出 $u(W) \le (|K| + 1) u(A)$。随后我们根据是否 $|K| = n - 1$ 进行分情形讨论:

  • 如果 $|K| = n - 1$,则 $G$ 之外的物品均包含在 $W$ 中,故 $A \subseteq W$ 且 $M \subseteq W \cup G$。添加 $G$ 至多带来 $(n - 1)\delta$ 的增益,给出 $V \le n \cdot u(A) + (n - 1)\delta < n(u(A) + \delta) = V$。
  • 如果 $|K| \le n - 2$,则不在 $K$ 中的参与者所拥有的 $A$ 之外的物品相对于 $X$ 具有零边际增益,并坍塌并入 $W \cup A$ 而不增加价值。添加 $G$ 至多带来 $|K|\delta \le (n - 2)\delta$ 的增益,而基底至多为 $(|K| + 2) u(A) \le n \cdot u(A)$,给出 $V \le n \cdot u(A) + (n - 2)\delta < V$。

两种情形均导出矛盾。现在我们确立这四个引理。

引理 1(submod_union_marginal_le)。设 $v : 2^M \to \mathbb{R}$ 为单调次模集合函数。对于所有子集 $S \subseteq T \subseteq M$ 和 $U \subseteq M$, $$v(T \cup U) - v(T) \le v(S \cup U) - v(S).$$ 证明。在 Lean 中通过对有限集 $U$ 进行归纳得以确立。基本情形 $U = \emptyset$ 给出 $0 \le 0$。对于归纳步骤,添加 $u \notin U$,由 $S \cup U \subseteq T \cup U$ 上的次模性(is_submodular)可得 $v(T \cup U \cup \{u\}) - v(T \cup U) \le v(S \cup U \cup \{u\}) - v(S \cup U)$。将其与归纳假设相加,中间项发生裂项抵消。

引理 2(submod_biUnion_le_sum)。设 $v : 2^M \to \mathbb{R}$ 为满足 $v(\emptyset) = 0$ 的单调次模集合函数。对于任意有限指标集 $K$ 和子集族 $(B_j)_{j \in K}$, $$v\left(\bigcup_{j \in K} B_j\right) \le \sum_{j \in K} v(B_j).$$ 证明。在 Lean 中通过对 $K$ 进行归纳得以确立。对于 $K = \emptyset$,$v(\emptyset) = 0 \le 0$。对于 $K = K' \cup \{k\}$(其中 $k \notin K'$),令 $U = \bigcup_{j \in K'} B_j$。应用引理 1 于 $S = \emptyset \subseteq U$,可得 $v(U \cup B_k) - v(U) \le v(B_k) - v(\emptyset) = v(B_k)$。加上归纳假设 $v(U) \le \sum_{j \in K'} v(B_j)$ 即完成归纳步骤。

引理 3(submod_add_items_le)。设 $v : 2^M \to \mathbb{R}$ 为次模集合函数。设 $A \subseteq W \subseteq M$,$\delta \ge 0$,且设 $G \subseteq M$ 为有限集,使得对每个 $g \in G$,均有 $g \notin A$ 且 $v(A \cup \{g\}) \le v(A) + \delta$。则 $$v(W \cup G) \le v(W) + |G| \cdot \delta.$$ 证明。在 Lean 中通过对 $G$ 进行归纳得以确立。对于 $G = \emptyset$,$|G| = 0$ 且 $v(W) \le v(W)$。对于 $G = G' \cup \{g\}$(其中 $g \notin G'$),由于 $A \subseteq W \subseteq W \cup G'$,由次模性可知 $v(W \cup G' \cup \{g\}) - v(W \cup G') \le v(A \cup \{g\}) - v(A) \le \delta$。将其与归纳界 $v(W \cup G') \le v(W) + |G'|\delta$ 相加即得 $v(W \cup G) \le v(W) + |G|\delta$。

引理 4(submod_zero_marginals)。设 $v : 2^M \to \mathbb{R}$ 为单调次模集合函数。设 $X \subseteq W \subseteq M$,且设 $R \subseteq M$ 为有限集,使得对每个 $z \in R$,均有 $v(X \cup \{z\}) \le v(X)$。则 $$v(W \cup R) = v(W).$$ 证明。在 Lean 中通过对 $R$ 进行归纳得以确立。情形 $R = \emptyset$ 是平凡的。对于 $R = R' \cup \{z\}$(其中 $z \notin R'$),归纳假设给出 $v(W \cup R') = v(W)$。由于 $X \subseteq W \subseteq W \cup R'$,由次模性可知 $v(W \cup R' \cup \{z\}) - v(W \cup R') \le v(X \cup \{z\}) - v(X) \le 0$。单调性给出了相匹配的下界 $v(W \cup R') \le v(W \cup R' \cup \{z\})$,故等式成立。

现在我们结合这些引理来证明该定理。

固定参与者 $i \in N$。记 $u = v_i$,$A = \text{bundle\_of } \sigma\ i$ 且 $V = u(M)$。由于 $\sigma$ 对 $i$ 是 MXS 公平的(is_mxs_fair),因此存在一个对 $i$ 而言是 EFX 公平的分配 $\tau$,使得 $u(X) \le u(A)$,其中 $X = \text{bundle\_of } \tau\ i$。注意,由于 $u(\emptyset) = 0$ 且 $u$ 是单调的,故 $u(A) \ge 0$。

反设 $A$ 在权益 $1/n$ 下不是 PROP1 公平的。根据定义 5(is_prop1_fair)的否定,我们有:

  1. $u(A) < \frac{1}{n} V$,
  2. 对所有 $g \notin A$,$u(A \cup \{g\}) \le \frac{1}{n} V$,
  3. 对所有 $c \in A$,$u(A \setminus \{c\}) \le \frac{1}{n} V$。

令 $\delta = \frac{1}{n} V - u(A)$。由条件 1 可知 $\delta > 0$,故 $V = n(u(A) + \delta)$。条件 2 给出对所有 $g \notin A$ 均有 $u(A \cup \{g\}) \le u(A) + \delta$。若 $M = \emptyset$,则 $A = \emptyset$ 且 $V = 0$,导出 $0 < 0$,矛盾。因此 $M$ 非空且 $n \ge 1$。

对于每个 $j \in N$,记 $B_j = \text{bundle\_of } \tau\ j$。定义性质 $P(j, x) \iff x \in B_j \land x \notin A \land u(X) < u(X \cup \{x\})$。令 $$K = \{j \in N \setminus \{i\} \mid \exists x \in M, P(j, x)\}.$$ 对于每个 $j \in K$,通过选择(Classical.epsilon)选取一个满足 $P(j, g(j))$ 的见证元 $g(j) \in M$。由 EFX 公平性(定义 3),因为 $j \neq i$ 且 $u(X) < u(X \cup \{g(j)\})$,单元素集 $\{g(j)\}$ 给出 $$u(B_j \setminus \{g(j)\}) \le u(X) \quad \text{for all } j \in K.$$

令 $G = \{g(j) \mid j \in K\}$。则 $|G| \le |K|$。每个 $x \in G$ 都满足 $x \notin A$ 以及 $u(A \cup \{x\}) \le u(A) + \delta$。定义 $$W = X \cup \bigcup_{j \in K} (B_j \setminus \{g(j)\}).$$ 应用引理 1 于 $S = \emptyset \subseteq X$ 和 $U = \bigcup_{j \in K} (B_j \setminus \{g(j)\})$,给出 $u(W) - u(X) \le u(U) - u(\emptyset) = u(U)$。对 $U$ 应用引理 2 给出 $u(U) \le \sum_{j \in K} u(B_j \setminus \{g(j)\}) \le |K| \cdot u(X)$。由于 $u(X) \le u(A)$,故有 $$u(W) \le (|K| + 1) u(X) \le (|K| + 1) u(A).$$

由于 $K \subseteq N \setminus \{i\}$,我们有 $|K| \le n - 1$。随后我们根据是否 $|K| = n - 1$ 进行分情形讨论。

情形 1:$K = N \setminus \{i\}$,故 $|K| = n - 1$。

对于任意 $x \in M \setminus G$,若 $\tau(x) = i$,则 $x \in X \subseteq W$。若 $\tau(x) = j \neq i$,则 $j \in K$ 且 $x \neq g(j)$,因此 $x \in B_j \setminus \{g(j)\} \subseteq W$。从而 $M \setminus G \subseteq W$。由于 $G \cap A = \emptyset$,这给出 $A \subseteq W$,并且还有 $M \subseteq W \cup G$。

由单调性,$V \le u(W \cup G)$。应用引理 3 于 $A \subseteq W$ 和 $G$,给出 $u(W \cup G) \le u(W) + |G| \cdot \delta \le n \cdot u(A) + (n - 1) \delta$。因为 $\delta > 0$,所以 $$V \le n \cdot u(A) + (n - 1) \delta < n \cdot u(A) + n \delta = V,$$ 导出矛盾。具体而言,对于 $n = 3$ 个参与者且 $|K| = 2$ 的情形,该上界给出 $V \le 3 u(A) + 2\delta$,与 $V = 3 u(A) + 3\delta$ 相比差了 $\delta > 0$。

情形 2:$K \subsetneq N \setminus \{i\}$,故 $|K| \le n - 2$ 且 $(|K| : \mathbb{R}) + 2 \le n$。

定义 $R = \{x \in M \mid x \notin A \land \tau(x) \neq i \land \tau(x) \notin K\}$。对于每个 $z \in R$,参与者 $\tau(z) \notin K$ 没有在 $A$ 之外相对于 $X$ 具有正边际增益的物品,故 $u(X \cup \{z\}) \le u(X)$。

令 $W' = W \cup A$。每个 $x \in M$ 都属于 $(W' \cup R) \cup G$:

  • 若 $\tau(x) = i$,则 $x \in X \subseteq W \subseteq W'$。
  • 若 $x \in A$,则 $x \in A \subseteq W'$。
  • 若 $x \notin A$ 且 $\tau(x) \in K$ 满足 $x = g(\tau(x))$,则 $x \in G$。
  • 若 $x \notin A$ 且 $\tau(x) \in K$ 满足 $x \neq g(\tau(x))$,则 $x \in B_{\tau(x)} \setminus \{g(\tau(x))\} \subseteq W \subseteq W'$。
  • 若 $x \notin A$ 且 $\tau(x) \notin K \cup \{i\}$,则 $x \in R$。

因此 $M \subseteq (W' \cup R) \cup G$,故 $V \le u((W' \cup R) \cup G)$。由于 $X \subseteq W'$,引理 4 给出 $u(W' \cup R) = u(W')$。应用引理 1 于 $\emptyset \subseteq W$ 和 $A$ 给出 $u(W') = u(W \cup A) \le u(W) + u(A) \le (|K| + 2) u(A)$。

应用引理 3 于 $A \subseteq W' \subseteq W' \cup R$ 和 $G$,给出 $$V \le u(W' \cup R) + |G| \cdot \delta \le (|K| + 2) u(A) + |K| \delta.$$ 由于 $|K| + 2 \le n$,$u(A) \ge 0$,$|K| \le n - 2$ 且 $\delta > 0$,所以 $$V \le n \cdot u(A) + (n - 2) \delta < n(u(A) + \delta) = V,$$ 导出矛盾。具体而言,对于 $n = 3$:若 $|K| = 1$,该界给出 $V \le 3 u(A) + \delta < 3 u(A) + 3\delta = V$(差额为 $2\delta$);若 $|K| = 0$,则给出 $V \le 2 u(A) \le 3 u(A) < 3 u(A) + 3\delta = V$(差额至少为 $u(A) + 3\delta$)。

两种情形均与 $V = V$ 矛盾,从而确立了定理 mxs_fair_imp_prop1_fair_of_submodular。

5. 讨论

定理 mxs_fair_imp_prop1_fair_of_submodular 对 arXiv:2502.02815 第 6 节的公开问题 3 给出了肯定的解答,表明在单调次模估价和平等权益下,对某个参与者而言具有 MXS 公平性的每个分配,对该参与者而言也都是 PROP1 公平的。

这一结果拓展了 arXiv:2502.02815 中所确立的内容。在该论文中,这一蕴涵关系是在二元边际值的限制下建立的(附录 D 中的引理 68),即任何物品对任何物品包的边际贡献要么为 0 要么为 1。定理 mxs_fair_imp_prop1_fair_of_submodular 表明,该蕴涵关系对所有单调次模估价均成立,而无需对边际价值做任何限制。

该论证凸显了次模性的结构性作用,并指出了该定理未涵盖的方面:

  • 次模性之外的估价:证明在三个不同步骤中使用了次模性。一步是利用次可加性来界定缩减后物品包的并集 $W$ 的价值,该次可加性源于次模性以及正规化条件 $v(\emptyset) = 0$(引理 2,submod_biUnion_le_sum)。另一步是利用边际报酬递减性质来界定所选物品 $G$ 在 $A$ 的超集之上的边际贡献(引理 3,submod_add_items_le)。还有一步是吸收属于不在 $K$ 中的参与者的物品 $R$,这依赖于相对于 $X$ 具有非正边际增益的物品在 $X$ 的任何超集之上的边际增益均为零的性质(引理 4,submod_zero_marginals)。对于更广泛的估价类别——如次可加(subadditive)、分数次可加(fractionally subadditive)或一般的单调估价——第三个性质通常不再成立,而在这些设定下 MXS 是否蕴涵 PROP1 尚未由该结果解决。
  • 不等权益:该定理是针对平等权益叙述的,其中每个参与者的权益权重为 $w = 1/n$。在不等权益 $(w_i)_{i \in N}$ 下,比例性和基于份额的概念均结合了参与者的权重。满足加权最小 EFX 份额保证的分配是否必然满足加权 PROP1,该结果并未涉及。
  • 负面物品与混合物品:该结果适用于正面物品(goods),此时估价是单调非降的且 $v_i(S) \ge 0$。在不可分负面物品(chores)的公平分配中,EFX、MXS 和 PROP1 的定义涉及不同的物品移除与添加,这些关系依然是独立的。

随着公开问题 3 得到解决,平等权益下次模估价的 MXS 与 PROP1 之间的关系得以解决。

为什么是研究级成果

  • settles OP-47 (Does MXS imply PROP1 for submodular goods?)

Lean 声明

  • mxs_fair_imp_prop1_fair_of_submodularOpen problem 3 of arXiv:2502.02815 has a positive answer: for submodular goods (monotone, v(empty) = 0) and equal entitlements, every…
  • 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_submodularA set function is submodular: for S inside T and j outside T, the marginal value of j over T is at most its marginal value over S.
  • is_mxs_fairAn allocation is MXS-fair to agent i (minimum EFX share, arXiv:2502.02815, Def. 10) if i's bundle is worth to her at least her bundle in…
  • is_prop1_fairAn allocation is PROP1-fair to an agent with valuation v and entitlement w if her bundle A has v(A) >= w v(M), or v(A + g) > w v(M) for…
  • submod_union_marginal_leFor a monotone submodular set function and S inside T, adding a set U gains at most as much on top of T as on top of S.
  • submod_biUnion_le_sumA monotone submodular set function with v(empty) = 0 is subadditive over a finite family of sets.
  • submod_add_items_leFor a submodular set function, if every item of G lies outside A and adds at most delta >= 0 to A, then adding G to any superset W of A…
  • submod_zero_marginalsFor a monotone submodular set function, items whose marginal value over X is zero add nothing on top of any superset of X.

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

参考文献

  1. arXiv:2502.02815 — Exploring Relations among Fairness Notions in Discrete Fair Division

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