基于八顶点图对双智能体连通性价格链接性猜想的反驳
low tier2026-10-06OP-68审阅: Claude CodeEnglish
摘要
在具有可加效用的两个智能体之间的不可分物品公平分配中,物品被建模为连通图 G 的顶点。最大最小份额(MMS)MMS(u, 2) 是智能体在顶点集的所有二划分上所能确保的最大最小效用,而连通最大最小份额(G-MMS)G-MMS(G, u, 2) 则将划分限制在诱导连通子图的划分块上。双智能体连通性价格(PoC)PoC(G, 2) 是 MMS(u, 2) / G-MMS(G, u, 2) 在所有可加估值 u 上的上确界。如果大小分别为 a 和 b 的任意两个不相交终端集都可以扩展到不相交的连通顶点集,则称图是 (a, b)-链接的。arXiv:1908.05433 的猜想 3.10 断言,如果整数 k >= 2 且图 G 满足 G 是 (2, k - 1)-链接但不是 (2, k)-链接的,则 PoC(G, 2) = 2k / (2k - 1)。本文给出了该猜想在 k = 4 时的显式反例,已在 Lean 4 中形式化并得到机器验证。具体而言,存在一个 8 顶点图,它是 (2, 3)-链接但不是 (2, 4)-链接的,却允许一个最大最小份额为 15 且连通最大最小份额至多为 13 的估值。这导致 PoC(G, 2) >= 15/13 > 8/7,从而推翻了预测的比率 8/7。
1. 引言
在智能体之间公平分配不可分物品是离散优化和算法博弈论中的核心课题。在没有拓扑约束的经典设定中,智能体的份额通常通过最大最小份额(MMS)来评估。对于在有限物品集 $V$ 上具有可加效用函数 $u$ 的两个智能体,最大最小份额 $\mathrm{MMS}(u, 2)$ 表示智能体通过将物品划分为两个捆绑包并接收价值较低的捆绑包所能保证的最高效用: $$\mathrm{MMS}(u, 2) = \max_{S \subseteq V} \min(u(S), u(V \setminus S)).$$
在许多实际应用中,由于物品之间存在空间、时间或操作上的关联,物品不能被任意划分。一个自然且被广泛研究的模型将物品放置在无向连通图 $G = (V, E)$ 的顶点上,要求每个分配的捆绑包在 $G$ 中诱导出连通子图。在 arXiv:1908.05433(“The Price of Connectivity in Fair Division”)中引入的这一设定下,连通最大最小份额(G-MMS)$G\text{-}\mathrm{MMS}(G, u, 2)$ 通过将优化限制在二划分 $(T, V \setminus T)$ 上来定义,其中 $T$ 和 $V \setminus T$ 均诱导 $G$ 的连通子图: $$G\text{-}\mathrm{MMS}(G, u, 2) = \max_{\substack{T \subseteq V \\ G[T], G[V \setminus T] \text{ connected}}} \min(u(T), u(V \setminus T)).$$
施加连通性约束所造成的公平性损失通过连通性价格来量化。对于两个智能体,连通性价格 $\mathrm{PoC}(G, 2)$ 定义为在所有非负可加估值 $u$(满足 $G\text{-}\mathrm{MMS}(G, u, 2) > 0$)上该比率的上确界: $$\mathrm{PoC}(G, 2) = \sup_u \frac{\mathrm{MMS}(u, 2)}{G\text{-}\mathrm{MMS}(G, u, 2)}.$$
为了理解 $G$ 的拓扑结构如何决定 $\mathrm{PoC}(G, 2)$,arXiv:1908.05433 研究了图的结构连通性质,重点关注链接性。一个图 $G$ 被定义为 $(a, b)$-链接的,如果对于任意两个满足 $|M_1| = a$ 和 $|M_2| = b$ 的不相交顶点集 $M_1, M_2 \subset V$,均存在不相交集合 $S_1, S_2 \subset V$,使得 $M_1 \subseteq S_1$,$M_2 \subseteq S_2$,且每个 $S_i$ 均诱导 $G$ 的连通子图。
arXiv:1908.05433 的命题 3.9 确立了不是 $(2, k)$-链接的会导致 $\mathrm{PoC}(G, 2) \ge 2k / (2k - 1)$。该猜想在 $k = 2$ 的情形成立(推论 3.6),且该猜想对于完全图减去非空匹配的情形成立(定理 3.11)。
基于这些结果,arXiv:1908.05433 提出了猜想 3.10:
猜想 3.10。设 $k \ge 2$ 为整数,且设 $G$ 是一个为 $(2, k - 1)$-链接但不是 $(2, k)$-链接的图。则 $\mathrm{PoC}(G, 2) = 2k / (2k - 1)$。
本文给出了在 Lean 4 中验证的对猜想 3.10 的形式化反驳。我们考察了一个 8 顶点图 $G$,它是 $(2, 3)$-链接但不是 $(2, 4)$-链接的。对于 $k = 4$,猜想 3.10 预测 $\mathrm{PoC}(G, 2) = 8/7 \approx 1.1429$。然而,我们在顶点上给出了一个显式的可加估值 $u$,使得 $\mathrm{MMS}(u, 2) = 15$ 而 $G\text{-}\mathrm{MMS}(G, u, 2) \le 13$。这表明: $$\mathrm{PoC}(G, 2) \ge \frac{15}{13} \approx 1.1538 > \frac{8}{7},$$ 从而反驳了该猜想。所有定义、引理以及主定理 poc_linkedness_conjecture_counterexample 均已在 Lean 4 中形式化并得到机器验证。
2. 预备知识
我们遵循其 Lean 形式化来阐述设定和定义。在全文中,图均为简单无向图。
定义 1(is_connected_vertex_set)。设 $G = (V, E)$ 为简单图,且设 $S \subseteq V$ 为顶点集。如果诱导子图 $G[S]$ 是连通的,则集合 $S$ 是 $G$ 中的连通顶点集: $$\mathrm{is\_connected\_vertex\_set}(G, S) \iff G[S] \text{ is connected}.$$ 注:在 Lean 中,这是通过诱导子图连通来定义的。在 Mathlib 的约定下,连通图必须具有非空顶点类型。因此,is_connected_vertex_set 蕴含 $S$ 是非空的。
定义 2(is_ab_linked)。设 $G = (V, E)$ 为简单图,且设 $a, b \in \mathbb{N}$。如果对于满足 $|M_1| = a$ 和 $|M_2| = b$ 的每对不相交有限子集 $M_1, M_2 \subset V$,均存在不相交子集 $S_1, S_2 \subseteq V$,使得 $M_1 \subseteq S_1$,$M_2 \subseteq S_2$,且 $S_1$ 和 $S_2$ 都是 $G$ 中的连通顶点集,则图 $G$ 是 $(a, b)$-链接的: $$\mathrm{is\_ab\_linked}(G, a, b) \iff \forall M_1, M_2 \subseteq V, M_1 \cap M_2 = \emptyset \land |M_1| = a \land |M_2| = b \implies \exists S_1, S_2 \subseteq V, S_1 \cap S_2 = \emptyset \land M_1 \subseteq S_1 \land M_2 \subseteq S_2 \land \mathrm{is\_connected\_vertex\_set}(G, S_1) \land \mathrm{is\_connected\_vertex\_set}(G, S_2).$$ 注:在 Lean 中,终端集 $M_1$ 和 $M_2$ 的类型为有限集,而扩展子集 $S_1$ 和 $S_2$ 的类型为 $V$ 的子集。
定义 3(公平分配估值与份额)。设 $V$ 为有限物品集($G$ 的顶点)。可加估值是一个函数 $u : V \to \mathbb{R}_{\ge 0}$,通过 $u(S) = \sum_{v \in S} u(v)$ 扩展到子集。对于两个智能体:
- 最大最小份额为 $\mathrm{MMS}(u, 2) = \max_{S \subseteq V} \min(u(S), u(V \setminus S))$。
- 连通最大最小份额为 $G\text{-}\mathrm{MMS}(G, u, 2) = \max_{T} \min(u(T), u(V \setminus T))$,其中最大值取遍所有使得 $T$ 和 $V \setminus T$ 均为 $G$ 中连通顶点集的 $T \subseteq V$。
- $G$ 的双智能体连通性价格为 $\mathrm{PoC}(G, 2) = \sup_u \frac{\mathrm{MMS}(u, 2)}{G\text{-}\mathrm{MMS}(G, u, 2)}$。
定义 4(poc8_graph)。图 poc8_graph 是在顶点集 $\mathrm{Fin}\; 8 = \{0, 1, 2, 3, 4, 5, 6, 7\}$ 上的简单图,具有以下 18 条无向边: - 来自 0:$\{0, 4\}, \{0, 5\}, \{0, 6\}, \{0, 7\}$, - 来自 1:$\{1, 3\}, \{1, 5\}, \{1, 6\}, \{1, 7\}$, - 来自 2:$\{2, 3\}, \{2, 4\}, \{2, 6\}, \{2, 7\}$, - 来自 3:$\{3, 6\}, \{3, 7\}$, - 来自 4:$\{4, 5\}, \{4, 7\}$, - 来自 5:$\{5, 7\}$, - 来自 6:$\{6, 7\}$。 注:在该图中,顶点 7 是全连接的(与所有其他 7 个顶点相邻)。顶点 6 的度数为 5,与 $\{0, 1, 2, 3, 7\}$ 相邻。顶点 $0, 1, 2, 3, 4, 5$ 的度数均为 4。
定义 5(poc8_u 与 poc8_val)。在 $\mathrm{Fin}\; 8$ 上的反例估值向量 poc8_u 定义为: $$u = (5, 5, 5, 1, 1, 1, 12, 0),$$ 即 $u(0) = u(1) = u(2) = 5$,$u(3) = u(4) = u(5) = 1$,$u(6) = 12$ 以及 $u(7) = 0$。 对于任意布尔选择谓词 $P : \mathrm{Fin}\; 8 \to \mathrm{Bool}$,poc8_val 使用对顶点范围的右折叠计算由 $P$ 选取的顶点的总估值: $$\mathrm{poc8\_val}(P) = \sum_{v \in \mathrm{Fin}\; 8, P(v) = \mathrm{true}} u(v).$$
定义 6(poc8_gmms_ok)。对于布尔谓词 $P : \mathrm{Fin}\; 8 \to \mathrm{Bool}$,检查 poc8_gmms_ok 定义为: $$\mathrm{poc8\_gmms\_ok}(P) = \mathrm{decide}(8 \cdot \min(\mathrm{poc8\_val}(P), \mathrm{poc8\_val}(\neg P)) < 105) \lor \mathrm{poc8\_discb}(P) \lor \mathrm{poc8\_discb}(\neg P),$$ 其中 poc8_discb 是在顶点集诱导不连通子图时返回 true 的布尔测试。 注:条件 $8 \cdot \min(u(P), u(\neg P)) < 105$ 测试较小捆绑包的价值是否至多为 13:因为效用是整数,$8 \times 13 = 104 < 105$,而 $8 \times 14 = 112 \ge 105$。
3. 主要结果
主定理通过在 $k = 4$ 时反驳 arXiv:1908.05433 针对两个智能体的猜想 3.10 解决了该问题。
定理(poc_linkedness_conjecture_counterexample)。存在一个包含 8 个顶点的简单图 $G$,它是 $(2, 3)$-链接但不是 $(2, 4)$-链接的,以及一个非负可加估值 $u : \mathrm{Fin}\; 8 \to \mathbb{R}$ 和一个无约束划分见证 $S = \{0, 1, 2, 7\}$,使得对于每个满足 $T$ 和 $T^c$ 均在 $G$ 中诱导连通子图的子集 $T \subseteq \mathrm{Fin}\; 8$, $$8 \cdot \min\left(\sum_{v \in T} u(v), \sum_{v \in T^c} u(v)\right) < 7 \cdot \min\left(\sum_{v \in S} u(v), \sum_{v \in S^c} u(v)\right).$$
该 Lean 定理断言存在 8 元有限类型 $\mathrm{Fin}\; 8$ 上的简单图 $G$,它对参数 2 和 3 满足 is_ab_linked,而对参数 2 和 4 不满足 is_ab_linked,连同非负实估值 $u : \mathrm{Fin}\; 8 \to \mathbb{R}$ 和有限子集 $S$,使得对于每个有限子集 $T$,只要 $T$ 及其补集 $T^c$ 均满足 is_connected_vertex_set,$T$ 对应划分块价值的最小值的 8 倍就严格小于 $S$ 对应划分块价值的最小值的 7 倍。
为了理解为什么这推翻了猜想 3.10: 1. 无约束划分 $S = \{0, 1, 2, 7\}$ 满足 $u(S) = 5 + 5 + 5 + 0 = 15$ 且 $u(S^c) = u(\{3, 4, 5, 6\}) = 1 + 1 + 1 + 12 = 15$。因此: $$\mathrm{MMS}(u, 2) \ge \min(u(S), u(S^c)) = 15.$$ 2. 定理确立了对于每个连通二划分 $(T, T^c)$, $$8 \cdot \min(u(T), u(T^c)) < 7 \times 15 = 105.$$ 由于效用是整数,这蕴含 $\min(u(T), u(T^c)) \le 13$,从而: $$G\text{-}\mathrm{MMS}(G, u, 2) \le 13.$$ 3. 因此 $G$ 的双智能体连通性价格满足: $$\mathrm{PoC}(G, 2) \ge \frac{\mathrm{MMS}(u, 2)}{G\text{-}\mathrm{MMS}(G, u, 2)} \ge \frac{15}{13} \approx 1.1538.$$ 4. 对于 $k = 4$,猜想 3.10 预测任何为 $(2, 3)$-链接但不是 $(2, 4)$-链接的图必须具有: $$\mathrm{PoC}(G, 2) = \frac{2k}{2k - 1} = \frac{8}{7} \approx 1.1429.$$ 因为 $15/13 > 8/7$(由于 $15 \times 7 = 105 > 104 = 8 \times 13$),图 $G$ 推翻了猜想 3.10。
每个辅助引理都为结果贡献了具体组成部分:
poc8_graph定义了 8 顶点反例图。poc8_linked_two_three形式化确认了 $(2, 3)$-链接性的肯定条件。poc8_not_linked_two_four形式化确认了 $(2, 4)$-链接性不成立。poc8_gmms_check验证了 8 个顶点的所有 256 个二划分要么在一侧诱导不连通子图,要么产生的较小块价值严格低于 $105/8$。poc8_discb_sound确保布尔不连通性谓词反映了图连通性的拓扑定义。poc8_val_eq将捆绑包的计算评估等同于实数上的有限集求和。
theorem poc_linkedness_conjecture_counterexample :
∃ G : SimpleGraph (Fin 8), is_ab_linked G 2 3 ∧ ¬ is_ab_linked G 2 4 ∧
∃ u : Fin 8 → ℝ, (∀ v, 0 ≤ u v) ∧ ∃ S : Finset (Fin 8), ∀ T : Finset (Fin 8),
is_connected_vertex_set G (↑T : Set (Fin 8)) →
is_connected_vertex_set G (↑(Tᶜ) : Set (Fin 8)) →
8 * min (∑ v ∈ T, u v) (∑ v ∈ Tᶜ, u v) < 7 * min (∑ v ∈ S, u v) (∑ v ∈ Sᶜ, u v)4. 证明
该证明通过表明 poc8_graph 满足 $k = 4$ 时的链接性前提同时超过了预测的连通性价格,从而推翻了 arXiv:1908.05433 的猜想 3.10。论证分为三个主要部分:
- 验证
poc8_graph是 $(2, 3)$-链接但不是 $(2, 4)$-链接的。 - 证明对于估值
poc8_u,无约束最大最小份额为 15,而每个连通二划分给予较贫穷智能体的价值至多为 13。 - 在 Lean 中结合这些事实以推导出
poc_linkedness_conjecture_counterexample中的严格不等式。
我们首先给出链接性的否定结果。
引理 1(poc8_not_linked_two_four)。图 poc8_graph 不是 $(2, 4)$-链接的: $$\neg\, \mathrm{is\_ab\_linked}(\mathrm{poc8\_graph}, 2, 4).$$
证明。我们在 $\mathrm{Fin}\; 8$ 中选取终端集 $M_1 = \{0, 1\}$ 与 $M_2 = \{2, 5, 6, 7\}$。显然 $|M_1| = 2$,$|M_2| = 4$,且 $M_1 \cap M_2 = \emptyset$。假设存在不相交集合 $S_1, S_2 \subseteq \mathrm{Fin}\; 8$,使得 $M_1 \subseteq S_1$,$M_2 \subseteq S_2$,并且 $S_1$ 和 $S_2$ 都是 poc8_graph 中的连通顶点集。
由于 $S_1$ 与 $S_2$ 不相交且 $M_2 \subseteq S_2$,$S_1$ 必须包含在 $M_2$ 的补集中: $$S_1 \subseteq \mathrm{Fin}\; 8 \setminus \{2, 5, 6, 7\} = \{0, 1, 3, 4\}.$$ 我们现在考察 poc8_graph 由 $\{0, 1, 3, 4\}$ 诱导的子图。根据定义 4,poc8_graph 的边为: - 0 的邻居为 $\{4, 5, 6, 7\}$,因此 0 在 $\{0, 1, 3, 4\}$ 中的唯一邻居是 4。 - 1 的邻居为 $\{3, 5, 6, 7\}$,因此 1 在 $\{0, 1, 3, 4\}$ 中的唯一邻居是 3。 - 3 的邻居为 $\{1, 2, 6, 7\}$,因此 3 在 $\{0, 1, 3, 4\}$ 中的唯一邻居是 1。 - 4 的邻居为 $\{0, 2, 5, 7\}$,因此 4 在 $\{0, 1, 3, 4\}$ 中的唯一邻居是 0。
因此,在 $\{0, 1, 3, 4\}$ 上的诱导子图恰好包含两条边:$\{0, 4\}$ 和 $\{1, 3\}$。特别地,没有连接 $\{0, 4\}$ 与 $\{1, 3\}$ 的边。该诱导子图的连通分支恰为 $\{0, 4\}$ 和 $\{1, 3\}$。
由于 $M_1 = \{0, 1\} \subseteq S_1$,$S_1$ 包含 $0 \in \{0, 4\}$ 和 $1 \in \{1, 3\}$。因为在 $\{0, 1, 3, 4\}$ 中 0 和 1 之间不存在路径,所以 $\{0, 1, 3, 4\}$ 中任何同时包含 0 和 1 的子集都是不连通的。因此 $S_1$ 不能是连通顶点集,产生矛盾。Lean 在 poc8_not_linked_two_four 中解决了该引理。
接下来,我们确立链接性的肯定性质。
引理 2(poc8_linked_two_three)。图 poc8_graph 是 $(2, 3)$-链接的: $$\mathrm{is\_ab\_linked}(\mathrm{poc8\_graph}, 2, 3).$$
证明。我们必须证明,对于任意满足 $|M_1| = 2$ 和 $|M_2| = 3$ 的不相交集合 $M_1, M_2 \subset \mathrm{Fin}\; 8$,存在分别包含 $M_1$ 和 $M_2$ 的不相交子集 $S_1, S_2$,使得二者均诱导连通子图。
需要检查的对 $(M_1, M_2)$ 的数量为: $$\binom{8}{2} \times \binom{6}{3} = 28 \times 20 = 560.$$ Lean 证明通过对所有 560 种配置进行穷举求值来解决此问题。在结构上,poc8_graph 具有高度连通性:顶点 7 与所有其他 7 个顶点相邻,顶点 6 与 $\{0, 1, 2, 3, 7\}$ 相邻。划分中包含顶点 7 的一侧可以立即将 7 用作星形中心来连接其终端,而其余顶点具有足够的边密度(例如边 $\{0, 4\}, \{0, 5\}, \{1, 3\}, \{2, 3\}, \{4, 5\}$ 以及通过 6 的连接)来跨越另一终端集。Lean 在 poc8_linked_two_three 中验证了此穷举检查。
我们现在转向公平分配的计算。
引理 3(poc8_discb_sound)。对于任意布尔谓词 $S : \mathrm{Fin}\; 8 \to \mathrm{Bool}$,若 $\mathrm{poc8\_discb}(S) = \mathrm{true}$,则集合 $\{x \mid S(x) = \mathrm{true}\}$ 不诱导 poc8_graph 的连通子图: $$\mathrm{poc8\_discb}(S) = \mathrm{true} \implies \neg\, \mathrm{is\_connected\_vertex_set}(\mathrm{poc8\_graph}, \{x \mid S(x) = \mathrm{true}\}).$$
证明。布尔函数 poc8_discb 通过可达性计算诱导子图的连通分支并测试非空性。引理 poc8_discb_sound 形式化了该判定过程的正确性。
引理 4(poc8_val_eq)。对于任意谓词 $P : \mathrm{Fin}\; 8 \to \mathrm{Bool}$,折叠值 poc8_val 与过滤后的有限集上的实数求和一致: $$(\mathrm{poc8\_val}(P) : \mathbb{R}) = \sum_{v \in \{x \in \mathrm{Fin}\; 8 \mid P(x) = \mathrm{true}\}} (u(v) : \mathbb{R}).$$
证明。这是通过对 $\mathrm{Fin}\; 8$ 全集中的顶点列表进行归纳来验证的,确立了列表上的折叠与有限集求和一致。
引理 5(poc8_gmms_check)。每个二划分 $P : \mathrm{Fin}\; 8 \to \mathrm{Bool}$ 都通过该检查: $$\forall P : \mathrm{Fin}\; 8 \to \mathrm{Bool},\; \mathrm{poc8\_gmms\_ok}(P) = \mathrm{true}.$$
证明。存在 $2^8 = 256$ 个可能的函数 $P : \mathrm{Fin}\; 8 \to \mathrm{Bool}$。在 Lean 中,此检查通过 poc8_gmms_check 中的决策求值来解决。
为了通过手动推导理解为什么没有连通二划分能取得大于 13 的最小值,设 $u = (5, 5, 5, 1, 1, 1, 12, 0)$。所有效用的总和为: $$5 + 5 + 5 + 1 + 1 + 1 + 12 + 0 = 30.$$ 反设存在二划分 $(T, T^c)$ 使得 $T$ 和 $T^c$ 在 poc8_graph 中均连通且 $\min(u(T), u(T^c)) \ge 14$。由于总和为 30,价值对 $(u(T), u(T^c))$ 必须是 $(14, 16)$ 或 $(15, 15)$ 之一。
顶点 6 的效用为 12。不妨设 $6 \in T$。则 $u(T \setminus \{6\}) = u(T) - 12 \in \{2, 3, 4\}$。 除 6 之外的顶点的效用为: - $u(0) = u(1) = u(2) = 5$, - $u(3) = u(4) = u(5) = 1$, - $u(7) = 0$。
由于 $\{0, 1, 2\}$ 中每个顶点的效用均为 5,它们都不能在 $T$ 中。因此 $T \setminus \{6\} \subseteq \{3, 4, 5, 7\}$。来自 $\{3, 4, 5, 7\}$ 的最大可能总和为 $1 + 1 + 1 + 0 = 3$。因此:
- $u(T \setminus \{6\})$ 不能是 4,所以 $u(T)$ 不能是 16。
- 由此 $u(T)$ 必须是 14 或 15,且 $T \setminus \{6\}$ 由来自 $\{3, 4, 5\}$ 的两个或三个顶点组成,若 $7 \in T$ 则连同 7 一起。
我们分析顶点 7 的位置:
情形 A:$7 \in T$。 则 $7 \notin T^c$,所以 $T^c \subseteq \{0, 1, 2, 3, 4, 5\}$。因为 $\{0, 1, 2\} \cap T = \emptyset$,所以有 $\{0, 1, 2\} \subseteq T^c$。此外,由于 $T$ 至少包含 $\{3, 4, 5\}$ 中的两个顶点,$T^c$ 至多包含 $\{3, 4, 5\}$ 中的一个顶点。 在 poc8_graph 中,$\{0, 1, 2\}$ 之间不存在边:$\{0, 1, 2\}$ 是一个独立集。$T^c$ 中唯一可能的边必须经过单个顶点 $v \in T^c \cap \{3, 4, 5\}$: - 若 $v = 3$,3 的邻居为 $\{1, 2, 6, 7\}$。由于 $0 \notin \{1, 2, 6, 7\}$,顶点 0 在 $T^c$ 中的度数为 0。 - 若 $v = 4$,4 的邻居为 $\{0, 2, 5, 7\}$。由于 $1 \notin \{0, 2, 5, 7\}$,顶点 1 在 $T^c$ 中的度数为 0。 - 若 $v = 5$,5 的邻居为 $\{0, 1, 4, 7\}$。由于 $2 \notin \{0, 1, 4, 7\}$,顶点 2 在 $T^c$ 中的度数为 0。 - 若 $T^c \cap \{3, 4, 5\} = \emptyset$,则 $T^c = \{0, 1, 2\}$,其中根本没有边。 在每种子情形下,$T^c$ 都有一个孤立顶点且 $|T^c| \ge 3$,因此 $T^c$ 是不连通的。
情形 B:$7 \notin T$(从而 $7 \in T^c$)。 则 $T \subseteq \{3, 4, 5, 6\}$ 且 $6 \in T$。 6 在 poc8_graph 中的邻居为 $\{0, 1, 2, 3, 7\}$。6 在 $\{3, 4, 5\}$ 中的唯一邻居是顶点 3;6 与 4 或 5 均不相邻。 - 若 $3 \notin T$,则 6 在 $T$ 中没有邻居,因此 6 是 $T$ 中的孤立顶点。由于 $|T| \ge 3$,$T$ 是不连通的。 - 若 $3 \in T$,则 $T$ 包含 6、3 以及 $\{4, 5\}$ 中至少一个顶点。4 的邻居为 $\{0, 2, 5, 7\}$(与 3 或 6 均不相邻)。5 的邻居为 $\{0, 1, 4, 7\}$(与 3 或 6 均不相邻)。因此,在 poc8_graph 中,$\{3, 6\}$ 与 $\{4, 5\}$ 之间不存在边。从而 $T$ 中来自 $\{4, 5\}$ 的任何顶点都无法与 $\{3, 6\}$ 连通。因此 $T$ 是不连通的。
在每种情形下,$T$ 或 $T^c$ 之一是不连通的。因此,没有连通二划分能取得 14 或更大的最小值。所以,对于每个连通二划分 $(T, T^c)$: $$8 \cdot \min(u(T), u(T^c)) \le 8 \times 13 = 104 < 105.$$ 这完成了引理 5 的手动验证。
我们现在完成主定理的证明。
poc_linkedness_conjecture_counterexample 的证明。 我们实例化: - 图 $G$ 为 poc8_graph。 - 链接性条件通过 poc8_linked_two_three 和 poc8_not_linked_two_four。 - 估值 $u$ 通过将 poc8_u 转换为 $\mathbb{R}$,它是非负的,因为所有分量都是自然数。 - 无约束划分见证 $S = \{0, 1, 2, 7\}$。
我们计算 $S$ 与 $S^c = \{3, 4, 5, 6\}$ 的价值: $$u(S) = u(0) + u(1) + u(2) + u(7) = 5 + 5 + 5 + 0 = 15,$$ $$u(S^c) = u(3) + u(4) + u(5) + u(6) = 1 + 1 + 1 + 12 = 15.$$ 因此 $\min(u(S), u(S^c)) = 15$,且 $7 \cdot \min(u(S), u(S^c)) = 7 \times 15 = 105$。在 Lean 中,这是在 poc8_val 上求值并通过 poc8_val_eq 转化为实数求和的。
设 $T \subseteq \mathrm{Fin}\; 8$ 为任意满足 $T$ 和 $T^c$ 均在 poc8_graph 中诱导连通子图的子集(假设 $hT$ 和 $hTc$)。 我们将 poc8_gmms_check 应用于 $P = \lambda v, \mathrm{decide}(v \in T)$。检查 poc8_gmms_ok 产生三路析取: 1. $8 \cdot \min(\mathrm{poc8\_val}(P), \mathrm{poc8\_val}(\neg P)) < 105$。 根据 poc8_val_eq,$\mathrm{poc8\_val}(P) = \sum_{v \in T} u(v)$ 且 $\mathrm{poc8\_val}(\neg P) = \sum_{v \in T^c} u(v)$。 将不等式转换为 $\mathbb{R}$ 给出: $$8 \cdot \min\left(\sum_{v \in T} u(v), \sum_{v \in T^c} u(v)\right) < 105 = 7 \cdot \min\left(\sum_{v \in S} u(v), \sum_{v \in S^c} u(v)\right),$$ 这证明了目标。 2. 不连通性测试在 $P$ 上返回 true。 根据 poc8_discb_sound,$T$ 不是连通顶点集,与 $hT$ 矛盾。 3. 不连通性测试在 $\neg P$ 上返回 true。 根据 poc8_discb_sound,$T^c$ 不是连通顶点集,与 $hTc$ 矛盾。
在所有情形下结果均成立,从而完成了 poc_linkedness_conjecture_counterexample 的证明。
5. 讨论
poc_linkedness_conjecture_counterexample 的形式化验证通过表明 arXiv:1908.05433 中的猜想 3.10 一般并不成立,从而解决了该猜想的状态。具体而言,该猜想在 $k = 4$ 时不成立。
为了理解这一结果与一般理论的关系,回顾 arXiv:1908.05433 中的命题 3.9 确立了:只要图 $G$ 不是 $(2, k)$-链接的,连通性价格就有下界: $$\mathrm{PoC}(G, 2) \ge \frac{2k}{2k - 1}.$$ 猜想 3.10 背后的直觉是,$(2, k - 1)$-链接性的肯定条件会同时充当上界,防止无约束与连通公平分配之间的差距扩大到超过 $2k / (2k - 1)$。这一直觉在 arXiv:1908.05433 的推论 3.6 中对 $k = 2$ 得到了证实,其中猜想成立:如果 $G$ 是 $(2, 1)$-链接但不是 $(2, 2)$-链接的,则 $\mathrm{PoC}(G, 2) = 4/3$。此外,arXiv:1908.05433 的定理 3.11 证明了该猜想对于完全图减去非空匹配的情形成立。
8 顶点图 poc8_graph 表明对于 $k = 4$,$(2, 3)$-链接性不足以强制施加上界 $8/7$。通过将估值集中在度数为 5 的高权重顶点上,并将低权重独立顶点与高权重子集隔离,该图迫使任何实现均衡划分的连通二划分将其中的一侧断开。因此,连通最大最小份额不能超过 13,产生的比率至少为 $15/13 \approx 1.1538$,严格超过了 $8/7 \approx 1.1429$。
该形式化结果留下了在该问题背景下确定的几个自然疑问:
1. 猜想 3.10 对 $k = 3$ 是否成立?虽然 $k = 2$ 的情形为真且 $k = 4$ 现已被推翻,但中间情形 $k = 3$(其中猜想预测连通性价格为 $6/5 = 1.2$)仍未解决。
2. 对于 poc8_graph,$\mathrm{PoC}(G, 2)$ 的确切值是多少?估值 poc8_u 证明了连通性价格至少为 $15/13$。在所有该图上的可加估值中,$15/13$ 是否是确切的上确界,或者是否存在另一个估值达到严格更大的比率,仍然是一个未决问题。
3. 哪些图论结构性质能正确刻画 $\mathrm{PoC}(G, 2)$?鉴于完全图减去匹配满足公式 $2k / (2k - 1)$ 但一般图不满足,寻找在一般拓扑中支配连通性价格的确切图不变量仍然是一个开放问题。
为什么是研究级成果
- refutes OP-68 (Linkedness and the two-agent price of connectivity)
Lean 声明
- poc_linkedness_conjecture_counterexampleCounterexample to arXiv:1908.05433 Conjecture 3.10 for two agents: there is a graph G on 8 vertices that is (2,3)-linked but not…
- is_connected_vertex_setA vertex set S of a graph G is connected if the subgraph of G induced by S is connected (in particular S is nonempty).
- is_ab_linkedA graph G is (a,b)-linked if for any disjoint vertex sets M1, M2 with |M1| = a and |M2| = b there are disjoint vertex sets S1 ⊇ M1 and S2…
- poc8_graphThe 8-vertex graph G with edges 04, 05, 06, 07, 13, 15, 16, 17, 23, 24, 26, 27, 36, 37, 45, 47, 57, 67.
- poc8_uThe valuation u = (5, 5, 5, 1, 1, 1, 12, 0) on the eight vertices.
- poc8_valThe total u-value of the vertex set selected by P, computed by a fold.
- poc8_gmms_okCheck for a bipartition (P, not P): 8 times the smaller part value is below 105 = 7·15, or one of the two parts is disconnected.
- poc8_linked_two_threeThe 8-vertex graph G is (2,3)-linked: any 2 terminals and 3 further terminals are separated by a connected bipartition of G.
- poc8_not_linked_two_fourG is not (2,4)-linked: for M1 = {0,1} and M2 = {2,5,6,7}, any S1 ⊇ M1 disjoint from S2 ⊇ M2 lies in {0,1,3,4}, and {0,4} is cut off from…
- poc8_gmms_checkEvery bipartition (P, not P) of the eight vertices passes the bipartition check.
- poc8_discb_soundIf the Boolean disconnectedness test accepts S, then S does not induce a connected subgraph of G.
- poc8_val_eqThe folded value agrees with the real sum of u over the selected vertices.
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
参考文献
- arXiv:1908.05433 — The Price of Connectivity in Fair Division
由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。