46个顶点的无权三色最大割博弈中五步强偏离环的存在性
low tier2026-11-02审阅: Claude CodeEnglish
摘要
在最大 $k$ 割(Max-$k$-Cut)博弈中,局中人对应于无向图的顶点,并通过选择 $k$ 种颜色之一来最大化关联割边的数量。虽然在无权图中个体最佳应对(BR)动态总是通过割权重势函数收敛到纳什均衡(NE),但联盟稳定性的表现却有所不同。在加权 Max-$k$-Cut 博弈中,已知存在有利可图的联盟偏离环,而 arXiv:1810.09278 讨论了无权图是否容许强势函数;其环(命题 2)使用了加权边。本文给出了一个包含 46 个顶点的显式无权简单图以及一个由五个 3-染色配置组成的序列,该序列构成了一个有利可图的联盟偏离的有向闭环。在每次转移中,每个改变颜色的顶点都严格增加了其效用(定义为被分配不同颜色的邻点数量)。该环在跨越四个各含 8 个顶点的核心块的 32 局中人协调偏离与四个每次各 8 名局中人的单块依次偏离之间交替进行,并由两个固定的 7 顶点锚块维持稳定。这确立了在五步后返回初始染色的强偏离周期序列的存在性,排除了无权三色最大割博弈中针对有利可图联盟偏离的任何强势函数的存在性。该构造、效用计算以及周期性重现在 Lean 4 中已在定理 maxcut_unweighted_strong_deviation_cycle_exists 下得到形式化验证。
1. 引言
定义在图上的策略博弈为研究去中心化协调、资源分配和局部交互提供了标准框架。在研究最充分的模型中包括 Max-$k$-Cut 博弈,其中局中人与无向图 $G = (V, E)$ 的顶点等同,且每位局中人从包含 $k$ 种可用颜色的调色板中独立选择一个动作。每位局中人的效用由端点被赋予不同颜色的关联边数量决定——即与该顶点关联的割边数量。
当局中人单独偏离时,Max-$k$-Cut 博弈是精确势博弈。标准的势函数是染色的总割权重,定义为割边集的基数。由于使局中人效用严格增加的每次单方偏离也会使总割权重严格增加相同的量,因此个体最佳应对和更优应对动态在任何有限图上都是严格无环的。特别是,从任何初始颜色配置出发,任何有利可图的个体偏离序列必在有限步内终止于纯纳什均衡(PNE)。
然而,个体稳定性并不意味着对联盟偏离的稳定性。在许多社会、经济和计算环境中,局中人的子集可以协调它们的动作以实现互利的成果。对于从染色 $\sigma$ 到染色 $\tau$ 的转变,若 $\tau$ 保持 $S$ 之外的所有非成员的颜色不变,且 $S$ 的每位成员在 $\tau$ 下相比于 $\sigma$ 都严格提高了其个体效用,则称联盟 $S \subseteq V$ 拥有有利可图的强偏离。没有任何联盟拥有此类偏离的颜色配置称为强纳什均衡(SNE)。
与个体偏离不同,协调的联盟行动可以在严格增加每位参与局中人效用的同时,导致图的总割权重发生净减少。因此,一旦允许联盟偏离,割权重便不再能作为势函数。这种分歧引发了一个基本的结构性问题:有利可图的联盟偏离序列是否总是终止,抑或联盟动态是否可能无限循环?
在加权图的设定下(其中每条边带有正实数权重,局中人的效用是关联割边权重的总和),联盟动态确实可以循环。具体而言,arXiv:1810.09278 的命题 2 构造了一个加权图并展示了一个有利可图联盟偏离的显式环。由于此类环中的每一步都严格增加了所有偏离局中人的效用,环的存在立即排除了任何广义强势函数的存在性——即在状态空间上沿所有有利可图联盟偏离严格递增的任何实值函数。
arXiv:1810.09278 还讨论了强势函数是否可能存在于所有边均具有单位权重的无权 Max-$k$-Cut 博弈中。在无权图中,离散组合结构对邻点计数和效用差施加了刚性约束,这使得环可能是边权重的特有产物的可能性依然存在。关于无权 Max-$k$-Cut 博弈中联盟稳定性、社会最优性以及强均衡存在性的相关问题在 arXiv:2610.04948 的第 4 节中进行了探讨。
本文给出了一个经过验证的构造,回答了关于无权博弈中强势函数的问题。我们展示了一个包含 46 个顶点的无权简单图以及由五个 3-染色组成的序列,该序列形成了一个有利可图联盟偏离的有向闭环。在环的每一步中,偏离联盟恰好由改变颜色的顶点组成,且联盟中的每一位成员都获得了严格更大的效用。周期性地重复该环会产生一个无限的强偏离序列,每五步返回初始构型一次。
该构造排除了无权三色最大割博弈中针对所有有利可图联盟偏离的强势函数的存在性。完整的证明,包括 46 顶点图的结构定义、所有五个阶段中所有效用增量的验证、以及提升到无限周期序列,已在 Lean 4 中形式化并验证为 maxcut_unweighted_strong_deviation_cycle_exists。
2. 预备知识
我们考虑在有限无向简单图上进行的 Max-$k$-Cut 博弈。形式上,设 $V$ 为具有可判定相等性的有限类型,设 $G$ 为 $V$ 上具有可判定邻接关系的简单图,设 $k$ 为表示可用颜色数量的正整数,由标准有限类型 $\text{Fin } k = \{0, 1, \dots, k-1\}$ 索引。
定义 1(最大割效用)。设 $G$ 为 $V$ 上的简单图,设 $k \ge 1$,设 $\sigma : V \to \text{Fin } k$ 为颜色配置。顶点 $v \in V$ 在 $\sigma$ 下的效用定义为分配有不同于 $\sigma(v)$ 的颜色的 $v$ 的邻点数量: $$u_v(\sigma) = |\{w \in V : G.\text{Adj}(v, w) \land \sigma(w) \ne \sigma(v)\}|.$$ 等价地,记 $\deg(v)$ 为 $v$ 在 $G$ 中的度数,效用满足 $u_v(\sigma) = \deg(v) - |\{w \in V : G.\text{Adj}(v, w) \land \sigma(w) = \sigma(v)\}|$,因此最大化效用等价于最小化同色邻点的数量。
定义 2(is_maxcut_strong_deviation)。设 $G$ 为 $V$ 上的简单图,设 $\sigma, \tau : V \to \text{Fin } k$ 为两个颜色配置。非空子集 $S \subseteq V$ 是从 $\sigma$ 到 $\tau$ 的强偏离,在 $G$、$\sigma$、$S$ 和 $\tau$ 上记作 is_maxcut_strong_deviation,如果:
- $S$ 非空;
- $\tau$ 在 $S$ 之外的所有顶点上与 $\sigma$ 一致:对所有 $v \in V$,$v \notin S \implies \tau(v) = \sigma(v)$;以及
- $S$ 中的每位局中人均严格增加其效用:对所有 $v \in S$,$u_v(\sigma) < u_v(\tau)$。
关于定义选择的说明。Lean 中的定义对 $S$ 的每位成员强制要求严格不等式($<$);弱改进是不够的。在下文的循环偏离定理中,联盟 $S$ 被选为恰好改变其颜色的顶点集,$S = \{v \in V : \tau(v) \ne \sigma(v)\}$。如 arXiv:1810.09278 中所述,要求每个偏离局中人改变策略对于联盟稳定性是不失一般性的。
定义 3(maxcut_cycle46_graph)。图 maxcut_cycle46_graph 是顶点集 $V = \text{Fin } 46 = \{0, 1, \dots, 45\}$ 上的无权简单图,通过二元关系 $R(u, v)$ 的对称和反自反闭包定义。这 46 个顶点被划分为六个不相交的块: - 四个核心块 $B_0, B_1, B_2, B_3$,每个包含 8 个顶点: $$B_0 = \{0, \dots, 7\}, \quad B_1 = \{8, \dots, 15\}, \quad B_2 = \{16, \dots, 23\}, \quad B_3 = \{24, \dots, 31\}.$$ - 两个锚块 $A_0, A_1$,每个包含 7 个顶点: $$A_0 = \{32, \dots, 38\}, \quad A_1 = \{39, \dots, 45\}.$$
关系 $R(u, v)$ 是八个条件的析取:
- $u < 8 \land 16 \le v < 24 \land (v - 16 + 8 - u) \pmod 8 < 2$;
- $u < 8 \land 24 \le v < 32$;
- $u < 8 \land 39 \le v$;
- $8 \le u < 16 \land 16 \le v < 24 \land (v - 16 + 8 - (u - 8)) \pmod 8 < 4$;
- $8 \le u < 16 \land 24 \le v < 32 \land 2 \le (v - 24 + 8 - (u - 8)) \pmod 8$;
- $8 \le u < 16 \land v = 32$;
- $16 \le u < 24 \land v = 39$;
- $24 \le u < 32 \land 32 \le v < 39$。
maxcut_cycle46_graph 的邻接关系是对称、反自反闭包:$x \sim y \iff (R(x, y) \lor R(y, x)) \land x \ne y$。
关于定义选择的说明。在定义 $R(u, v)$ 的八个子句中的每一个中,$u$ 的数值范围都严格小于 $v$ 的范围。因此,$R$ 不包含对角线对 $(u, u)$,并且同一块中没有两个顶点是相关的。六个块中的每一个在 maxcut_cycle46_graph 中都形成独立集。
定义 4(maxcut_cycle46_coloring)。对于每个阶段 $s \in \text{Fin } 5 = \{0, 1, 2, 3, 4\}$,染色配置 $\sigma_s : \text{Fin } 46 \to \text{Fin } 3$ 由 maxcut_cycle46_coloring s 定义,按块分配 $\{0, 1, 2\}$ 中的颜色:
- 对于 $v \in B_0$:若 $s = 0$ 则 $\sigma_s(v) = 0$,若 $s \in \{1, 2, 3, 4\}$ 则 $\sigma_s(v) = 2$;
- 对于 $v \in B_1$:若 $s \in \{0, 3, 4\}$ 则 $\sigma_s(v) = 1$,若 $s \in \{1, 2\}$ 则 $\sigma_s(v) = 0$;
- 对于 $v \in B_2$:若 $s \in \{0, 4\}$ 则 $\sigma_s(v) = 2$,若 $s \in \{1, 2, 3\}$ 则 $\sigma_s(v) = 1$;
- 对于 $v \in B_3$:若 $s = 1$ 则 $\sigma_s(v) = 1$,若 $s \in \{0, 2, 3, 4\}$ 则 $\sigma_s(v) = 0$;
- 对于 $v \in A_0$:对所有阶段 $s \in \text{Fin } 5$ 均有 $\sigma_s(v) = 1$;
- 对于 $v \in A_1$:对所有阶段 $s \in \text{Fin } 5$ 均有 $\sigma_s(v) = 2$。
关于定义选择的说明。锚块 $A_0$ 和 $A_1$ 在所有阶段都被分配了恒定颜色,这意味着锚顶点从不改变颜色。阶段索引属于有限类型 $\text{Fin } 5$,阶段转移按模 5 加法计算,因此阶段 4 的后继为阶段 0。
3. 主要结果
主定理确立了一个包含 46 个顶点的无权简单图以及一个每五步通过严格有利可图的联盟偏离进行循环的 3-染色配置无限序列的存在性。
定理(maxcut_unweighted_strong_deviation_cycle_exists)。 存在一个包含 46 个顶点且具有可判定邻接关系的无权简单图 $G$,以及一个 3-染色配置的无限序列 $f : \mathbb{N} \to (\text{Fin } 46 \to \text{Fin } 3)$,使得: 1. 该序列在五步后返回其初始构型: $$f(5) = f(0);$$ 2. 对于每个 $n \in \mathbb{N}$,从 $f(n)$ 到 $f(n+1)$ 的配置转移是在 $G$ 中对于 $k = 3$ 种颜色的强偏离,其中偏离联盟恰好是改变其颜色的顶点集: $$S_n = \{v \in \text{Fin } 46 : f(n+1)(v) \ne f(n)(v)\}.$$
在 Lean 4 中,定理 maxcut_unweighted_strong_deviation_cycle_exists 断言,存在 46 个顶点类型上的无权图、邻接关系的可判定性实例以及 3-染色的序列,使得步骤 5 处的染色等于步骤 0 处的染色,并且对于每个自然数 $n$,联盟偏离谓词 is_maxcut_strong_deviation 在该图上对 3 种颜色在步骤 $n$ 和步骤 $n+1$ 之间成立,其中偏离联盟由颜色的不等性过滤得到。
这一主要结果依赖于两个辅助定理,它们将论证分为 46 个顶点上的具体组合验证和抽象周期延拓:
第一个辅助结果 maxcut_cycle46_deviations 证明了对于具体图 maxcut_cycle46_graph 和染色族 maxcut_cycle46_coloring,$\text{Fin } 5$ 中的每个阶段转移 $i \to i+1$ 都是以 $\{v : \sigma_{i+1}(v) \ne \sigma_i(v)\}$ 为联盟的有效强联盟偏离。对于这五个转移中的每一个,偏离联盟中的每位成员都严格提升了其效用。
第二个辅助结果 maxcut_five_cycle_repeats 确立了一个抽象提升性质:对于具有可判定邻接关系的有限顶点类型上的任意有限简单图 $G$ 和任意包含 $k$ 种颜色的调色板,如果一个由五个染色组成的族在模 5 的阶段递增下形成强偏离的有向闭环,则存在一个无限序列 $f : \mathbb{N} \to (V \to \text{Fin } k)$,使得 $f(5) = f(0)$ 且每一步 $n \to n+1$ 都是由改变颜色的顶点发起的强偏离。
这些结果共同排除了无权 Max-3-Cut 博弈中针对有利可图联盟偏离的强势函数的存在性:如果存在这样的势函数,它将必须沿着这五个转移严格递增,这与 $f(5) = f(0)$ 相矛盾。
theorem maxcut_unweighted_strong_deviation_cycle_exists : ∃ (G : SimpleGraph (Fin 46)) (d : DecidableRel G.Adj) (f : ℕ → Fin 46 → Fin 3), f 5 = f 0 ∧ ∀ n, @is_maxcut_strong_deviation _ _ G d 3 (f n) (Finset.univ.filter fun v => f (n + 1) v ≠ f n v) (f (n + 1))
4. 证明
证明分为三个部分。首先,我们解释 46 顶点图的结构设计。其次,我们陈述引理 1(maxcut_cycle46_deviations)并逐步验证五个阶段转移中的每一个,详细说明每个顶点块的度数、同色邻点数和精确效用。第三,我们陈述引理 2(maxcut_five_cycle_repeats)并展示它如何与引理 1 结合以完成 maxcut_unweighted_strong_deviation_cycle_exists 的证明。
maxcut_cycle46_graph 背后的思想是将联盟动态解耦为两个互补的阶段。在第一阶段(转移 $0 \to 1$),所有四个核心块 $B_0, B_1, B_2, B_3$ 参与一次大规模协调偏离:32 个顶点同时改变其颜色。在第二阶段(转移 $1 \to 2$、$2 \to 3$、$3 \to 4$ 和 $4 \to 0$),四个核心块一次一个块地恢复到其初始颜色:
- 在转移 $1 \to 2$ 中,块 $B_3$ 从颜色 1 恢复为颜色 0;
- 在转移 $2 \to 3$ 中,块 $B_1$ 从颜色 0 恢复为颜色 1;
- 在转移 $3 \to 4$ 中,块 $B_2$ 从颜色 1 恢复为颜色 2;
- 在转移 $4 \to 0$ 中,块 $B_0$ 从颜色 2 恢复为颜色 0。
锚块 $A_0$ 和 $A_1$ 分别固定在颜色 1 和颜色 2。它们的作用是提供精确的不对称邻点数,以使每一个单独的转移都严格增加 $+1$ 的收益。
引理 1(maxcut_cycle46_deviations)。 设 $G = \text{maxcut\_cycle46\_graph}$ 且对 $s \in \text{Fin } 5$ 设 $\sigma_s = \text{maxcut\_cycle46\_coloring } s$。对于每个 $i \in \text{Fin } 5$,从 $\sigma_i$ 到 $\sigma_{i+1}$ 的转移是 $G$ 中的强联盟偏离,偏离联盟为 $S_i = \{v \in \text{Fin } 46 : \sigma_{i+1}(v) \ne \sigma_i(v)\}$。
引理 1 的证明。 我们确定 maxcut_cycle46_graph 各块中任意顶点的度数和邻域组成: - 对于 $u \in B_0 = \{0, \dots, 7\}$:$u$ 在 $B_2$ 中有 2 个邻点(满足 $(v - 16 + 8 - u) \pmod 8 \in \{0, 1\}$ 的索引 $v$),在 $B_3$ 中有 8 个邻点($B_3$ 的所有顶点),以及在 $A_1$ 中有 7 个邻点($A_1$ 的所有顶点)。总度数为 $\deg(u) = 2 + 8 + 7 = 17$。 - 对于 $u \in B_1 = \{8, \dots, 15\}$:$u$ 在 $B_2$ 中有 4 个邻点(满足 $(v - 16 + 8 - (u - 8)) \pmod 8 \in \{0, 1, 2, 3\}$ 的索引 $v$),在 $B_3$ 中有 6 个邻点(满足 $(v - 24 + 8 - (u - 8)) \pmod 8 \ge 2$ 的索引 $v$),以及在 $A_0$ 中有 1 个邻点(具体为顶点 32)。总度数为 $\deg(u) = 4 + 6 + 1 = 11$。 - 对于 $v \in B_2 = \{16, \dots, 23\}$:$v$ 在 $B_0$ 中有 2 个邻点(满足 $(v - 16 + 8 - u) \pmod 8 \in \{0, 1\}$ 的索引 $u$),在 $B_1$ 中有 4 个邻点(满足 $(v - 16 + 8 - (u - 8)) \pmod 8 \in \{0, 1, 2, 3\}$ 的索引 $u$),以及在 $A_1$ 中有 1 个邻点(具体为顶点 39)。总度数为 $\deg(v) = 2 + 4 + 1 = 7$。 - 对于 $v \in B_3 = \{24, \dots, 31\}$:$v$ 在 $B_0$ 中有 8 个邻点($B_0$ 的所有顶点),在 $B_1$ 中有 6 个邻点(满足 $(v - 24 + 8 - (u - 8)) \pmod 8 \ge 2$ 的索引 $u$),以及在 $A_0$ 中有 7 个邻点($A_0$ 的所有顶点)。总度数为 $\deg(v) = 8 + 6 + 7 = 21$。
$A_0$ 和 $A_1$ 中的顶点在所有五个阶段中都保持恒定颜色,因此它们从不属于 $S_i$。我们现在验证所有五个转移中的效用增量:
步骤 0($0 \to 1$):初始染色 $\sigma_0$ 给 $B_0$ 分配颜色 0,给 $B_1$ 分配 1,给 $B_2$ 分配 2,给 $B_3$ 分配 0,给 $A_0$ 分配 1,给 $A_1$ 分配 2。目标染色 $\sigma_1$ 给 $B_0$ 分配颜色 2,给 $B_1$ 分配 0,给 $B_2$ 分配 1,给 $B_3$ 分配 1,给 $A_0$ 分配 1,给 $A_1$ 分配 2。偏离联盟为 $S_0 = B_0 \cup B_1 \cup B_2 \cup B_3$,其中 $|S_0| = 32$。
- 对于 $u \in B_0$:在阶段 0,$u$ 的颜色为 0;其在 $B_3$ 中的 8 个邻点共享颜色 0,而其在 $B_2$ 中的 2 个邻点颜色为 2,在 $A_1$ 中的 7 个邻点颜色为 2。同色邻点数为 8,给出效用 $u_u(\sigma_0) = 17 - 8 = 9$。在阶段 1,$u$ 的颜色为 2;其在 $A_1$ 中的 7 个邻点共享颜色 2,而其在 $B_2$ 中的 2 个邻点颜色为 1,在 $B_3$ 中的 8 个邻点颜色为 1。同色邻点数为 7,给出效用 $u_u(\sigma_1) = 17 - 7 = 10$。效用严格从 9 增加到 10($+1$)。
- 对于 $u \in B_1$:在阶段 0,$u$ 的颜色为 1;其在 $A_0$ 中的邻点顶点 32 颜色为 1,而其在 $B_2$ 中的 4 个邻点颜色为 2,在 $B_3$ 中的 6 个邻点颜色为 0。同色邻点数为 1,给出效用 $u_u(\sigma_0) = 11 - 1 = 10$。在阶段 1,$u$ 的颜色为 0;其在 $B_2$ 中的 4 个邻点颜色为 1,在 $B_3$ 中的 6 个邻点颜色为 1,且顶点 32 颜色为 1。同色邻点数为 0,给出效用 $u_u(\sigma_1) = 11 - 0 = 11$。效用严格从 10 增加到 11($+1$)。
- 对于 $v \in B_2$:在阶段 0,$v$ 的颜色为 2;其在 $A_1$ 中的邻点顶点 39 颜色为 2,而其在 $B_0$ 中的 2 个邻点颜色为 0,在 $B_1$ 中的 4 个邻点颜色为 1。同色邻点数为 1,给出效用 $u_v(\sigma_0) = 7 - 1 = 6$。在阶段 1,$v$ 的颜色为 1;其在 $B_0$ 中的 2 个邻点颜色为 2,在 $B_1$ 中的 4 个邻点颜色为 0,且顶点 39 颜色为 2。同色邻点数为 0,给出效用 $u_v(\sigma_1) = 7 - 0 = 7$。效用严格从 6 增加到 7($+1$)。
- 对于 $v \in B_3$:在阶段 0,$v$ 的颜色为 0;其在 $B_0$ 中的 8 个邻点共享颜色 0,而其在 $B_1$ 中的 6 个邻点颜色为 1,在 $A_0$ 中的 7 个邻点颜色为 1。同色邻点数为 8,给出效用 $u_v(\sigma_0) = 21 - 8 = 13$。在阶段 1,$v$ 的颜色为 1;其在 $A_0$ 中的 7 个邻点共享颜色 1,而其在 $B_0$ 中的 8 个邻点颜色为 2,在 $B_1$ 中的 6 个邻点颜色为 0。同色邻点数为 7,给出效用 $u_v(\sigma_1) = 21 - 7 = 14$。效用严格从 13 增加到 14($+1$)。
步骤 1($1 \to 2$):染色 $\sigma_2$ 给 $B_0$ 分配颜色 2,给 $B_1$ 分配 0,给 $B_2$ 分配 1,给 $B_3$ 分配 0,给 $A_0$ 分配 1,给 $A_1$ 分配 2。仅有块 $B_3$ 改变颜色(从 1 到 0),因此 $S_1 = B_3$,其中 $|S_1| = 8$。对于 $v \in B_3$:在阶段 1,$v$ 的颜色为 1,在 $A_0$ 中有 7 个同色邻点,给出效用 14。在阶段 2,$v$ 的颜色为 0;其在 $B_1$ 中的 6 个邻点颜色为 0,而其在 $B_0$ 中的 8 个邻点颜色为 2,在 $A_0$ 中的 7 个邻点颜色为 1。同色邻点数为 6,给出效用 $u_v(\sigma_2) = 21 - 6 = 15$。效用严格从 14 增加到 15($+1$)。
步骤 2($2 \to 3$):染色 $\sigma_3$ 给 $B_0$ 分配颜色 2,给 $B_1$ 分配 1,给 $B_2$ 分配 1,给 $B_3$ 分配 0,给 $A_0$ 分配 1,给 $A_1$ 分配 2。仅有块 $B_1$ 改变颜色(从 0 到 1),因此 $S_2 = B_1$,其中 $|S_2| = 8$。对于 $u \in B_1$:在阶段 2,$u$ 的颜色为 0,在 $B_3$ 中有 6 个同色邻点(其颜色为 0),给出效用 $u_u(\sigma_2) = 11 - 6 = 5$。在阶段 3,$u$ 的颜色为 1;其在 $B_2$ 中的 4 个邻点颜色为 1 且顶点 32 颜色为 1,给出 5 个同色邻点及效用 $u_u(\sigma_3) = 11 - 5 = 6$。效用严格从 5 增加到 6($+1$)。
步骤 3($3 \to 4$):染色 $\sigma_4$ 给 $B_0$ 分配颜色 2,给 $B_1$ 分配 1,给 $B_2$ 分配 2,给 $B_3$ 分配 0,给 $A_0$ 分配 1,给 $A_1$ 分配 2。仅有块 $B_2$ 改变颜色(从 1 到 2),因此 $S_3 = B_2$,其中 $|S_3| = 8$。对于 $v \in B_2$:在阶段 3,$v$ 的颜色为 1,在 $B_1$ 中有 4 个同色邻点(其颜色为 1),给出效用 $u_v(\sigma_3) = 7 - 4 = 3$。在阶段 4,$v$ 的颜色为 2;其在 $B_0$ 中的 2 个邻点颜色为 2 且顶点 39 颜色为 2,给出 3 个同色邻点及效用 $u_v(\sigma_4) = 7 - 3 = 4$。效用严格从 3 增加到 4($+1$)。
步骤 4($4 \to 0$):按模 5 加法,阶段 $4 + 1$ 为阶段 0。仅有块 $B_0$ 改变颜色(从 2 到 0),因此 $S_4 = B_0$,其中 $|S_4| = 8$。对于 $u \in B_0$:在阶段 4,$u$ 的颜色为 2;其在 $B_2$ 中的 2 个邻点颜色为 2 且在 $A_1$ 中的 7 个邻点颜色为 2,给出 9 个同色邻点及效用 $u_u(\sigma_4) = 17 - 9 = 8$。在阶段 0,$u$ 的颜色为 0;其在 $B_3$ 中的 8 个邻点颜色为 0,给出 8 个同色邻点及效用 $u_u(\sigma_0) = 17 - 8 = 9$。效用严格从 8 增加到 9($+1$)。
这验证了所有五个转移均满足 is_maxcut_strong_deviation。在 Lean 中,有限类型的检验通过可判定性求值完成。
引理 2(maxcut_five_cycle_repeats)。 设 $V$ 为有限类型,$G$ 为 $V$ 上具有可判定邻接关系的简单图,$k \in \mathbb{N}$,且 $\text{colors} : \text{Fin } 5 \to V \to \text{Fin } k$。如果对所有 $i \in \text{Fin } 5$,从 $\text{colors}(i)$ 到 $\text{colors}(i+1)$ 的步骤是由改变颜色的顶点构成的强偏离,则存在具有 $f(5) = f(0)$ 的 $f : \mathbb{N} \to V \to \text{Fin } k$,使得每一步 $n \to n+1$ 均是由改变颜色的顶点构成的强偏离。
引理 2 的证明。 定义 $f(n) = \text{colors}(\langle n \pmod 5, \dots \rangle)$。由于 $5 \equiv 0 \pmod 5$,有 $f(5) = \text{colors}(0) = f(0)$。对每个 $n \in \mathbb{N}$,设 $i = \langle n \pmod 5, \dots \rangle$,从 $f(n)$ 到 $f(n+1)$ 的配置转移对应于 $\text{colors}(i) \to \text{colors}(i+1)$。偏离集合为 $\{v : f(n+1)(v) \ne f(n)(v)\} = \{v : \text{colors}(i+1)(v) \ne \text{colors}(i)(v)\}$。根据假设,此转移满足 is_maxcut_strong_deviation,因此该单步性质对所有 $n$ 均成立。
主定理的证明。 将 maxcut_five_cycle_repeats 应用于 maxcut_cycle46_graph、maxcut_cycle46_coloring 以及 maxcut_cycle46_deviations,可得出序列 $f$、周期性 $f(5) = f(0)$ 以及对所有 $n$ 的偏离凭证。将这些与 maxcut_cycle46_graph 及其可判定性见证一同打包到存在量词元组中,即证明了 maxcut_unweighted_strong_deviation_cycle_exists。
5. 讨论
本文给出的构造针对三种颜色的情形回答了 arXiv:1810.09278 中讨论的关于无权 Max-$k$-Cut 博弈是否容许强势函数的问题。尽管无权 Max-$k$-Cut 博弈中的个体偏离受割权重精确势函数支配,但联盟偏离不受任何标量势函数的约束:即使所有边权重严格等于 1,有利可图的联盟偏离也可以形成有向闭环。
观察促成该环的机制是很有启发性的。在加权博弈中(例如 arXiv:1810.09278 的命题 2),可以连续调整边权重以平衡不对称的偏离。在无权设定中,所有效用增量必须为整数。在此处,五个转移中的每一个都为偏离联盟的每位成员带来恰好 $+1$ 的严格效用增长。该构造通过将核心块之间的正则循环连接与精心确定规模的锚块($A_0$ 和 $A_1$,各含 7 个顶点)配对来实现这种平衡,锚块提供了抵消内部连接变化所需的恒定外部邻点数量。
然而,仍有若干基本问题尚未解决:
- 联盟规模:在 46 顶点的构造中,环在大小为 8 的单块偏离与涉及所有四个核心块的大型协调偏离(其中 $|S_0| = 32$)之间交替。该结果并未断言规模为 32 的联盟是启动该环的极小规模,也未确定在无权博弈中能够循环的极小联盟规模。无权图能否支持所有偏离联盟规模至多为 2 的环,还是说联盟循环必然需要大型联盟?
- 强均衡存在性:强偏离环的存在并不排除同一图的状态空间中其他地方存在强纳什均衡(SNE)。一般来说,一个博弈既可以有偏离环,也可以拥有无法离开的稳定状态。正如 arXiv:2610.04948 第 4 节所强调的,每个无权 Max-$k$-Cut 博弈是否至少拥有一个强纳什均衡仍是一个悬而未决的问题。
- 图的规模与颜色数量:当前的实例使用了 46 个顶点和 3 种颜色。对于 $k = 3$,容许强偏离环的无权简单图的最小顶点数是多少?对于 $k = 2$(无权最大割),是否存在这样的环,还是说无权双色博弈具备迫使其无环的结构性质?
- 社会最优性:正如 arXiv:2610.04948 中所讨论的,社会最优割(即最大化总割权重的割)与联盟稳定性之间的关系是复杂的。在我们的五阶段环中,割权重在各阶段之间波动:步骤 0 的协调偏离严格增加了所有 32 个参与顶点的效用,但将配置转移到了具有不同全局割权重的状态。
总之,maxcut_unweighted_strong_deviation_cycle_exists 的形式化验证通过一个具体的有限实例排除了无权博弈中的强势函数,同时留下了极小联盟规模、极小图阶数以及强纳什均衡的一般存在性等问题供未来研究探索。
为什么是研究级成果
- Exhibits a cycle of profitable coalitional deviations in an unweighted three-color game, ruling out a strong potential for all such deviations; the cited cycle used weighted edges. This does not assert that the large coalition is minimal or resolve strong-equilibrium existence
Lean 声明
- maxcut_unweighted_strong_deviation_cycle_existsThere is an unweighted simple graph on 46 vertices and an infinite sequence of three-color profiles that returns to its starting profile…
- is_maxcut_strong_deviationA strong deviation from σ is a nonempty coalition S ⊆ V with a coloring τ agreeing with σ outside S such that u_v(τ) > u_v(σ) for every v…
- maxcut_cycle46_graphA 46-vertex finite simple unweighted graph for a five-step strong-deviation cycle: four core blocks of eight, and two fixed-color anchor…
- maxcut_cycle46_coloringThe five successive three-color profiles of the 46-vertex example, with stage addition modulo five.
- maxcut_cycle46_deviationsEach successive pair of the five displayed colorings, including the transition from the fifth to the first, is a strong deviation on the…
- maxcut_five_cycle_repeatsAny five colorings that form a directed cycle of strong deviations repeat periodically to yield an infinite strong-deviation sequence…
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
参考文献
- arXiv:1810.09278
- arXiv:2610.04948 — Social Optimality Does Not Imply Coalitional Stability in Unweighted Max-k-Cut Games
由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。