每个加权投票博弈在所有简单博弈中均由其摆动表唯一确定
medium tier2026-10-02OP-49审阅: Claude CodeEnglish
摘要
在 arXiv:2607.07013 中作为猜想 10.2 提出的摆动刚性猜想探讨了:在所有简单博弈中,是否每个加权投票博弈(WVG)都由其摆动表唯一确定。尽管不同的非加权简单博弈可以具有完全相同的摆动表——从而使它们无法被任何半值所区分——但加权博弈被猜想是刚性的。该问题得到了肯定的回答:在所有简单博弈中,每个加权投票博弈均由其摆动表唯一确定。证明过程首先确立了任意简单博弈的摆动表唯一确定每个基数的获胜联盟数量,以及包含每个特定局中人的每个基数的获胜联盟数量。对这些计数求和可以恢复获胜联盟的总数以及包含每个局中人的获胜联盟数量。根据刻画定理 weighted_game_eq_of_chow_parameters_eq,这些参数在联盟上的所有布尔函数中唯一确定一个加权博弈。因此,如果一个加权简单博弈与任意一个简单博弈具有相同的摆动表,则它们必然重合。整个结果及其辅助引理已在 Lean 4 中形式化验证,对应定理为 weighted_game_eq_of_swing_table_eq。
1. 引言
在投票理论与合作博弈论中,简单博弈通过为局中人的每个联盟赋予一个二元结果(获胜或失败)来对集体决策机构进行建模。理解局中人之间权力分配的核心问题是评估跨联盟的边际贡献。若对于不包含局中人 $i$ 的联盟 $S$,$S$ 是失败联盟而扩充后的联盟 $S \cup \{i\}$ 是获胜联盟,则称局中人 $i$ 在联盟 $S$ 处具有摆动。博弈的摆动表按局中人和联盟大小组织这些关键事件:表项 $T(i, k)$ 记录不包含局中人 $i$ 且局中人 $i$ 在其上具有摆动的大小为 $k$ 的联盟数量。
在 arXiv:2607.07013 中,研究了匿名边际值(称为半值)的信息极限。半值通过跨大小的摆动表表项的线性组合来评估局中人的权力,其权重系数仅取决于联盟大小。arXiv:2607.07013 中记录的一个基本观察是,不同的简单博弈可以具有完全相同的摆动表。每当两个博弈拥有相同的摆动表时,任何半值都会为两个博弈中的所有局中人分配完全相同的权力剖面。因此,半值无法区分产生相同摆动表的博弈。
这种二义性引出了一个问题:某些特殊类别的简单博弈是否拥有唯一的摆动表。在简单博弈中,加权投票博弈——其中每个局中人拥有一个非负权重,且一个联盟获胜当且仅当其总权重达到或超过指定配额——构成了被研究最广泛的族系。在 arXiv:2607.07013 中,第 10 节中的猜想 10.2(亦作为第 11 节的未决问题之一提出)给出了摆动刚性猜想:在所有简单博弈中,每个加权投票博弈均由其摆动表唯一确定。换言之,若 $f$ 是一个加权简单博弈,而 $g$ 是与 $f$ 具有相同摆动表的任意简单博弈,则 $f = g$。
根据 arXiv:2607.07013,广泛的计算机研究为该猜想提供了经验支持:对 $n = 5$ 个局中人的所有简单博弈的详尽普查,以及对 $n = 6$ 和 $n = 7$ 个局中人的广泛计算搜索,均未发现与任何其他简单博弈共享摆动表的加权投票博弈。尽管如此,一般性问题仍未得到解决。
本文给出了猜想 10.2 的完整数学解答,对所有局中人数量 $n$ 肯定地解决了这一未决问题。形式化定理 weighted_game_eq_of_swing_table_eq 证明了若 $f$ 是加权简单博弈且 $g$ 是具有相同摆动表的任意简单博弈,则 $f$ 与 $g$ 相同。该证明建立了一个显式递推关系,表明任意简单博弈的摆动表唯一确定每个基数的获胜联盟数量,以及包含每个指定局中人的每个基数的获胜联盟数量。对这些按层计数求和表明,$f$ 与 $g$ 的获胜联盟总数以及单个局中人的获胜计数完全一致。随后,该结果由在 weighted_game_eq_of_chow_parameters_eq 中形式化的刻画定理得出,该定理确立了这些参数在联盟上的所有布尔函数中唯一刻画任意加权博弈。
2. 预备知识
令 $n \in \mathbb{N}$ 表示局中人数量,由集合 $\{0, 1, \dots, n-1\}$ 索引,对应于 Lean 中的有限类型 Fin $n$。局中人的联盟表示为有限集,对应于 Finset (Fin $n$)。博弈由布尔函数 $v : \mathcal{P}([n]) \to \{0, 1\}$ 表示,在 Lean 中形式化为类型 Finset (Fin $n$) → Bool,其中求值为 true 的联盟为获胜联盟,求值为 false 的联盟为失败联盟。
定义 1(is_simple_game)。若布尔函数 $v : \mathcal{P}([n]) \to \{0, 1\}$ 满足以下条件,则称其为简单博弈:
- 单调性:对所有联盟 $S, T \subseteq [n]$,若 $S \subseteq T$ 且 $v(S) = \text{true}$,则 $v(T) = \text{true}$;
- 规范性:$v(\emptyset) = \text{false}$ 且 $v([n]) = \text{true}$。
注 1。在 Lean 形式化 is_simple_game 中,$v$ 的定义域为 Finset (Fin $n$),其陪域为 Bool。单调性使用子集关系 $S \subseteq T$ 以及布尔等式之间的命题蕴涵 $v(S) = \text{true} \implies v(T) = \text{true}$ 来表示。规范性条件确保空联盟严格为失败联盟,而大联盟 Finset.univ 严格为获胜联盟。
定义 2(is_weighted_game)。若存在权重向量 $w : [n] \to \mathbb{R}$ 和配额 $q \in \mathbb{R}$ 满足以下条件,则布尔函数 $v : \mathcal{P}([n]) \to \{0, 1\}$ 为加权博弈: 1. 局中人权重非负:对所有 $i \in [n]$,有 $0 \le w(i)$; 2. 联盟 $S \subseteq [n]$ 获胜当且仅当其累积权重达到配额: $$v(S) = \text{true} \iff q \le \sum_{i \in S} w(i).$$
注 2。在 is_weighted_game 中,权重 $w(i)$ 和配额 $q$ 取值于实数集 $\mathbb{R}$。局中人权重由弱不等式 $0 \le w(i)$ 约束,阈值条件同样是一个弱不等式 $q \le \sum_{i \in S} w(i)$。空联盟 $\emptyset$ 上的求和求值为 $0$。此外,定义 is_weighted_game 本身并不强制要求边界条件 $v(\emptyset) = \text{false}$ 或 $v([n]) = \text{true}$;当一个博弈既是简单博弈又是加权博弈时,同时假设 is_simple_game 与 is_weighted_game。
定义 3(swing_table)。对于布尔函数 $v : \mathcal{P}([n]) \to \{0, 1\}$、局中人 $i \in [n]$ 以及整数 $k \in \mathbb{N}$,摆动表表项 $T(i, k)$(记作 swing_table $v\ i\ k$)是不包含局中人 $i$ 且使得 $S$ 为失败联盟而 $S \cup \{i\}$ 为获胜联盟的基数为 $k$ 的联盟 $S \subseteq [n]$ 的数量: $$T(i, k) = \left| \{ S \subseteq [n] : i \notin S \wedge |S| = k \wedge v(S \cup \{i\}) = \text{true} \wedge v(S) = \text{false} \} \right|.$$
注 3。在 swing_table 中,表项对所有 $k : \mathbb{N}$ 和所有 $i : \text{Fin } n$ 均有定义。当 $k \ge n$ 时,对于 $S \subseteq [n] \setminus \{i\}$,过滤条件 $|S| = k$ 无法满足,因此摆动表表项为零。关键在于,大小参数 $k$ 指定了在加入局中人 $i$ 之前的基础联盟 $S$ 的大小,因此获胜联盟 $S \cup \{i\}$ 的基数为 $k+1$。该定义适用于任意布尔函数 $v$,尽管在我们的结果中它被应用于满足 is_simple_game 的博弈。
3. 主要结果
主定理确立了一个加权简单博弈与任意简单博弈之间摆动表的相等蕴涵这两个博弈完全相同。
定理(weighted_game_eq_of_swing_table_eq)。令 $n \in \mathbb{N}$。令 $f, g : \mathcal{P}([n]) \to \{0, 1\}$ 为 $n$ 个局中人的联盟上的布尔函数。假设: 1. $f$ 是简单博弈(is_simple_game $f$); 2. $f$ 是加权博弈(is_weighted_game $f$); 3. $g$ 是简单博弈(is_simple_game $g$); 4. $f$ 和 $g$ 具有相同的摆动表:对所有 $i \in [n]$ 以及所有 $k \in \mathbb{N}$, $$\text{swing\_table } f\ i\ k = \text{swing\_table } g\ i\ k.$$ 则 $f = g$。
Lean 定理 weighted_game_eq_of_swing_table_eq 针对任意自然数局中人数量 $n$ 上的类型为 Finset (Fin $n$) → Bool 的函数 $f, g$ 形式化了这一陈述,它接受假设 (hf : is_simple_game f)、(hfw : is_weighted_game f)、(hg : is_simple_game g) 和 (h : ∀ i k, swing_table f i k = swing_table g i k),并在对维数没有任何限制的情况下得出命题等式 $f = g$。
这一主要结果依赖于阐明摆动表所传达的确切信息的三个辅助引理:
- 引理 simple_game_card_winning_eq_of_swing_table_eq 补充了简单博弈中获胜联盟的总数完全由其摆动表决定的事实。对于具有相同摆动表的任意两个简单博弈 $f$ 和 $g$, $$|\{ S \subseteq [n] : f(S) = \text{true} \}| = |\{ S \subseteq [n] : g(S) = \text{true} \}|.$$
- 引理 simple_game_card_winning_mem_eq_of_swing_table_eq 补充了对于每个单独的局中人 $i$,包含 $i$ 的获胜联盟数量也是摆动表的不变量: $$|\{ S \subseteq [n] : i \in S \wedge f(S) = \text{true} \}| = |\{ S \subseteq [n] : i \in S \wedge g(S) = \text{true} \}|.$$
- 引理 weighted_game_eq_of_chow_parameters_eq 给出了决定性定理:若 $f$ 是加权博弈,$g$ 是联盟上的任意布尔函数,使得 $f$ 和 $g$ 具有相同数量的获胜联盟总数,且对每个局中人 $i$,包含 $i$ 的获胜联盟数量相同,则 $f = g$。
这些引理共同表明,摆动表决定了完整的 0 度和 1 度联盟参数,而这些参数反过来又唯一刻画了任意加权博弈。
theorem weighted_game_eq_of_swing_table_eq {n : ℕ} (f g : Finset (Fin n) → Bool)
(hf : is_simple_game f) (hfw : is_weighted_game f) (hg : is_simple_game g)
(h : ∀ i k, swing_table f i k = swing_table g i k) : f = g4. 证明
证明思路: 该证明仅从摆动表出发,重构了每个基数的获胜联盟数量,以及包含每个指定局中人的每个基数的获胜联盟数量。 对于任意简单博弈 $v$,令 $w_k(v)$ 表示基数为 $k$ 的获胜联盟数量。由单调性可知,不包含局中人 $i$ 的联盟 $S$ 产生获胜联盟 $S \cup \{i\}$ 当且仅当 $S$ 本身已获胜或者 $S$ 是 $i$ 的摆动。 将该关系对所有局中人求和并通过对局中人归属进行双重计数,可得到关于 $w_{k+1}(v)$ 的单步递推关系,用 $w_k(v)$ 和行和 $\sum_i T(i, k)$ 表示。由于 $v(\emptyset) = \text{false}$,我们有 $w_0(v) = 0$,因此所有的 $w_k(v)$ 以及获胜总数 $\sum_k w_k(v)$ 都被确定。 一个相伴的递推关系确定了包含局中人 $i$ 的获胜联盟计数。在总计数和针对特定局中人的计数均匹配的情况下,weighted_game_eq_of_chow_parameters_eq 证明了 $f = g$。
引理 1(simple_game_card_winning_eq_of_swing_table_eq)。 令 $f, g : \mathcal{P}([n]) \to \{0, 1\}$ 为满足 is_simple_game f 和 is_simple_game g 的简单博弈。若对所有 $i \in [n]$ 和 $k \in \mathbb{N}$ 均有 swing_table $f\ i\ k =$ swing_table $g\ i\ k$,则 $$|\{ S \subseteq [n] : f(S) = \text{true} \}| = |\{ S \subseteq [n] : g(S) = \text{true} \}|.$$
引理 1 的证明: 对于简单博弈 $v$,令 $w_k(v) = |\{S : |S| = k \wedge v(S) = \text{true}\}|$。 对于局中人 $i$,令 $W_{k, i}(v)$ 为包含 $i$ 的大小为 $k$ 的获胜联盟,令 $W_{k, \setminus i}(v)$ 为不包含 $i$ 的那些获胜联盟。 则 $w_k(v) = |W_{k, i}(v)| + |W_{k, \setminus i}(v)|$。 根据 is_simple_game 中的单调性,大小为 $k$ 的 $S \subseteq [n] \setminus \{i\}$ 满足 $v(S \cup \{i\}) = \text{true}$ 当且仅当 $v(S) = \text{true}$ 或 $S$ 是 $i$ 的摆动。因此: $$|W_{k+1, i}(v)| = |W_{k, \setminus i}(v)| + \text{swing\_table } v\ i\ k = w_k(v) - |W_{k, i}(v)| + \text{swing\_table } v\ i\ k.$$ 对所有 $n$ 个局中人 $i$ 求和,双重计数给出 $\sum_i |W_{k+1, i}(v)| = (k+1) w_{k+1}(v)$ 以及 $\sum_i |W_{k, i}(v)| = k w_k(v)$。于是: $$(k+1) w_{k+1}(v) - (n - k) w_k(v) = \sum_{i=0}^{n-1} \text{swing\_table } v\ i\ k.$$ 移项重排得: $$w_{k+1}(v) = \frac{1}{k+1} \left( (n - k) w_k(v) + \sum_{i=0}^{n-1} \text{swing\_table } v\ i\ k \right).$$ 由于 $v(\emptyset) = \text{false}$,有 $w_0(v) = 0$。由归纳法,每个 $w_k(v)$ 均由摆动表决定。 由于 $f$ 和 $g$ 共享摆动表,对所有 $k$ 均有 $w_k(f) = w_k(g)$,因此 $\sum_k w_k(f) = \sum_k w_k(g)$。
引理 2(simple_game_card_winning_mem_eq_of_swing_table_eq)。 令 $f, g : \mathcal{P}([n]) \to \{0, 1\}$ 为满足 is_simple_game f 和 is_simple_game g 的简单博弈。若对所有 $i \in [n]$ 和 $k \in \mathbb{N}$ 均有 swing_table $f\ i\ k =$ swing_table $g\ i\ k$,则对每个局中人 $i \in [n]$, $$|\{ S \subseteq [n] : i \in S \wedge f(S) = \text{true} \}| = |\{ S \subseteq [n] : i \in S \wedge g(S) = \text{true} \}|.$$
引理 2 的证明: 固定局中人 $i$。引理 1 中的关系式给出: $$|W_{k+1, i}(v)| = \text{swing\_table } v\ i\ k + w_k(v) - |W_{k, i}(v)|.$$ 由于 $|W_{0, i}(v)| = 0$ 且每个 $w_k(v)$ 均通过引理 1 由摆动表确定,该递推关系通过归纳法唯一确定了所有 $k \ge 0$ 的 $|W_{k, i}(v)|$。 相同的摆动表意味着对每个 $k$ 均有 $|W_{k, i}(f)| = |W_{k, i}(g)|$。 对 $k \in \{1, \dots, n\}$ 求和即得出包含 $i$ 的获胜联盟数量相等。
引理 3(weighted_game_eq_of_chow_parameters_eq)。 令 $f, g : \mathcal{P}([n]) \to \{0, 1\}$ 为布尔函数。假设 is_weighted_game f,且满足: 1. $|\{ S : f(S) = \text{true} \}| = |\{ S : g(S) = \text{true} \}|$; 2. 对所有 $i \in [n]$,$|\{ S : i \in S \wedge f(S) = \text{true} \}| = |\{ S : i \in S \wedge g(S) = \text{true} \}|$。 则 $f = g$。
引理 3 的证明: 设 $f$ 具有非负权重 $w(i) \ge 0$ 和配额 $q \in \mathbb{R}$,因此 $f(S) = \text{true} \iff \sum_{i \in S} w(i) \ge q$。 定义 $L(S) = \sum_{i \in S} w(i) - q$。对每个 $S \subseteq [n]$,乘积 $(f(S) - g(S)) L(S) \ge 0$,因为每当 $f(S) \ne g(S)$ 时,$f(S) - g(S)$ 与 $L(S)$ 具有相同的符号。 对所有 $S \subseteq [n]$ 求和: $$\sum_S (f(S) - g(S)) L(S) = \sum_{i=0}^{n-1} w(i) \left( \sum_{S: i \in S} (f(S) - g(S)) \right) - q \sum_S (f(S) - g(S)).$$ 右边的两个和根据假设 (1) 和 (2) 均归零,从而得到 $\sum_S (f(S) - g(S)) L(S) = 0$。 由于每个求和项都是非负的,每个求和项都必须为零,这迫使对所有 $S$ 均有 $f(S) = g(S)$,在 Lean 中已确立为 weighted_game_eq_of_chow_parameters_eq。
组合论证: 定理 weighted_game_eq_of_swing_table_eq 直接组合了这些结果。 假设 (hf : is_simple_game f)、(hg : is_simple_game g) 和 (h : ∀ i k, swing_table f i k = swing_table g i k) 为引理 1(simple_game_card_winning_eq_of_swing_table_eq)和引理 2(simple_game_card_winning_mem_eq_of_swing_table_eq)提供了输入。 这些条件与 (hfw : is_weighted_game f) 一起,为引理 3(weighted_game_eq_of_chow_parameters_eq)提供了完全相同的前提条件,从而确立了 $f = g$。
实例验证: 考虑 $n = 3$ 个局中人的多数决博弈 $f$,其权重为 $w = (1, 1, 1)$,配额为 $q = 2$。 获胜联盟为 $\{ \{0, 1\}, \{0, 2\}, \{1, 2\}, \{0, 1, 2\} \}$,给出 $w_0 = 0, w_1 = 0, w_2 = 3, w_3 = 1$(总数为 4)。 包含局中人 $0$ 的获胜联盟为 $\{0, 1\}, \{0, 2\}, \{0, 1, 2\}$(总数为 3)。 局中人 $0$ 的摆动表表项为: - $k = 0$:$S = \emptyset$;$f(\emptyset) = \text{false}, f(\{0\}) = \text{false}$,因此 $T(0, 0) = 0$。 - $k = 1$:$S \in \{\{1\}, \{2\}\}$;每个均为失败联盟且加入 $0$ 后获胜,因此 $T(0, 1) = 2$。 - $k = 2$:$S = \{1, 2\}$ 为获胜联盟,因此 $T(0, 2) = 0$。 由对称性,对所有 $i$ 均有 $T(i, 0) = 0, T(i, 1) = 2, T(i, 2) = 0$。 应用带有 $w_0 = 0$ 的引理 1: - $w_1 = (3 \cdot 0 + 0) / 1 = 0$; - $w_2 = (2 \cdot 0 + 6) / 2 = 3$; - $w_3 = (1 \cdot 3 + 0) / 3 = 1$。 总计数为 $0 + 0 + 3 + 1 = 4$。 应用针对局中人 $0$ 且 $|W_{0, 0}| = 0$ 的引理 2: - $|W_{1, 0}| = 0 + 0 - 0 = 0$; - $|W_{2, 0}| = 2 + 0 - 0 = 2$; - $|W_{3, 0}| = 0 + 3 - 2 = 1$。 包含局中人 $0$ 的总数为 $0 + 2 + 1 = 3$。具有此摆动表的任意简单博弈 $g$ 都会产生相同的计数,从而迫使 $g = f$。
5. 讨论
定理 weighted_game_eq_of_swing_table_eq 对 arXiv:2607.07013 中的猜想 10.2(摆动刚性猜想)给出了肯定回答,解决了该论文第 11 节中强调的未决问题。该结果确立了加权投票博弈在摆动表映射下是完全刚性的:没有任何加权简单博弈能够与任何其他简单博弈(无论是否加权)共享其摆动表。
应当强调该结果不涵盖的内容。此处确立的刚性现象是加权博弈类所特有的。正如 arXiv:2607.07013 中所确立的,一般的简单博弈并不具有摆动刚性:存在共享完全相同摆动表的不同非加权简单博弈对。因为任何半值都是通过跨大小的摆动表表项的线性组合来评估局中人权力,所以此类非加权博弈对完全无法被任何半值所区分。定理 weighted_game_eq_of_swing_table_eq 表明这种二义性严格局限于非加权博弈:加权博弈绝不可能与非加权博弈相混淆,两个不同的加权博弈也绝不可能具有相同的摆动表。
此外,在 simple_game_card_winning_eq_of_swing_table_eq 和 simple_game_card_winning_mem_eq_of_swing_table_eq 中建立的递推关系关键取决于 is_simple_game 的性质,具体而言是单调性条件($S \subseteq T \implies v(S) = \text{true} \implies v(T) = \text{true}$)和边界条件 $v(\emptyset) = \text{false}$。若没有单调性,将扩充获胜用获胜基础联盟和摆动来表示的恒等式便不再成立,因为局中人的加入可能会使获胜联盟变为失败联盟。
猜想 10.2 的解决将人们的注意力引向 arXiv:2607.07013 第 11 节中关于摆动表映射结构的更广泛问题。当两个非加权简单博弈共享摆动表时,需要哪些额外的非匿名边际信息来区分它们?除加权博弈外,是否存在其他表现出摆动刚性的简单博弈自然子族?arXiv:2607.07013 中记录的 $n = 5$ 处的计算普查以及 $n = 6, 7$ 处的搜索勾勒出了共享摆动表的博弈的初步实例;刻画简单博弈空间上摆动表映射的完整纤维仍是一个活跃的研究方向。
为什么是研究级成果
- settles OP-49 (Swing rigidity of weighted voting games)
Lean 声明
- weighted_game_eq_of_swing_table_eqThe swing-rigidity conjecture (arXiv:2607.07013, Conjecture 10.2) is true: if f is a weighted simple game and g is any simple game with…
- weighted_game_eq_of_chow_parameters_eqChow's theorem for games: if f is weighted and g is any 0/1-valued function on coalitions with the same number of winning coalitions and,…
- is_simple_gameA simple game on n players is a monotone function v from coalitions to {0,1} with v(empty) = 0 and v(all players) = 1; the coalitions with…
- is_weighted_gameA game is weighted if there are nonnegative player weights w and a quota q such that a coalition wins exactly when its total weight is at…
- swing_tableThe swing table of a game: T(i, k) is the number of coalitions S of size k not containing i such that S together with i wins while S loses.
- simple_game_card_winning_eq_of_swing_table_eqIf two simple games have the same swing table, they have the same number of winning coalitions.
- simple_game_card_winning_mem_eq_of_swing_table_eqIf two simple games have the same swing table, then for every player i they have the same number of winning coalitions containing i.
Each one elaborated against Mathlib, and #print axioms returned
nothing outside Classical.choice · Quot.sound · propext.
参考文献
- arXiv:2607.07013 — What Semivalues Cannot See: The Information Content of Anonymous Marginal Values
由 gemini-3.8-flash 根据知识库起草,经过检查并由 Claude Code 审阅英文版;中文版由模型翻译并对照英文检查。只有 Lean 部分经过验证,文字是对它的解读。