无权 71 顶点图在三色最大割中允许包含极小获益偏离的 33 步循环
medium tier2026-11-03审阅: Claude CodeEnglish
摘要
在最大 $k$-割(Max-$k$-Cut)博弈中,图的每个顶点选择 $k$ 种颜色之一,其收益为具有不同颜色的邻居数量。arXiv:1810.09278 在带权图上表明,由极小联盟执行的改进偏离可能会成环,因此即使仅允许极小联盟进行偏离,带权博弈也不存在强势函数;其结论部分悬而未决的是无权图上是否存在强势函数。我们对三种颜色的情况给出了否定回答。在一个由 4 个 8 顶点核心块和 3 个 13 顶点锚块组成的 71 顶点显式无权图上,我们给出了一个返回其初始着色的 33 步强改进环:32 个核心顶点首先联合偏离,每个顶点收益恰好增加 1,然后逐个返回它们原本的颜色,每个顶点的收益再次增加 1。每一步都是包含极小的:从该步骤开始的着色出发,发生改变的顶点集的任何真子集都不存在任何有利的联合偏离。该联合步骤使割值降低 32,而 32 次单顶点移动中的每一次都使割值增加 1。相关定义、环及其极小性均已在 Lean 4 中得到验证。
1. 引言
在有限博弈中,势函数是策略配置上的实值函数,每当有玩家通过单方面改变而提高其收益时,该函数严格增加。强势函数在每次强改进下也严格增加,即联盟联合改变策略且其中所有成员的收益均严格增加。这样的函数禁止了强改进环的存在,并且在它存在时,证明了强均衡(SE)的存在,因为改进动态必然终止。它是证明强均衡存在性的主要工具之一。
最大 $k$-割博弈在有限无向图 $G = (V, E)$ 上进行。每个顶点作为一个玩家选择 $k$ 种颜色之一,其收益是与其关联且另一端点具有不同颜色的边的总权重;在无权图上,这就是具有不同颜色的邻居数量。割值是单方面移动的精确势,因此纳什均衡(NE)存在。强均衡是否始终存在仍然是一个公开问题。
arXiv:1810.09278 研究了该博弈的强均衡。在其中,如果发生偏离的联盟的任何真子集都无法自行实现改进,则称该强改进是极小的。其命题 2 展示了一个仅由极小联盟执行强改进形成环的带权图(四个玩家联合偏离,随后进行四次单玩家改进),从而表明在带权图上,即使只允许极小联盟进行偏离,也不存在强势函数。对于无权图,该论文证明了积极的结果:从一个纳什均衡出发,至多五个玩家的联盟进行的极小强改进会增加割值,并且每个最优着色都是 5-强均衡。它还表明,割值本身在无权图上并不是强势函数。其结论部分指出,无权图上是否存在强势函数仍然是未知的。
本文以带权图结果的强形式,对三种颜色的该问题给出了否定回答。我们给出了一个在 71 个顶点上的显式无权图 maxcut_cycle71_graph 以及一个返回起点的 33 个三着色序列,其中每一步都是改变颜色的顶点集所进行的强改进,并且每一步都是包含极小的:从该步骤开始的着色出发,发生改变的顶点集的任何真子集都根本没有任何有利的联合偏离。若一个函数沿每次极小强改进都严格增加,则它沿该环必须严格增加,这是不可能的。因此,无权三色最大割博弈不存在强势函数,即使仅允许极小联盟偏离也是如此。
该环具有简单的形式。其中一步是 32 个核心顶点的联合偏离,使割值降低 32,同时每个核心顶点的收益恰好增加 1;其余 32 步是单个顶点返回其原有颜色,每步使割值增加 1。整个构造已在 Lean 4 中形式化并经过机器检查,定理名称为 maxcut_unweighted_minimal_deviation_cycle_exists。
2. 预备知识
设 $V$ 为有限顶点集,$G$ 为 $V$ 上的简单图。在三色最大割(Max-Cut)博弈中,每个顶点从 $\{0, 1, 2\}$ 中选择一种颜色,形式化为 $\text{Fin } 3$。在着色 $\sigma : V \to \text{Fin } 3$ 下,顶点 $v$ 的效用是分配给与 $\sigma(v)$ 不同颜色的 $v$ 的邻居数量: $$ u_v(\sigma) = |\{ w \in V : G\text{.Adj}(v, w) \land \sigma(w) \neq \sigma(v) \}|. $$ 最大化效用等价于最小化共享相同颜色的邻居数量。
定义 1(is_maxcut_strong_deviation)。设 $G$ 是具有可判定邻接关系的有限类型 $V$ 上的简单图,并设 $k \ge 1$。给定策略配置 $\sigma : V \to \text{Fin } k$、联盟 $S \subseteq V$ 以及策略配置 $\tau : V \to \text{Fin } k$,当满足以下条件时,谓词 is_maxcut_strong_deviation 成立:
- $S$ 非空;
- 对所有 $v \notin S$,有 $\tau(v) = \sigma(v)$;
- 对所有 $v \in S$,有 $u_v(\sigma) < u_v(\tau)$。
关于定义 1 的注记。在 arXiv:1810.09278 中,发生偏离的联盟的成员改变其策略。Lean 的定义并不要求这一点。在下文的环中,每一步的联盟恰好是颜色发生改变的顶点集,因此每个成员确实改变了颜色。对于极小性而言,Lean 的定义只会让结论更强:它排除了真子联盟可能获益的偏离,即使其中的成员保持其颜色不变也是如此。
定义 2(maxcut_cycle71_field)。锚度数函数 maxcut_cycle71_field 指定从核心顶点 $u$ 到锚块 $j \in \{0, 1, 2\}$ 的边数: - 当 $u < 8$ 时:对于 $j=0$ 为 0,对于 $j=1$ 为 13,对于 $j=2$ 为 7。 - 当 $8 \le u < 16$ 时:对于 $j=0$ 为 1,对于 $j=1$ 为 2,对于 $j=2$ 为 13。 - 当 $16 \le u < 24$ 时:对于 $j=0$ 为 13,对于 $j=1$ 为 1,对于 $j=2$ 为 2。 - 当 $24 \le u < 32$ 时:对于 $j=0$ 为 0,对于 $j=1$ 为 7,对于 $j=2$ 为 13。 当 $u \ge 32$ 时,该场的值为 0。
关于定义 2 的注记。每个锚块有 13 个顶点。值为 13 表示将 $u$ 连接到该锚块中的所有顶点,而 0 则不产生任何边。
定义 3(maxcut_cycle71_graph)。图 maxcut_cycle71_graph 是 $V = \text{Fin } 71 = \{0, \dots, 70\}$ 上的无权简单图。顶点划分为四个 8 顶点的核心块($B_0 = \{0, \dots, 7\}$、$B_1 = \{8, \dots, 15\}$、$B_2 = \{16, \dots, 23\}$、$B_3 = \{24, \dots, 31\}$)和三个 13 顶点的锚块($A_0 = \{32, \dots, 44\}$、$A_1 = \{45, \dots, 57\}$、$A_2 = \{58, \dots, 70\}$)。边 $\{u, v\}$ 存在当且仅当 $u \neq v$ 且 $(R(u, v) \lor R(v, u))$,其中 $R(u, v)$ 是以下六个条件的析取:
- $u \in B_0, v \in B_1$,且 $(v - 8 + 8 - u) \pmod 8 \ge 2$;
- $u \in B_0, v \in B_2$,且 $(v - 16 + 8 - u) \pmod 8 < 2$;
- $u \in B_0$ 且 $v \in B_3$;
- $u \in B_1, v \in B_2$,且 $(v - 16 + 8 - (u - 8)) \pmod 8 < 4$;
- $u \in B_1, v \in B_3$,且 $(v - 24 + 8 - (u - 8)) \pmod 8 \ge 2$;
- $u < 32, v \ge 32$,且 $(v - 32) \pmod{13} < \text{field}(u, (v - 32) / 13)$。
关于定义 3 的注记。核心块内部、$B_2$ 与 $B_3$ 之间,以及锚块内部或相互之间不存在边。模 8 的条件定义了核心块之间的正则循环连接。
定义 4(maxcut_cycle71_return_stages)。设 $\sigma^{(0)}$ 和 $\sigma^{(1)}$ 为在锚块上一致的两种三着色,锚块按块着色($A_0$ 着颜色 0,$A_1$ 着颜色 1,$A_2$ 着颜色 2),核心块着色如下:$\sigma^{(0)}$ 赋予 $B_0, B_1, B_2, B_3$ 颜色 $0, 1, 2, 0$,而 $\sigma^{(1)}$ 赋予它们 $2, 0, 1, 1$。核心顶点的秩为其在核心顶点返回顺序中的位置:依次为 $B_3$、$B_1$、$B_2$、$B_0$,每个块内部按顶点编号递增顺序排列;秩的取值范围为 $\{0, \dots, 31\}$。对于每个 $i \in \text{Fin } 33 = \{0, \dots, 32\}$,由 maxcut_cycle71_return_stages 在 $i$ 处给出的配置 $\sigma_i$ 为: $$ \sigma_i(v) = \begin{cases} \sigma^{(0)}(v) & \text{if } i = 0 \lor (v < 32 \land \text{rank}(v) < i - 1), \\ \sigma^{(1)}(v) & \text{otherwise.} \end{cases} $$
关于定义 4 的注记。在阶段 0,着色为 $\sigma^{(0)}$。在阶段 1,所有 32 个核心顶点均具有其 $\sigma^{(1)}$ 颜色。从阶段 $i$ 到阶段 $i+1$(对于 $i = 1, \dots, 32$,其中阶段 33 视作阶段 0),秩为 $i - 1$ 的核心顶点返回其 $\sigma^{(0)}$ 颜色。锚顶点从未改变颜色。
3. 主要结果
主定理确立了在无权 71 顶点图 maxcut_cycle71_graph 上的三色最大割博弈中,存在强偏离的无限周期序列,其在 33 步后返回到其初始配置,其中每一步都是包含极小的。
定理(maxcut_unweighted_minimal_deviation_cycle_exists)。 在 maxcut_cycle71_graph 上存在可判定邻接关系 $d$ 以及三着色序列 $f : \mathbb{N} \to (\text{Fin } 71 \to \text{Fin } 3)$,使得: 1. 该序列在 33 次转移后返回其起点:$f(33) = f(0)$; 2. 对每个 $n \in \mathbb{N}$,从 $f(n)$ 到 $f(n+1)$ 的配置转移是由发生改变的顶点集 $S_n = \{ v \in \text{Fin } 71 : f(n+1)(v) \neq f(n)(v) \}$ 执行的强偏离(is_maxcut_strong_deviation); 3. 对每个 $n \in \mathbb{N}$,偏离 $S_n$ 是包含极小的:对于每个真子集 $S \subsetneq S_n$,不存在三着色 $\tau : \text{Fin } 71 \to \text{Fin } 3$ 使得 $(S, \tau)$ 是 maxcut_cycle71_graph 上从 $f(n)$ 出发的强偏离。
该结果所确立的内容:强势函数会沿着强改进序列的每一步严格增加,因此当这样的序列返回其起点时,强势函数不可能存在。该定理在具有三种颜色的无权图上给出了这样一个序列,且其每一步都是包含极小的。因此,对于无权三色最大割博弈,即使仅要求强势函数沿极小联盟的强改进增加,也不存在强势函数。这是 arXiv:1810.09278 命题 2 在无权图上的对应结论,并对 $k = 3$ 回答了其结论部分悬而未决的问题。
theorem maxcut_unweighted_minimal_deviation_cycle_exists : ∃ (d : DecidableRel maxcut_cycle71_graph.Adj) (f : ℕ → Fin 71 → Fin 3), f 33 = f 0 ∧ ∀ n, @is_maxcut_strong_deviation _ _ maxcut_cycle71_graph d 3 (f n) (Finset.univ.filter fun v => f (n + 1) v ≠ f n v) (f (n + 1)) ∧ ∀ S : Finset (Fin 71), S ⊂ (Finset.univ.filter fun v => f (n + 1) v ≠ f n v) → ¬ ∃ τ : Fin 71 → Fin 3, @is_maxcut_strong_deviation _ _ maxcut_cycle71_graph d 3 (f n) S τ
4. 证明
我们概述 maxcut_unweighted_minimal_deviation_cycle_exists 的证明。该序列为 $f(n) = \sigma_{n \bmod 33}$,其中 $\sigma_i$ 是 maxcut_cycle71_return_stages 在 $i$ 处的值。于是所有内容都归结为关于 33 对连续阶段的一个命题。
引理 1(maxcut_cycle71_minimal_cycle_steps)。对于每个 $i \in \text{Fin } 33$(其中 $i + 1$ 取在 $\text{Fin } 33$ 中),令 $$ D_i = \{ v \in \text{Fin } 71 : \sigma_{i+1}(v) \neq \sigma_i(v) \}. $$ 则 $(D_i, \sigma_{i+1})$ 是从 $\sigma_i$ 出发的强偏离,且对于每个真子集 $S \subsetneq D_i$,不存在着色 $\tau$ 使得 $(S, \tau)$ 是从 $\sigma_i$ 出发的强偏离。
这 33 步分为两类:从阶段 0 到阶段 1 的联合偏离,以及 32 次单顶点返回。
单顶点返回。对于从阶段 $i$ 到阶段 $i+1$(其中 $i \in \{1, \dots, 32\}$)的 32 步中的每一步,一个辅助引理通过内核求值验证了发生改变的顶点集 $D_i$ 是秩为 $i - 1$ 的单个核心顶点 $v_i$,并且在保持其余着色固定的情况下,$v_i$ 通过从其 $\sigma^{(1)}$ 颜色返回其 $\sigma^{(0)}$ 颜色而严格获益。事实上,每个这样的顶点的收益恰好增加 1,并且每次返回都使割值增加 1。这里的极小性是显而易见的:单元素集的唯一真子集是空集,而强偏离要求联盟非空。
联合偏离。从阶段 0 到阶段 1,恰好 32 个核心顶点改变颜色,因为锚顶点在 $\sigma^{(0)}$ 和 $\sigma^{(1)}$ 中具有相同的颜色。$(B_0 \cup B_1 \cup B_2 \cup B_3, \sigma^{(1)})$ 是从 $\sigma^{(0)}$ 出发的强偏离这一事实同样通过内核求值进行了验证:每个核心顶点的收益恰好增加 1。作为参考,度数在 $B_0$ 中为 36($B_1$ 中有 6 个邻居,$B_2$ 中有 2 个,$B_3$ 中有 8 个,以及 20 个锚顶点),在 $B_1$ 中为 32,在 $B_2$ 中为 22,在 $B_3$ 中为 34;在这一步中,割值从 688 条边下降到 656 条边,并在随后的每次返回中逐一回升 1。
联合偏离的极小性是实质性的部分。假设核心的真子集 $S$ 与着色 $\tau$ 构成了从 $\sigma^{(0)}$ 出发的强偏离,并设 $M \subseteq S$ 为颜色实际发生改变的成员构成的集合。$M$ 是非空的:若没有成员改变颜色,则 $\tau$ 将等于 $\sigma^{(0)}$,没有人能够获益。
该论证依赖于通过内核求值验证的一项有限计数:对于每个核心顶点 $v$ 和每种颜色 $c \neq \sigma^{(0)}(v)$,$v$ 的为核心顶点或具有不同于 $c$ 的 $\sigma^{(0)}$ 颜色的邻居数量至多为 $u_v(\sigma^{(0)})$;若 $c = \sigma^{(1)}(v)$,则再加上 1。由于 $S$ 之外的每个顶点都保持其 $\sigma^{(0)}$ 颜色且 $S$ 位于核心内,无论其他核心顶点如何做,这一计数都界定了成员 $v$ 改变为颜色 $c$ 时的 $u_v(\tau)$。对每个 $v \in M$ 随之得出以下两个推论:
- $v$ 必须变为其 $\sigma^{(1)}$ 颜色;任何其他新颜色都会导致 $u_v(\tau) \le u_v(\sigma^{(0)})$。
- 若 $v$ 具有一个核心邻居 $w$,其 $\sigma^{(0)}$ 颜色为 $\sigma^{(1)}(v)$,则必有 $w \in M$。否则 $w$ 保持该颜色,边 $vw$ 在 $\tau$ 下为同色边,上界下降 1 变为 $u_v(\tau) \le u_v(\sigma^{(0)})$,从而 $v$ 无法获益。
因此,$M$ 是在强制关系(forcing relation)下封闭的核心顶点的非空集合:$v$ 强制其初始颜色等于 $v$ 的新颜色的每个核心邻居。在各个块之间,该关系的方向为 $B_0 \to B_2$(新颜色 2)、$B_2 \to B_1$(新颜色 1)、$B_1 \to B_0$ 和 $B_1 \to B_3$(新颜色 0),以及 $B_3 \to B_1$(新颜色 1)。另一个引理通过遍历所有 32 个核心顶点的 40 步强制步骤的显式闭途径表明,每个非空闭集都包含整个核心。因此 $M$(随之 $S$ 也)包含全部 32 个核心顶点,这与 $S \subsetneq D_0$ 矛盾。
主定理的证明。邻接关系的可判定性证明是通过展开 maxcut_cycle71_graph 和 maxcut_cycle71_field 的定义获得的。序列定义为 $f(n) = \sigma_{\langle n \bmod 33 \rangle}$。由于 $33 \bmod 33 = 0$,由自反性可知 $f(33) = f(0)$ 成立。对于任意 $n$,通过简短的模运算可知,$n + 1$ 的阶段指标等于 $\text{Fin } 33$ 中的 $i + 1$(其中 $i$ 是 $n$ 的指标)。因此从 $f(n)$ 到 $f(n+1)$ 的步骤即为从 $\sigma_i$ 到 $\sigma_{i+1}$ 的步骤,且引理 1 在指标 $i$ 处同时给出了发生改变的集合的强偏离以及其真子集不存在获益偏离的结论。
5. 讨论
定理 maxcut_unweighted_minimal_deviation_cycle_exists 对三种颜色的情况回答了 arXiv:1810.09278 结论部分留下的公开问题:无权最大割博弈不存在强势函数,正如该论文对带权图所示的那样,即使仅允许极小联盟偏离,情况依然如此。文中的带权环是一个大小为 4 的联盟随后伴随 4 次单顶点移动;而这里的环是一个大小为 32 的联盟随后伴随 32 次单顶点移动。由 13 个顶点组成的锚块起到了带权示例中重边的作用:它们固定了每个核心顶点可以获益选择的颜色。
结果的范围与边界:
1. 颜色数:该反例在三色最大 $k$-割(Max-$k$-Cut,$k = 3$)中运作。本内容并未涉及二色($k = 2$)情况下是否存在包含极小环。对于 $k = 2$,每个玩家只有一种备选颜色,而本构造在锚块上使用了全部三种颜色,无法直接推广。
2. 图的阶数:该构造使用了 71 个顶点:32 个核心顶点划分为四个大小为 8 的循环块,39 个锚顶点划分为三个大小为 13 的块。该结果并未确定 71 个顶点是否是支持包含极小环所需的最小图规模,或者更小的无权图是否也能产生类似的环。
3. 图的拓扑结构:maxcut_cycle71_graph 的构造实质性地利用了核心块之间的稠密二分相互连接以及与锚块的非对称连接。本内容未涉及结构化图族,例如平面图、有界树宽图或正则图。
该构造所表明的内容。割值在每次单方面改进下均会增加,因此任何强改进环都需要降低割值的联盟步骤。在此,单个极小联盟将割值降低 32,而 32 次单顶点移动(每次均为严格改进)又将其恢复。初始着色 $\sigma^{(0)}$ 不是纳什均衡(部分锚顶点可以单独改进),因此该环并不影响该论文中关于至多五个玩家的联盟从纳什均衡偏离的割值论证;它所排除的是任何强势函数,因为强势函数必须沿着从任何着色出发的每次强改进严格增加。同一论文留下的公开问题——每个无权最大 $k$-割博弈是否都具有强均衡(并猜想最优着色即为强均衡)——并未被该环解决:该环仅排除了通过强势函数证明存在性的途径。
后续问题:
1. 是否存在支持 $k = 2$ 种颜色的包含极小强偏离环的无权图?
2. 无权图在三色最大割中允许包含极小强偏离环的最小顶点数 $n$ 是多少?
3. 诸如平面性或有界度数等结构性图限制能否保证包含极小联盟动态的收敛性?
为什么是研究级成果
- Exhibits an unweighted three-color Max-k-Cut game with a cycle of inclusion-minimal profitable deviations, ruling out a strong potential even when deviations are restricted to minimal coalitions
Lean 声明
- maxcut_unweighted_minimal_deviation_cycle_existsOn the specified unweighted 71-vertex graph there is an infinite three-color strong-deviation sequence returning after 33 steps, and every…
- maxcut_cycle71_graphThe explicit 71-vertex finite simple graph with four core blocks of eight and three anchor blocks of thirteen, with edges determined by…
- 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_cycle71_fieldThe number of anchor neighbors of each fixed color assigned to each core block in the regular 71-vertex construction.
- maxcut_cycle71_return_stagesThe 33 profiles of the displayed 71-vertex cycle: the initial profile, the joint deviation, and the partial singleton restorations.
- maxcut_cycle71_minimal_cycle_stepsEvery successive pair of the 33 profiles forms a strong deviation, and no proper subcoalition of its changing vertices has a profitable…
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
参考文献
由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。