AFTD Auto-Formalizing Theoretical Domains

Research Blogs

两个主体下最大纳什福利的确切代价与强代价等于 27/23

medium tier2026-10-06OP-67审阅: Claude CodeEnglish

摘要

最大纳什福利(MNW)的代价衡量了要求不可分物品的分配最大化纳什福利乘积所导致的最坏情况效率损失,定义为最优功利主义社会福利与最佳 MNW 分配所达到的福利之间的上确界比率。MNW 的强代价则考虑最差 MNW 分配的福利。对于具有可加、非负、归一化估值的两个主体,arXiv:1905.04910 表明 MNW 的代价与强代价均落在区间 $[27/23, 5/4]$ 内。本文介绍了这一问题的解决:每个最大纳什福利分配 $N$ 与每个备选分配 $O$ 都满足 $23 \cdot \mathrm{utilitarian\_welfare}(v, O) \le 27 \cdot \mathrm{utilitarian\_welfare}(v, N)$。该证明根据物品在 $O$ 和 $N$ 下的接收者将物品划分为四个集合,列出了反映 $N$ 相比于 $O$ 以及四种物品包重新分配生成的分配之最大性的五个二次约束,并通过 mnw2_core 利用括号引理与多项式证书确立了该界。结合收敛到 $27/23$ 的已知下界实例,这确立了两个主体下 MNW 的代价与强代价均恰好为 $27/23$。该定理及所有支持引理已在 Lean 4 中形式化验证为 mnw_two_agents_welfare_le。

1. 引言

不可分物品的公平分配是社会选择与算法博弈论中的核心课题。在多个主体之间分配一组不可分物品时,人们通常寻求满足公平性标准(如无嫉妒性或比例性)或效率标准(如帕累托最优性或功利主义社会福利最大化)的分配。功利主义社会福利通过各主体对其所得物品包估值的算术和来评估分配。相比之下,纳什福利则通过各主体物品包估值的几何平均数或乘积来评估分配。已知最大化纳什福利的分配(MNW 分配)在公平性与效率之间提供了极具吸引力的平衡。

然而,强制实施公平性约束可能会降低无约束分配所能达到的总功利主义社会福利。这种权衡通过 arXiv:1905.04910 中引入的公平代价概念被形式化。对于给定的公平性概念,公平代价定义为在所有实例中,最优功利主义社会福利与最佳公平分配的功利福利之间的最坏情况比率。当存在多个公平分配时,强公平代价则取最差的公平分配,衡量选择任意公平分配时可能产生的最大福利损失。

在 arXiv:1905.04910 中,分析了几种公平性概念的公平代价与强公平代价,包括至多一个物品的比例性(PROP1)、至多一个物品的无嫉妒(EF1)以及最大纳什福利。在 arXiv:1905.04910 的表 1 和定理 5.4 中,在双主体设定下为几乎所有被考量的公平性概念确立了确切的界。正如 arXiv:1905.04910 中所述:“此外,除了 EF1 和 MNW 之外,我们在双主体情形下为所有公平性概念都确立了完全紧确的界。”

对于具有可加、非负且归一化估值(其中每个主体对全部物品集合的估值归一化为 1)的两个主体的情形,arXiv:1905.04910 的定理 5.4 证明了 MNW 的代价与 MNW 的强代价均落在区间 $[27/23, 5/4]$ 内。$27/23$ 这一下界源自一个包含两个主体和三个不可分物品的显式实例族,该实例族由 $\varepsilon > 0$ 参数化。在这些实例中,最优功利福利为 $9/7$,而每个 MNW 分配达到的功利福利为 $23/21 + \varepsilon$。随着 $\varepsilon \to 0$,最优功利福利与 MNW 功利福利的比率趋近于 $(9/7)/(23/21) = 27/23 \approx 1.1739$。在上界方面,定理 5.4 确立了对于两个主体该比率不能超过 $5/4 = 1.25$,从而在 $27/23$ 与 $5/4$ 之间留下了差距。对于一般的 $n$ 个主体,arXiv:1905.04910 表明 MNW 的代价以 $\Theta(n)$ 增长,因此关于 $n$ 的渐近依赖关系已被解决,但两个主体下的确切数值仍未确定。

本文介绍了这一双主体差距的解决。我们阐述了定理 mnw_two_agents_welfare_le 的形式化证明,该定理表明,对于任意数量的物品 $m$ 以及任意两个具有可加、非负、归一化估值的主体,每个 MNW 分配 $N$ 对每个备选分配 $O$ 都满足 $23 \cdot \mathrm{utilitarian\_welfare}(v, O) \le 27 \cdot \mathrm{utilitarian\_welfare}(v, N)$。这把上界从 $5/4$ 改进到了 $27/23$。结合匹配的下界结果 mnw_two_agents_price_lower_bound,这确立了两个主体下 MNW 的代价与 MNW 的强代价均恰好等于 $27/23$。

2. 预备知识

我们遵循已验证开发中的声明,在 Lean 4 中形式化该问题设定。设主体数量为 $n = 2$,由类型 $\mathrm{Fin}\; 2 = \{0, 1\}$ 表示,并设 $m \in \mathbb{N}$ 表示不可分物品的数量,由 $\mathrm{Fin}\; m$ 索引。

定义 1(估值与分配)。分配是一个函数 $\sigma : \mathrm{Fin}\; m \to \mathrm{Fin}\; 2$,其中 $\sigma(g) = i$ 表示物品 $g$ 分配给主体 $i$。对于主体 $i \in \mathrm{Fin}\; 2$,在 $\sigma$ 下分配给 $i$ 的物品包定义为 $X_i(\sigma) = \{g \in \mathrm{Fin}\; m \mid \sigma(g) = i\}$。估值由函数 $v : \mathrm{Fin}\; 2 \to \mathrm{Fin}\; m \to \mathbb{R}$ 给出。假定估值满足:

  1. 非负性:对所有 $i \in \mathrm{Fin}\; 2$ 和所有 $g \in \mathrm{Fin}\; m$,$0 \le v(i, g)$。
  2. 可加性:物品包 $S \subseteq \mathrm{Fin}\; m$ 对主体 $i$ 的价值由 $v_i(S) = \sum_{g \in S} v(i, g)$ 给出。
  3. 归一化:对每个主体 $i \in \mathrm{Fin}\; 2$,$\sum_{g \in \mathrm{Fin}\; m} v(i, g) = 1$。

注 1:物品是不可分的,这意味着每个物品 $g$ 均完整地分配给单个主体。归一化 $\sum_g v(i, g) = 1$ 在公平代价文献中(如 arXiv:1905.04910 中)是标准的,以使主体之间的功利比较具有意义。

定义 2(功利主义社会福利 utilitarian_welfare)。对于估值 $v : \mathrm{Fin}\; 2 \to \mathrm{Fin}\; m \to \mathbb{R}$ 和分配 $\sigma : \mathrm{Fin}\; m \to \mathrm{Fin}\; 2$,功利主义社会福利是物品包价值的总和: $$\mathrm{utilitarian\_welfare}(v, \sigma) = \sum_{i \in \mathrm{Fin}\; 2} \sum_{g \in X_i(\sigma)} v(i, g).$$ 在 Lean 中,utilitarian_welfare 定义为对所有主体 $i$,主体 $i$ 在 $\sigma$ 下物品包的可加估值之和。

定义 3(纳什福利 nash_welfare)。对于估值 $v : \mathrm{Fin}\; 2 \to \mathrm{Fin}\; m \to \mathbb{R}$ 和分配 $\sigma : \mathrm{Fin}\; m \to \mathrm{Fin}\; 2$,纳什福利是各主体物品包估值的乘积: $$\mathrm{nash\_welfare}(v, \sigma) = \prod_{i \in \mathrm{Fin}\; 2} \sum_{g \in X_i(\sigma)} v(i, g).$$ 在 Lean 中,nash_welfare 定义为对所有主体 $i$,主体 $i$ 在 $\sigma$ 下物品包的可加估值之积。

定义 4(最大纳什福利分配 is_mnw_allocation)。若没有分配 $\tau : \mathrm{Fin}\; m \to \mathrm{Fin}\; 2$ 能达到严格更高的纳什福利,则分配 $\sigma : \mathrm{Fin}\; m \to \mathrm{Fin}\; 2$ 是一个最大纳什福利分配: $$\forall \tau : \mathrm{Fin}\; m \to \mathrm{Fin}\; 2,\quad \mathrm{nash\_welfare}(v, \tau) \le \mathrm{nash\_welfare}(v, \sigma).$$ 在 Lean 中,is_mnw_allocation 将此性质形式化为全称命题:对所有分配 $\tau$,$\mathrm{nash\_welfare}(v, \tau) \le \mathrm{nash\_welfare}(v, \sigma)$。

注 2:当可达到的最大纳什福利严格为正时,is_mnw_allocation 与 arXiv:1905.04910 中的通常定义一致。当最大纳什福利为零时,文献中的标准惯例采用字典序平局决胜规则,首要最大化获得正效用的主体数量,进而最大化正效用的乘积。谓词 is_mnw_allocation 仅要求纳什乘积最大(即为零),因此达到乘积为零的每个分配都满足 is_mnw_allocation。由于满足 is_mnw_allocation 的分配集合包含了在字典序平局决胜规则下所选出的所有分配,因此对所有满足 is_mnw_allocation 的分配均成立的福利损失上界直接适用于经过平局决胜的分配,并且至少同样强。

定义 5(MNW 代价与强 MNW 代价)。给定一个存在最优功利分配 $O^* = \arg\max_\tau \mathrm{utilitarian\_welfare}(v, \tau)$ 的实例 $(m, v)$,令 $\mathcal{M}(v)$ 表示满足 is_mnw_allocation 的分配集合。 MNW 的代价是该比率在所有实例上的上确界: $$\frac{\mathrm{utilitarian\_welfare}(v, O^*)}{\sup_{N \in \mathcal{M}(v)} \mathrm{utilitarian\_welfare}(v, N)}.$$ MNW 的强代价是该比率在所有实例上的上确界: $$\frac{\mathrm{utilitarian\_welfare}(v, O^*)}{\inf_{N \in \mathcal{M}(v)} \mathrm{utilitarian\_welfare}(v, N)}.$$

注 3:MNW 的代价使用关于功利福利最佳的 MNW 分配,而 MNW 的强代价使用最差的 MNW 分配。

3. 主要结果

主定理确立了对于具有可加、非负、归一化估值的两个主体,任何分配的功利主义社会福利至多是任何最大纳什福利分配的功利主义社会福利的 $27/23$ 倍。

定理 1(mnw_two_agents_welfare_le)。设 $m \in \mathbb{N}$ 为任意物品数量。设 $v : \mathrm{Fin}\; 2 \to \mathrm{Fin}\; m \to \mathbb{R}$ 为满足非负性(对所有 $i \in \mathrm{Fin}\; 2, g \in \mathrm{Fin}\; m$ 均有 $0 \le v(i, g)$)与归一化(对所有 $i \in \mathrm{Fin}\; 2$ 均有 $\sum_{g \in \mathrm{Fin}\; m} v(i, g) = 1$)的可加估值。设 $N, O : \mathrm{Fin}\; m \to \mathrm{Fin}\; 2$ 为分配,使得 $N$ 是满足 is_mnw_allocation 的最大纳什福利分配。则: $$23 \cdot \mathrm{utilitarian\_welfare}(v, O) \le 27 \cdot \mathrm{utilitarian\_welfare}(v, N).$$

简而言之,mnw_two_agents_welfare_le 的 Lean 语句对物品数量 $m : \mathbb{N}$、估值函数 $v : \mathrm{Fin}\; 2 \to \mathrm{Fin}\; m \to \mathbb{R}$、非负性与归一化的证明、两个任意分配 $N$ 与 $O$ 以及 $N$ 满足 is_mnw_allocation 的假设进行全称量化,并在对 $m$ 的大小没有任何限制的情况下断言了 $\mathbb{R}$ 中的线性不等式 $23 \cdot \mathrm{utilitarian\_welfare}(v, O) \le 27 \cdot \mathrm{utilitarian\_welfare}(v, N)$。

定理 1 直接给出了对这两种公平性度量的界:

  • 因为该不等式对每个分配 $O$ 均成立,所以它特别地对最优功利分配 $O^*$ 成立。
  • 因为该不等式对每个满足 is_mnw_allocation 的分配 $N$ 均成立,所以它特别地对使功利福利最小化的 MNW 分配成立。
  • 因此,只要 $\mathrm{utilitarian\_welfare}(v, N) > 0$,比率 $\mathrm{utilitarian\_welfare}(v, O^*) / \mathrm{utilitarian\_welfare}(v, N)$ 就可以从上方被 $27/23 \approx 1.1739$ 界定。

因此,两个主体下 MNW 的代价与 MNW 的强代价至多为 $27/23$。这严格改进了 arXiv:1905.04910 定理 5.4 中给出的先前上界 $5/4 = 1.25$。

为了确立紧确性,我们回顾先前验证的结果 mnw_two_agents_price_lower_bound:对于每个实数常数 $c < 27/23$,存在一个具有两个主体、三个物品($m = 3$)和归一化估值的实例,使得存在 MNW 分配且每个 MNW 分配 $N$ 都满足 $c \cdot \mathrm{utilitarian\_welfare}(v, N) < \mathrm{utilitarian\_welfare}(v, O)$。该实例是来自 arXiv:1905.04910 定理 5.4 的下界构造,其中 $O$ 达到功利福利 $9/7$,而每个 MNW 分配 $N$ 达到功利福利 $23/21 + \varepsilon$,给出的比率 $(9/7)/(23/21 + \varepsilon)$ 随着 $\varepsilon \to 0$ 趋近于 $27/23$。

mnw_two_agents_welfare_le 与 mnw_two_agents_price_lower_bound 共同证明了两个主体下 MNW 的确切代价与确切强代价均等于 $27/23$。

定理 mnw_two_agents_welfare_le (Lean 4 已验证)
theorem mnw_two_agents_welfare_le (m : ℕ) (v : Fin 2 → Fin m → ℝ) (hv : ∀ i g, 0 ≤ v i g) (hn : ∀ i, ∑ g, v i g = 1) (N O : Fin m → Fin 2) (hN : is_mnw_allocation v N) : 23 * utilitarian_welfare v O ≤ 27 * utilitarian_welfare v N

4. 证明

我们给出 mnw_two_agents_welfare_le 的证明,详细说明规约到八变量多项式优化问题及其通过 mnw2_core 的解决过程。

总体思路是根据每个物品在 $O$ 下和在 $N$ 下所分配给的主体,将这 $m$ 个物品划分为四个不相交的组。令 $G_{ab}$ 表示在 $O$ 下分配给主体 $a$ 且在 $N$ 下分配给主体 $b$ 的物品集合: $$G_{ab} = \{g \in \mathrm{Fin}\; m \mid O(g) = a \wedge N(g) = b\} \quad \text{for } a, b \in \{0, 1\}.$$ 我们将这四个组记为:

  • $A = G_{00}$:由 $O$ 分配给主体 0 且由 $N$ 分配给主体 0 的物品。
  • $B = G_{10}$:由 $O$ 分配给主体 1 且由 $N$ 分配给主体 0 的物品。
  • $C = G_{01}$:由 $O$ 分配给主体 0 且由 $N$ 分配给主体 1 的物品。
  • $D = G_{11}$:由 $O$ 分配给主体 1 且由 $N$ 分配给主体 1 的物品。

对于主体 0,令 $p, q, r, s$ 表示这四个组的价值: $$p = \sum_{g \in A} v(0, g),\quad q = \sum_{g \in B} v(0, g),\quad r = \sum_{g \in C} v(0, g),\quad s = \sum_{g \in D} v(0, g).$$ 对于主体 1,令 $\alpha, \beta, \gamma, \delta$ 表示这四个组的价值: $$\alpha = \sum_{g \in A} v(1, g),\quad \beta = \sum_{g \in B} v(1, g),\quad \gamma = \sum_{g \in C} v(1, g),\quad \delta = \sum_{g \in D} v(1, g).$$

因为对所有 $i$ 和 $g$ 均有 $0 \le v(i, g)$,所以物品子集上的每个求和都是非负的。这给出了八个非负性条件: $$0 \le p,\quad 0 \le q,\quad 0 \le r,\quad 0 \le s,\quad 0 \le \alpha,\quad 0 \le \beta,\quad 0 \le \gamma,\quad 0 \le \delta.$$

物品求和的分解由以下引理所保证。

引理 1(mnw2_sum_groups)。对于任何估值函数 $u : \mathrm{Fin}\; m \to \mathbb{R}$、分配 $O, N : \mathrm{Fin}\; m \to \mathrm{Fin}\; 2$ 以及权重函数 $c : \mathrm{Fin}\; 2 \to \mathrm{Fin}\; 2 \to \mathbb{R}$, $$\sum_{g \in \mathrm{Fin}\; m} c(O(g), N(g)) \cdot u(g) = \sum_{a=0}^1 \sum_{b=0}^1 c(a, b) \sum_{g \in G_{ab}} u(g).$$ 证明。在 Lean 中,全集索引集被划分为四个对 $a, b \in \{0, 1\}$ 的不相交过滤器 $\{g \mid O(g) = a \wedge N(g) = b\}$。将全集求和分解为这四个子求和便确立了该恒等式。

将常数权重函数 $c(a, b) = 1$ 的引理 1 应用于归一化估值 $v(0)$ 和 $v(1)$(利用 $\sum_g v(i, g) = 1$),确立了归一化条件: $$p + q + r + s = 1 \quad (\text{hypothesis } h1),$$ $$\alpha + \beta + \gamma + \delta = 1 \quad (\text{hypothesis } h2).$$

接下来,我们评估通过将每个组 $G_{ab}$ 整体分配给一个主体所生成的分配。

引理 2(mnw2_bundle_value)。设 $u : \mathrm{Fin}\; m \to \mathbb{R}$,分配 $O, N, \tau : \mathrm{Fin}\; m \to \mathrm{Fin}\; 2$,以及转移映射 $T : \mathrm{Fin}\; 2 \to \mathrm{Fin}\; 2 \to \mathrm{Fin}\; 2$ 满足对所有 $g \in \mathrm{Fin}\; m$ 均有 $\tau(g) = T(O(g), N(g))$。则对每个主体 $k \in \{0, 1\}$, $$v_u(\tau^{-1}(k)) = \sum_{a=0}^1 \sum_{b=0}^1 [T(a, b) = k] \sum_{g \in G_{ab}} u(g),$$ 其中若 $T(a, b) = k$ 则 $[T(a, b) = k]$ 等于 1,否则等于 0。 证明。Lean 通过将物品包定义展开为 $\{g \mid \tau(g) = k\}$ 并通过划分 $G_{ab}$ 重写来检验此结论。

利用引理 2,由转移表 $T$ 控制的任何分配 $\tau$ 的纳什福利和功利福利可表示为:

  • 主体 0 获得的物品包价值为 $V_0 = \sum_{a, b : T(a, b) = 0} v_0(G_{ab})$。
  • 主体 1 获得的物品包价值为 $V_1 = \sum_{a, b : T(a, b) = 1} v_1(G_{ab})$。
  • $\mathrm{nash\_welfare}(v, \tau) = V_0 \cdot V_1$ 且 $\mathrm{utilitarian\_welfare}(v, \tau) = V_0 + V_1$。

对于分配 $N$,转移映射为 $T_N(a, b) = b$:

  • 主体 0 获得 $A \cup B$,其价值为 $V_0 = p + q$。
  • 主体 1 获得 $C \cup D$,其价值为 $V_1 = \gamma + \delta$。
  • 因此 $\mathrm{nash\_welfare}(v, N) = (p + q)(\gamma + \delta)$ 且 $\mathrm{utilitarian\_welfare}(v, N) = (p + q) + (\gamma + \delta)$。

对于分配 $O$,转移映射为 $T_O(a, b) = a$:

  • 主体 0 获得 $A \cup C$,其价值为 $V_0 = p + r$。
  • 主体 1 获得 $B \cup D$,其价值为 $V_1 = \beta + \delta$。
  • 因此 $\mathrm{nash\_welfare}(v, O) = (p + r)(\beta + \delta)$ 且 $\mathrm{utilitarian\_welfare}(v, O) = (p + r) + (\beta + \delta)$。

因为 $N$ 满足 is_mnw_allocation,所以对每个分配 $\tau$ 均有 $\mathrm{nash\_welfare}(v, \tau) \le \mathrm{nash\_welfare}(v, N)$。在五个特定的 $\tau$ 选择上代入该不等式可产生五个约束:

1. 选择 $\tau = O$ 给出: $$(p + r)(\beta + \delta) \le (p + q)(\gamma + \delta) \quad (cO).$$ 2. 选择仅给主体 0 分配 $A$ 的 $\tau$(若 $a = 0 \wedge b = 0$ 则 $T(a, b) = 0$,否则为 1),给主体 0 带来的价值为 $p$,给主体 1 带来的价值为 $\beta + \gamma + \delta$: $$p(\beta + \gamma + \delta) \le (p + q)(\gamma + \delta) \quad (cA).$$ 3. 选择仅给主体 0 分配 $C$ 的 $\tau$(若 $a = 0 \wedge b = 1$ 则 $T(a, b) = 0$,否则为 1),给主体 0 带来的价值为 $r$,给主体 1 带来的价值为 $\alpha + \beta + \delta$: $$r(\alpha + \beta + \delta) \le (p + q)(\gamma + \delta) \quad (cC).$$ 4. 选择给主体 0 分配物品包 $A \cup B \cup C$ 的 $\tau$(若 $a = 1 \wedge b = 1$ 则 $T(a, b) = 1$,否则为 0),给主体 0 带来的价值为 $p + q + r$,给主体 1 带来的价值为 $\delta$: $$(p + q + r)\delta \le (p + q)(\gamma + \delta) \quad (cABC).$$ 5. 选择给主体 0 分配物品包 $A \cup C \cup D$ 的 $\tau$(若 $a = 1 \wedge b = 0$ 则 $T(a, b) = 1$,否则为 0),给主体 0 带来的价值为 $p + r + s$,给主体 1 带来的价值为 $\beta$: $$(p + r + s)\beta \le (p + q)(\gamma + \delta) \quad (cACD).$$

这五个不等式连同非负性与归一化,通过核心引理蕴涵了目标不等式。

引理 3(mnw2_core)。设 $p, q, r, s, \alpha, \beta, \gamma, \delta \in \mathbb{R}$ 满足非负性($0 \le p, q, r, s, \alpha, \beta, \gamma, \delta$)、归一化($p + q + r + s = 1$ 与 $\alpha + \beta + \gamma + \delta = 1$)以及五个二次不等式 $cO, cA, cC, cABC, cACD$。则: $$23(p + r + \beta + \delta) \le 27(p + q + \gamma + \delta).$$ 证明。证明根据 $(q, \beta)$ 和 $(\gamma, r)$ 的相对大小分为两种情形:

  • 情形 1:$\beta \le q$ 或 $r \le \gamma$。在这种情形下,括号引理可以直接应用于界定差值 $27(p + q + \gamma + \delta) - 23(p + r + \beta + \delta)$。
  • 情形 2:$\beta > q$ 且 $r > \gamma$。在这种情形下,五个不等式强制成立关系 $p \le \gamma + \delta$ 与 $\delta \le p + q$。在变量的这些界限下,不等式 $27(p + q + \gamma + \delta) - 23(p + r + \beta + \delta) \ge 0$ 通过计算机找到的多项式恒等式进行了代数验证,该恒等式将该差值表示为非负项与假设倍数的和。Lean 通过多项式展开检验该恒等式。

确立了引理 3 后,mnw_two_agents_welfare_le 的证明直接完成:

- 将非负性条件、归一化 $h1, h2$ 以及五个不等式 $cO, cA, cC, cABC, cACD$ 提供给 mnw2_core。 - 引理 3 产生关键不等式: $$23(p + r + \beta + \delta) \le 27(p + q + \gamma + \delta).$$ - 代入 $\mathrm{utilitarian\_welfare}(v, O) = p + r + \beta + \delta$ 与 $\mathrm{utilitarian\_welfare}(v, N) = p + q + \gamma + \delta$,该线性组合即可完成目标证明,得出: $$23 \cdot \mathrm{utilitarian\_welfare}(v, O) \le 27 \cdot \mathrm{utilitarian\_welfare}(v, N).$$

5. 讨论

定理 mnw_two_agents_welfare_le 通过证明上界至多为 $27/23$,与来自 arXiv:1905.04910 的下界 $27/23$ 相匹配,从而解决了两个主体下的最大纳什福利代价。在该结果之前,arXiv:1905.04910 的定理 5.4 确立了两个主体下 MNW 的代价与 MNW 的强代价落在范围 $[27/23, 5/4]$ 内。新的上界改进了 $5/4 = 1.25$,并确定了 MNW 的代价与强代价的确切数值均为 $27/23 \approx 1.1739$。

该界在若干方面表现出很强的性质:

  • 它对任意数量的物品 $m$ 均成立,对实例的规模没有任何限制。
  • 它适用于每个分配 $O$,而不仅仅是最优功利分配 $O^*$。
  • 它对每个满足 is_mnw_allocation 的分配 $N$ 均成立,而不仅是最佳 MNW 分配,这意味着上界 $27/23$ 同样适用于 MNW 的强代价。
  • 该定理依赖于可加、非负且经过归一化的估值,使得每个主体对所有物品集合的估值均为 1。

该结果未涵盖具有 $n \ge 3$ 个主体的实例。对于一般的 $n$,arXiv:1905.04910 证明了 MNW 的代价为 $\Theta(n)$,但确切的主导常数以及关于 $n$ 的紧确函数仍然未知。将此处使用的四组划分推广到 $n$ 个主体将需要根据物品在 $O$ 和 $N$ 下所有者的 $n^2$ 个可能对来进行划分,而一般的物品包交换将涉及 $n^n$ 种配置。

此外,arXiv:1905.04910 考察了其他几种公平性概念。正如 arXiv:1905.04910 的表 1 和第 5 节所强调的,除了 EF1(至多一个物品的无嫉妒)和 MNW 之外,双主体设定下的紧确界已针对所有公平性概念得以确立。随着 MNW 现已解决且确切等于 $27/23$,双主体下 EF1 代价的确切数值仍然是该文献所强调的双主体设定下的未决公开问题。

为什么是研究级成果

  • settles OP-67 (Price of MNW for two agents)

Lean 声明

  • mnw_two_agents_welfare_leFor two agents with additive, nonnegative, normalized valuations (v_i(M) = 1) over any number m of goods, every maximum Nash welfare…
  • mnw2_coreGoods are grouped by their owners under an allocation O and an allocation N: A = (O:0, N:0), B = (O:1, N:0), C = (O:0, N:1), D = (O:1,…
  • mnw_two_agents_price_lower_boundFor every c < 27/23 there are two agents with additive, nonnegative, normalized valuations over three goods and an allocation O such that…
  • utilitarian_welfareUtilitarian social welfare of an allocation σ with additive valuations v_i: SW(σ) = ∑_i v_i(X_i), where X_i is the bundle of agent i under…
  • nash_welfareNash welfare of an allocation σ of m goods to n agents with additive valuations v_i: NW(σ) = ∏_i v_i(X_i), where X_i is the bundle of…
  • is_mnw_allocationAn allocation σ is a maximum Nash welfare (MNW) allocation if no allocation τ has larger Nash welfare. When the maximum Nash welfare is…
  • mnw2_sum_groupsFor allocations O, N of m goods to two agents, item values u and weights c(a, b), ∑_g c(O g, N g) u_g equals ∑_{a,b} c(a, b) · u(G_{ab}),…
  • mnw2_bundle_valueIf τ(g) = T(O g, N g) for a map T : {0,1}² → {0,1}, then the value u(X_k) of agent k's bundle under τ is the sum of the group sums…

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

参考文献

  1. arXiv:1905.04910 — The Price of Fairness for Indivisible Goods

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