AFTD Auto-Formalizing Theoretical Domains

Research Blogs

无权最大 $k$-割博弈并非总存在最优强平衡:一个 3 种颜色的 182 顶点反例

medium tier2026-10-28OP-89审阅: Claude CodeEnglish

摘要

在有限简单图上的无权最大 $k$-割博弈(Max-$k$-Cut game)中,每个顶点从 $k$ 种颜色中选择一种,以最大化端点具有不同颜色的关联边数。如果一种着色达到了最大割值,则称其为最优着色;如果不存在非空顶点联盟可以通过联合重新着色使每个成员都严格提高其效用,则称其为强平衡(SE)。尽管在 arXiv:2610.04948 中已经确立并非每个最优着色都是强平衡,但该文留下了一个未决问题:是否每个无权最大 $k$-割博弈都至少存在一个作为强平衡的最优着色。本文针对 $k = 3$ 对该问题给出了形式化的否定回答。我们构造了一个记为 maxcut_pinned_twins_graph 的 182 顶点图,该图是通过将 arXiv:2610.04948 中 91 顶点的反例图的每个顶点替换为一对独立孪生顶点,并在核心孪生顶点与指定的锚孪生顶点之间添加特定的固定边构建而成的。我们证明了该图表现出最优刚性:除三种颜色的全局置换外,每个最大化福利的 3-着色都等于倍增后的初始着色。由于这一唯一的最优着色配置允许有利可图的联盟偏离,因此该图完全不存在最优强平衡。主定理 maxcut_op89_optimal_strong_equilibrium_negation 及其支撑刚性引理已在 Lean 4 中形式化验证。

1. 引言

在合作博弈论中,无权割博弈为分散式资源分配与划分问题建模,其中智能体占据网络的顶点,并力求使其选择区别于其邻居的选择。给定一个有限简单图 $G = (V, E)$ 和一个整数 $k \ge 3$,无权最大 $k$-割博弈为每个顶点 $v \in V$ 分配由 $k$ 种颜色组成的策略空间 $\{0, \dots, k-1\}$。在着色配置 $\sigma : V \to \{0, \dots, k-1\}$ 下,顶点 $v$ 的收益或效用定义为 $G$ 中分配了与 $\sigma(v)$ 不同颜色的 $v$ 的邻居数量。整个顶点集上所有个体效用的总和恰好是划分割值的两倍,这意味着该博弈中的社会福利最大化与经典的最大 $k$-割优化问题完全一致。

博弈论与组合优化交叉领域的一个核心议题是,社会最优配置是否能够抵御玩家群体的策略性偏离。如果不存在非空顶点联盟可以联合改变其颜色,使得每个参与成员都严格增加其个体效用,则称着色配置为强平衡。因为社会最优性最大化了总割权重,人们可能会问社会最优性是否蕴涵联盟稳定性,或者至少社会福利最大化是否与联盟稳定性相容。

在 arXiv:2610.04948 中,定理 2 表明社会最优性并不蕴涵联盟稳定性:该文构造了一个具体的 91 顶点图 $G_3$,带有一个最优 3-着色 $\sigma_0$,其由 16 个核心顶点组成的联盟可以联合重新着色为着色 $\tau_0$,使得每个成员都获得 1 单位效用,同时割值保持不变。然而,该结果仅表明某个特定的最优着色可能不具备联盟稳定性。正如 arXiv:2610.04948 的注记 6 和第 4 节所指出的,图 $G_3$ 并没有排除在其图上存在另一个稳定的最优点。事实上,在 $G_3$ 本身上,偏离后的着色 $\tau_0$ 具有与 $\sigma_0$ 相同的割值,因此它是最优的,且它是一个强平衡(maxcut_anchor_three_coloring_strong):$G_3$ 确实存在最优强平衡。

因此,arXiv:2610.04948 的第 4 节留下了两个不同的未决问题:

  • 是否每个无权最大 $k$-割博弈都存在强平衡?
  • 是否每个无权最大 $k$-割博弈都存在一个作为强平衡的最优着色?

关于最优强平衡的存在性,文献与形式化进展中已知有若干积极结果。根据 arXiv:2610.04948 的推论 9(形式化为 maxcut_op89_exists_of_max_degree_le),最大度满足 $\Delta(G) \le 2k - 1$ 的每个有限简单图都存在一个作为强平衡的最优着色。特别是对于 $k = 3$,任何最大度至多为 5 的图都存在最优强平衡,这记录在 maxcut_op89_exists_of_max_degree_five 中。此外,对于满足 $|V| \le 2k$ 的小图,始终保证存在最优强平衡(maxcut_op89_exists_of_card_le)。然而,超出这些度和基数界限后,社会最优性与联盟稳定性的一般相容性仍然悬而未决。

本文介绍了对 $k = 3$ 时第二个问题的否定解决,并在 Lean 4 中形式化为 maxcut_op89_optimal_strong_equilibrium_negation。我们证明并非每个有限简单图上的无权最大 $k$-割博弈都存在一个作为强平衡的最优着色。该反例是一个具体的 182 顶点图 maxcut_pinned_twins_graph。该图是通过将 arXiv:2610.04948 中的 91 顶点图的每个顶点倍增为两个独立孪生顶点,并在核心孪生顶点与指定的锚顶点之间添加固定边构造而成的。

倍增变换将基础图的每条边转化为对应孪生对之间的完全二分图 $K_{2,2}$,而固定边则刚性地固定了最优 3-着色。具体而言,我们确立了一个最优刚性定理(maxcut_pinned_twins_optimum_rigidity):maxcut_pinned_twins_graph 的每个最优 3-着色在相差三种颜色的全局置换下,都与倍增后的基础着色完全相同。由于该最优着色配置在倍增联盟下继承了原始构造的不稳定性,因此没有最优着色可以是强平衡(maxcut_pinned_twins_refutes_of_rigidity)。因此,对于 $k = 3$,社会最优性与联盟稳定性并非总能兼得。

2. 预备知识

我们回顾有限简单图上无权最大 $k$-割博弈的形式化设定,并具体说明形式化中使用的图构造与稳定性概念。

定义 1(无权最大 $k$-割博弈)。设 $G = (V, E)$ 是一个邻接关系可判定的有限简单图,并设 $k \ge 3$ 为整数。着色是一个函数 $\sigma : V \to \{0, \dots, k-1\}$,在 Lean 中表示为 $\sigma : V \to \text{Fin } k$。顶点 $v \in V$ 在着色 $\sigma$ 下的效用是分配了与 $\sigma(v)$ 不同颜色的 $v$ 的邻居数量: $$u_v(\sigma) = \sum_{u \in V, \, G.\text{Adj } u \, v} \mathbf{1}_{\sigma(u) \ne \sigma(v)}.$$ $\sigma$ 的割值是割边集 $E(\sigma) = \{\{u, v\} \in E : \sigma(u) \ne \sigma(v)\}$ 的基数。着色配置的总社会福利为 $\sum_{v \in V} u_v(\sigma) = 2 |E(\sigma)|$。

定义 2(最优着色)。如果着色 $\sigma : V \to \text{Fin } k$ 在所有着色中最大化了割值,则称其在 $G$ 上的最大 $k$-割博弈中是最优的: $$\sum_{v \in V} u_v(\sigma) \ge \sum_{v \in V} u_v(\sigma') \quad \text{for all } \sigma' : V \to \text{Fin } k.$$

定义 3(强平衡)。如果不存在非空联盟 $C \subseteq V$ 可以联合偏离到着色 $\tau : C \to \text{Fin } k$ 使得 $C$ 的每个成员都严格获益,则称着色配置 $\sigma : V \to \text{Fin } k$ 为强平衡。也就是说,令 $\sigma' : V \to \text{Fin } k$ 定义为当 $v \in C$ 时 $\sigma'(v) = \tau(v)$,当 $v \notin C$ 时 $\sigma'(v) = \sigma(v)$,不存在任何非空 $C \subseteq V$ 和 $\tau : C \to \text{Fin } k$ 使得 $$u_v(\sigma') > u_v(\sigma) \quad \text{for all } v \in C.$$

定义 4(最优强平衡性质,maxcut_has_optimal_strong_equilibrium)。如果存在一个同时为最优且为强平衡的着色 $\sigma : V \to \text{Fin } k$,则有限简单图 $G$ 在无权最大 $k$-割博弈中存在最优强平衡: $$\text{maxcut\_has\_optimal\_strong\_equilibrium } G \, k \iff \exists \sigma : V \to \text{Fin } k, \, \sigma \text{ is optimal} \wedge \sigma \text{ is a strong equilibrium}.$$

定义 5(基础锚图与基础初始着色)。基础图 $G_3$ 定义在不交和类型上: $$V_0 = \text{Fin } 16 \oplus (\text{Fin } 3 \times \text{Fin } 25).$$ 顶点集包含 $16 + 3 \times 25 = 91$ 个顶点,包括 16 个由 $\text{inl } i$(其中 $i \in \{0, \dots, 15\}$)索引的核心顶点,以及 75 个由 $\text{inr } (j, a)$(其中 $j \in \{0, 1, 2\}$ 且 $a \in \{0, \dots, 24\}$)索引的锚顶点。基础着色 $\sigma_0$ 为 $V_0$ 中的每个顶点分配一个 $\text{Fin } 3$ 中的初始颜色。

定义 6(固定孪生图,maxcut_pinned_twins_graph)。候选反例图构造在笛卡尔积类型上: $$V = V_0 \times \text{Fin } 2 = (\text{Fin } 16 \oplus (\text{Fin } 3 \times \text{Fin } 25)) \times \text{Fin } 2,$$ 包含 $91 \times 2 = 182$ 个顶点。对于每个顶点 $w \in V_0$,元素 $(w, 0)$ 和 $(w, 1)$ 表示独立的孪生顶点。边关系由一个二元关系生成,其中 $u$ 和 $v$ 关联当且仅当 $u.1$ 和 $v.1$ 在基础图 $G_3$ 中相邻,或者 $u$ 与 $v$ 之间满足固定关系。固定关系定义为在 $u.1 = \text{inl } i$ 为核心顶点、$v.1 = \text{inr } (j, a)$ 为锚顶点且满足以下三个条件时成立:

  1. $a = 24$,指定该分支的最后一个锚顶点;
  2. $v.2 = 0$,选择该锚顶点的第一个孪生顶点;
  3. $j \ne \sigma_0(\text{inl } i)$,仅连接到与核心顶点初始颜色不同的颜色所对应的分支。

关于定义的注记。Lean 中的简单图构造器会自动去除自环并强制对称性。在该定义下,同一顶点 $w$ 的孪生顶点 $(w, 0)$ 和 $(w, 1)$ 之间没有基础边,因为 $G_3$ 是反自反的;因此,孪生顶点构成大小为 2 的独立集。$G_3$ 中 $w$ 与 $z$ 之间的边诱导出 $\{(w, 0), (w, 1)\}$ 与 $\{(z, 0), (z, 1)\}$ 之间的完全二分图 $K_{2,2}$。固定关系在其定义中是非对称的,但在应用简单图生成器后变为对称的。

3. 主要结果

主定理反驳了关于有限简单图上的每个无权最大 $k$-割博弈都存在一个同时为强平衡的最优着色的全称猜想。

定理(最优强平衡存在性的否定解决,maxcut_op89_optimal_strong_equilibrium_negation)。并非对于每个有限类型 $V$、每个具有可判定邻接关系的 $V$ 上的简单图 $G$ 以及每个整数 $k \ge 3$,$G$ 上的无权最大 $k$-割博弈都存在一个作为强平衡的最优着色: $$\neg \, \forall (V : \text{Type}) \, [\text{Fintype } V] \, (G : \text{SimpleGraph } V) \, [\text{DecidableRel } G.\text{Adj}] \, (k : \mathbb{N}), \, 3 \le k \to \text{maxcut\_has\_optimal\_strong\_equilibrium } G \, k.$$

该定理的 Lean 陈述通过对赋予有限类型结构的顶点全域 $V$、具有可判定邻接关系的简单图 $G$ 以及颜色参数 $k \ge 3$ 进行全称量化,断言关于 $G$ 和 $k$ 的命题 maxcut_has_optimal_strong_equilibrium 的否定,从而翻译了英文断言。

该定理通过给出 $k = 3$ 时的一个具体反例来证明,即 182 顶点图 maxcut_pinned_twins_graph。形式化证明基于两个基础引理:

为了结合背景理解此结果,该项目中先前的形式化在结构限制下确立了若干积极的存在性结果:

定理 maxcut_op89_optimal_strong_equilibrium_negation 表明,在超出这些度和大小界限之后,最优强平衡不必存在。

定理 maxcut_op89_optimal_strong_equilibrium_negation (Lean 4 已验证)
theorem maxcut_op89_optimal_strong_equilibrium_negation :
    ¬ ∀ (V : Type) [Fintype V] (G : SimpleGraph V) [DecidableRel G.Adj] (k : ℕ),
      3 ≤ k → maxcut_has_optimal_strong_equilibrium G k

4. 证明

证明思路。在 $G_3$ 上,从 $\sigma_0$ 到 $\tau_0$ 的偏离对该问题无害,因为 $\tau_0$ 是另一个最优点且是稳定的。构建固定孪生图是为了使倍增后的 $\sigma_0$ 在相差颜色重命名下成为唯一的最优点,而倍增后的偏离仍然对每个联盟成员有利。

该构造包含两个部分。首先,$G_3$ 的每个顶点 $w$ 变成两个不相邻的孪生顶点 $(w,0)$ 和 $(w,1)$,并且 $G_3$ 的每条边变成孪生对之间的完全二分图 $K_{2,2}$。其次,对两种颜色 $j \ne \sigma_0(\mathrm{inl}\ i)$ 中的每一种,32 个核心孪生顶点 $(\mathrm{inl}\ i, t)$ 中的每一个都通过固定边连接到锚孪生顶点 $(\mathrm{inr}\ (j,24), 0)$;这是 64 条新边。在倍增着色 $\sigma(w,t) = \sigma_0(w)$ 下,没有任何固定边是单色的。

引理 1(maxcut_pinned_twins_optimum_rigidity)。maxcut_pinned_twins_graph 的每个最大化福利的 3-着色 $\rho$ 对三种颜色的某个置换 $p$ 都满足 $\rho = \lambda v,\ p(\sigma_0(v.1))$。

引理 1 的证明。福利加上有序同色对的数量等于度数和,因此最优着色最小化有序同色对的数量。根据论文中最优性定理(已被形式化),在 $G_3$ 上该最小值为 48(24 条同色边),由 $\sigma_0$ 达到。在孪生图上,倍增后的 $\sigma$ 恰好有 $4 \cdot 48 = 192$ 个有序同色对,且全部位于倍增边上。因此,最优 $\rho$ 至多有 192 个。

关键步骤是一个平均恒等式。对于 $G_3$ 的每个顶点 $w$ 上选择一个孪生顶点 $c(w) \in \{0,1\}$ 的每个选择 $c$,切片 $w \mapsto \rho(w, c(w))$ 是 $G_3$ 的一个 3-着色,因此它至少有 48 个有序同色对。对于 $G_3$ 的一条边 $uw$,在所有 $2^{91}$ 种选择中,四个孪生对 $(s,t)$ 中的每一个都恰好被四分之一的选择所选取。在 Lean 中,这是一个对合论证:在 $u$ 和 $w$ 处翻转 $c$ 置换了这些选择。对所有选择求和可得 $$4 \sum_c \mathrm{mono}_{G_3}(\text{slice}_c) = 2^{91} \cdot B(\rho),$$ 其中 $B(\rho)$ 计数 $\rho$ 在倍增边上的有序同色对。因此 $B(\rho) \ge 4 \cdot 48 = 192$。结合上界可得 $B(\rho) = 192$,没有任何固定边是单色的,且每个切片恰好有 48 个有序同色对。

接下来是论文中的冲突间隙引理。$G_3$ 的每个锚类都是 25 个顶点的独立集,而一个切片只有 24 条同色边。因此,每个锚类都包含一个不在任何同色边上的顶点,这三个顶点构成一个三角形,并且每个锚类都是单色的且具有三种不同的颜色。因此,在相差置换下,每个切片都规范地为锚着色。将处处选取孪生顶点 0 的切片与仅在单个孪生顶点处与之不同的切片进行比较表明,所有 150 个锚孪生顶点都遵循同一个置换 $p$。最后,每个核心孪生顶点 $(\mathrm{inl}\ i, t)$ 对于两个 $j \ne \sigma_0(\mathrm{inl}\ i)$ 都具有颜色为 $p(j)$ 的固定邻居,且这些固定边都不是单色的。因此其颜色为 $p(\sigma_0(\mathrm{inl}\ i))$。

引理 2(maxcut_pinned_twins_refutes_of_rigidity)。如果 maxcut_pinned_twins_graph 的每个最优 3-着色都是倍增后 $\sigma_0$ 的颜色置换,则该图不存在最优强平衡。

引理 2 的证明。由刚性可知,最优着色具有形式 $\rho = p \circ \sigma$。取所有 32 个核心孪生顶点构成的联盟,并让它们变动到 $p \circ \tau$,其中 $\tau(w,t) = \tau_0(w)$。在倍增边上,每个核心孪生顶点看到 $G_3$ 的每个邻居两次,因此其在 $G_3$ 中的 1 单位增益变成了 2 单位增益。由于 $\tau_0$ 将每个核心顶点的颜色变为两个固定锚颜色之一,因此其两条固定边中恰好有一条变为同色,造成 1 单位损失。因此,每个联盟成员恰好获得 1 单位净增益;这是通过在整个图上的内核计算验证的。效用在全局颜色置换下是不变的,因此从 $p \circ \sigma$ 出发的同样偏离也是有效的,从而 $\rho$ 不是强平衡。

主定理的证明。将全称命题在顶点类型 $(\mathrm{Fin}\ 16 \oplus (\mathrm{Fin}\ 3 \times \mathrm{Fin}\ 25)) \times \mathrm{Fin}\ 2$、图 maxcut_pinned_twins_graph 以及 $k = 3$ 处进行实例化。由此可得一个最优强平衡,而将引理 2 应用于引理 1 排除了这种可能性。

5. 讨论

arXiv:2610.04948 中问题 2 的解决阐明了网络博弈中社会最优性与联盟稳定性之间的界限。原始论文证实了最优着色可能不是强平衡,但留下了一个悬而未决的问题:是否每个博弈仍至少拥有一个稳定的最优着色。maxcut_pinned_twins_graph 的构造在 $k = 3$ 时否定地解决了这一问题,表明存在所有最优着色都在联盟意义下不稳定的博弈。

审视该结果如何划定现有积极保证的边界是富有启发性的。先前的工作指出了保证存在最优强平衡的三种情形:

该图不可 3-着色,拥有远多于 $2k+2 = 8$ 个顶点,且最大度远高于 $2k = 6$。因此,度数界限留下的情形(不可 $k$-着色且具有度数至少为 $2k$ 的顶点的图)并不总是存在最优强平衡;这也已被形式化。

若干自然的问题仍然悬而未决:

  • arXiv:2610.04948 的问题 1:是否每个无权最大 $k$-割博弈都存在强平衡(不一定是最优的)?此处的反例否定了最优强平衡的存在性,但并未探讨 maxcut_pinned_twins_graph 或其他图是否存在次优强平衡。
  • 更多颜色数($k \ge 4$):本反例特别针对 $k = 3$。论文中的图 $G_k$ 对每个 $k \ge 3$ 都存在;将其倍增并固定是否对每个 $k$ 都能给出相同的刚性,在此尚未得到证明。
  • 最小反例规模:图 maxcut_pinned_twins_graph 包含 182 个顶点。确定使无权最大 3-割博弈不存在最优强平衡所需的最少顶点数仍是一个未决问题,横跨小基数界限 $|V| \le 6$ 与 182 顶点构造之间的差距。

为什么是研究级成果

  • Answers the paper's Question 2 negatively for k = 3: a 182-vertex graph (the paper's 91-vertex G_3 with every vertex doubled into independent twins, plus pin edges from each core twin to two anchors) has an optimal Max-3-Cut coloring that is unique up to color permutation and not a strong equilibrium, so no optimal coloring is a strong equilibrium. The paper only shows that some optimal coloring can fail

Lean 声明

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

参考文献

  1. arXiv:2610.04948 — Social Optimality Does Not Imply Coalitional Stability in Unweighted Max-k-Cut Games

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