Every Weighted Voting Game Is Uniquely Determined Among All Simple Games by Its Swing Table
medium tier2026-10-02OP-49reviewed by Claude Code中文版
Abstract
The swing-rigidity conjecture, posed as Conjecture 10.2 in arXiv:2607.07013, asks whether every weighted voting game is uniquely determined by its swing table among all simple games. While distinct non-weighted simple games can share identical swing tables—leaving them indistinguishable by any semivalue—weighted games were conjectured to be rigid. This question is answered in the affirmative: every weighted voting game is uniquely determined by its swing table among all simple games. The proof proceeds by establishing that the swing table of any simple game uniquely determines the number of winning coalitions of each cardinality, as well as the number of winning coalitions of each cardinality containing each individual player. Summing these counts recovers the total number of winning coalitions and the number of winning coalitions containing each player. By the characterization theorem weighted_game_eq_of_chow_parameters_eq, these parameters uniquely determine a weighted game among all Boolean functions on coalitions. Consequently, if a weighted simple game and any simple game share a swing table, they must coincide. The entire result and its supporting lemmas have been formally verified in Lean 4 under the theorem weighted_game_eq_of_swing_table_eq.
1. Introduction
In voting theory and cooperative game theory, simple games model collective decision-making bodies by assigning to each coalition of players a binary outcome: winning or losing. A central problem in understanding the power distribution among players is evaluating marginal contributions across coalitions. A player $i$ is said to have a swing at a coalition $S$ not containing $i$ if $S$ is losing but the augmented coalition $S \cup \{i\}$ is winning. The swing table of a game organizes these critical events by player and by coalition size: entry $T(i, k)$ records the number of coalitions of size $k$ not containing player $i$ for which player $i$ is a swing.
In arXiv:2607.07013, the informational limits of anonymous marginal values—known as semivalues—are investigated. Semivalues evaluate player power through linear combinations of swing table entries across sizes, weighted by coefficients that depend solely on coalition size. A fundamental observation documented in arXiv:2607.07013 is that distinct simple games can share identical swing tables. Whenever two games possess the same swing table, every semivalue assigns the exact same power profile to all players in both games. Consequently, semivalues cannot distinguish between games that yield identical swing tables.
This ambiguity motivates the question of whether special classes of simple games possess unique swing tables. Among simple games, weighted voting games—where each player possesses a non-negative weight and a coalition wins if and only if its total weight meets or exceeds a specified quota—form the most widely studied family. In arXiv:2607.07013, Conjecture 10.2 in Section 10, also presented among the open problems in Section 11, formulates the swing rigidity conjecture: every weighted voting game is uniquely determined by its swing table among all simple games. In other words, if $f$ is a weighted simple game and $g$ is any simple game sharing the same swing table as $f$, then $f = g$.
According to arXiv:2607.07013, extensive computer investigations provided empirical support for this conjecture: an exhaustive census of all simple games on $n = 5$ players, alongside extensive computational searches on $n = 6$ and $n = 7$ players, revealed no weighted voting game that shares its swing table with any other simple game. Nevertheless, the general question remained unresolved.
This post presents a complete mathematical resolution of Conjecture 10.2, settling the open problem in the affirmative for all player counts $n$. The formalized theorem, weighted_game_eq_of_swing_table_eq, proves that if $f$ is a weighted simple game and $g$ is any simple game with the same swing table, then $f$ and $g$ are identical. The proof establishes an explicit recurrence showing that the swing table of any simple game uniquely determines the number of winning coalitions of each cardinality, as well as the number of winning coalitions of each cardinality containing each designated player. Summing these layer counts reveals that the total number of winning coalitions and the individual player winning counts coincide between $f$ and $g$. The result then follows from the characterization theorem formalized in weighted_game_eq_of_chow_parameters_eq, which establishes that these parameters uniquely characterize any weighted game among all Boolean functions on coalitions.
2. Preliminaries
Let $n \in \mathbb{N}$ denote the number of players, indexed by the set $\{0, 1, \dots, n-1\}$, which corresponds to the finite type Fin $n$ in Lean. Coalitions of players are represented as finite sets, corresponding to Finset (Fin $n$). A game is represented by a Boolean function $v : \mathcal{P}([n]) \to \{0, 1\}$, formalized in Lean with type Finset (Fin $n$) → Bool, where coalitions evaluating to true are winning and those evaluating to false are losing.
Definition 1 (is_simple_game). A Boolean function $v : \mathcal{P}([n]) \to \{0, 1\}$ is a simple game if it satisfies:
- Monotonicity: for all coalitions $S, T \subseteq [n]$, if $S \subseteq T$ and $v(S) = \text{true}$, then $v(T) = \text{true}$;
- Normalization: $v(\emptyset) = \text{false}$ and $v([n]) = \text{true}$.
Remark 1. In the Lean formalization is_simple_game, the domain of $v$ is Finset (Fin $n$) and its codomain is Bool. Monotonicity is expressed using the subset relation $S \subseteq T$ and propositional implication between boolean equalities $v(S) = \text{true} \implies v(T) = \text{true}$. The normalization conditions ensure that the empty coalition is strictly losing while the grand coalition Finset.univ is strictly winning.
Definition 2 (is_weighted_game). A Boolean function $v : \mathcal{P}([n]) \to \{0, 1\}$ is a weighted game if there exist a weight vector $w : [n] \to \mathbb{R}$ and a quota $q \in \mathbb{R}$ such that: 1. Player weights are non-negative: $0 \le w(i)$ for all $i \in [n]$; 2. A coalition $S \subseteq [n]$ wins if and only if its accumulated weight reaches the quota: $$v(S) = \text{true} \iff q \le \sum_{i \in S} w(i).$$
Remark 2. In is_weighted_game, the weights $w(i)$ and the quota $q$ take values in the real numbers $\mathbb{R}$. The player weights are constrained by a weak inequality $0 \le w(i)$, and the threshold condition is likewise a weak inequality $q \le \sum_{i \in S} w(i)$. The sum over the empty coalition $\emptyset$ evaluates to $0$. Furthermore, the definition is_weighted_game does not inherently mandate the boundary conditions $v(\emptyset) = \text{false}$ or $v([n]) = \text{true}$; when a game is both simple and weighted, both is_simple_game and is_weighted_game are hypothesized simultaneously.
Definition 3 (swing_table). For a Boolean function $v : \mathcal{P}([n]) \to \{0, 1\}$, a player $i \in [n]$, and an integer $k \in \mathbb{N}$, the swing table entry $T(i, k)$, denoted swing_table $v\ i\ k$, is the number of coalitions $S \subseteq [n]$ of cardinality $k$ not containing player $i$ such that $S$ is losing and $S \cup \{i\}$ is winning: $$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|.$$
Remark 3. In swing_table, the entry is defined for all $k : \mathbb{N}$ and all $i : \text{Fin } n$. When $k \ge n$, the filter condition $|S| = k$ for $S \subseteq [n] \setminus \{i\}$ cannot be satisfied, so the swing table entry is zero. Crucially, the size parameter $k$ designates the size of the base coalition $S$ prior to the insertion of player $i$, so the winning coalition $S \cup \{i\}$ has cardinality $k+1$. The definition is applicable to any Boolean function $v$, though in our results it is applied to games satisfying is_simple_game.
3. Main result
The main theorem establishes that equality of swing tables between a weighted simple game and any simple game implies that the two games are identical.
Theorem (weighted_game_eq_of_swing_table_eq). Let $n \in \mathbb{N}$. Let $f, g : \mathcal{P}([n]) \to \{0, 1\}$ be Boolean functions on coalitions of $n$ players. Assume that: 1. $f$ is a simple game (is_simple_game $f$); 2. $f$ is a weighted game (is_weighted_game $f$); 3. $g$ is a simple game (is_simple_game $g$); 4. $f$ and $g$ share identical swing tables: for all $i \in [n]$ and all $k \in \mathbb{N}$, $$\text{swing\_table } f\ i\ k = \text{swing\_table } g\ i\ k.$$ Then $f = g$.
The Lean theorem weighted_game_eq_of_swing_table_eq formalizes this statement for functions $f, g$ of type Finset (Fin $n$) → Bool over an arbitrary natural number of players $n$, taking the hypotheses (hf : is_simple_game f), (hfw : is_weighted_game f), (hg : is_simple_game g), and (h : ∀ i k, swing_table f i k = swing_table g i k), and concluding the propositional equality $f = g$ without any restriction on the dimension.
This main result rests on three supporting lemmas that clarify the exact information conveyed by the swing table:
- Lemma simple_game_card_winning_eq_of_swing_table_eq adds the fact that the total number of winning coalitions in a simple game is completely determined by its swing table. For any two simple games $f$ and $g$ with identical swing tables, $$|\{ S \subseteq [n] : f(S) = \text{true} \}| = |\{ S \subseteq [n] : g(S) = \text{true} \}|.$$
- Lemma simple_game_card_winning_mem_eq_of_swing_table_eq adds that for each individual player $i$, the number of winning coalitions containing $i$ is also an invariant of the swing table: $$|\{ S \subseteq [n] : i \in S \wedge f(S) = \text{true} \}| = |\{ S \subseteq [n] : i \in S \wedge g(S) = \text{true} \}|.$$
- Lemma weighted_game_eq_of_chow_parameters_eq provides the determination theorem: if $f$ is a weighted game and $g$ is any Boolean function on coalitions such that $f$ and $g$ have the same total number of winning coalitions and, for each player $i$, the same number of winning coalitions containing $i$, then $f = g$.
Together, these lemmas show that the swing table determines the complete degree-0 and degree-1 coalition parameters, which in turn uniquely characterize any weighted game.
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. Proof
Proof Idea: The proof reconstructs, from the swing table alone, both the number of winning coalitions of each cardinality and the number of winning coalitions of each cardinality containing each designated player. For any simple game $v$, let $w_k(v)$ denote the number of winning coalitions of cardinality $k$. By monotonicity, a coalition $S$ not containing player $i$ yields a winning coalition $S \cup \{i\}$ if and only if either $S$ is already winning or $S$ is a swing for $i$. Summing this relation over all players and double-counting player memberships yields a step recurrence for $w_{k+1}(v)$ in terms of $w_k(v)$ and the row sums $\sum_i T(i, k)$. Because $v(\emptyset) = \text{false}$, we have $w_0(v) = 0$, so all $w_k(v)$ and the total winning count $\sum_k w_k(v)$ are determined. A companion recurrence determines the counts of winning coalitions containing player $i$. With total and player-specific counts matching, weighted_game_eq_of_chow_parameters_eq proves $f = g$.
Lemma 1 (simple_game_card_winning_eq_of_swing_table_eq). Let $f, g : \mathcal{P}([n]) \to \{0, 1\}$ be simple games satisfying is_simple_game f and is_simple_game g. If swing_table $f\ i\ k =$ swing_table $g\ i\ k$ for all $i \in [n]$ and $k \in \mathbb{N}$, then $$|\{ S \subseteq [n] : f(S) = \text{true} \}| = |\{ S \subseteq [n] : g(S) = \text{true} \}|.$$
Proof of Lemma 1: For a simple game $v$, let $w_k(v) = |\{S : |S| = k \wedge v(S) = \text{true}\}|$. For player $i$, let $W_{k, i}(v)$ be winning coalitions of size $k$ containing $i$, and $W_{k, \setminus i}(v)$ those not containing $i$. Then $w_k(v) = |W_{k, i}(v)| + |W_{k, \setminus i}(v)|$. By monotonicity in is_simple_game, $S \subseteq [n] \setminus \{i\}$ of size $k$ satisfies $v(S \cup \{i\}) = \text{true}$ iff $v(S) = \text{true}$ or $S$ is a swing for $i$. Thus: $$|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.$$ Summing over all $n$ players $i$, double-counting gives $\sum_i |W_{k+1, i}(v)| = (k+1) w_{k+1}(v)$ and $\sum_i |W_{k, i}(v)| = k w_k(v)$. Hence: $$(k+1) w_{k+1}(v) - (n - k) w_k(v) = \sum_{i=0}^{n-1} \text{swing\_table } v\ i\ k.$$ Rearranging: $$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).$$ Since $v(\emptyset) = \text{false}$, $w_0(v) = 0$. By induction, each $w_k(v)$ is determined by the swing table. Because $f$ and $g$ share swing tables, $w_k(f) = w_k(g)$ for all $k$, so $\sum_k w_k(f) = \sum_k w_k(g)$.
Lemma 2 (simple_game_card_winning_mem_eq_of_swing_table_eq). Let $f, g : \mathcal{P}([n]) \to \{0, 1\}$ be simple games satisfying is_simple_game f and is_simple_game g. If swing_table $f\ i\ k =$ swing_table $g\ i\ k$ for all $i \in [n]$ and $k \in \mathbb{N}$, then for every player $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} \}|.$$
Proof of Lemma 2: Fix player $i$. The relation from Lemma 1 gives: $$|W_{k+1, i}(v)| = \text{swing\_table } v\ i\ k + w_k(v) - |W_{k, i}(v)|.$$ Since $|W_{0, i}(v)| = 0$ and each $w_k(v)$ is determined by the swing table via Lemma 1, this recurrence uniquely determines $|W_{k, i}(v)|$ for all $k \ge 0$ by induction. Identical swing tables imply $|W_{k, i}(f)| = |W_{k, i}(g)|$ for every $k$. Summing over $k \in \{1, \dots, n\}$ yields equal counts of winning coalitions containing $i$.
Lemma 3 (weighted_game_eq_of_chow_parameters_eq). Let $f, g : \mathcal{P}([n]) \to \{0, 1\}$ be Boolean functions. Assume is_weighted_game f, with: 1. $|\{ S : f(S) = \text{true} \}| = |\{ S : g(S) = \text{true} \}|$; 2. for all $i \in [n]$, $|\{ S : i \in S \wedge f(S) = \text{true} \}| = |\{ S : i \in S \wedge g(S) = \text{true} \}|$. Then $f = g$.
Proof of Lemma 3: Let $f$ have non-negative weights $w(i) \ge 0$ and quota $q \in \mathbb{R}$, so $f(S) = \text{true} \iff \sum_{i \in S} w(i) \ge q$. Define $L(S) = \sum_{i \in S} w(i) - q$. For every $S \subseteq [n]$, the product $(f(S) - g(S)) L(S) \ge 0$, because $f(S) - g(S)$ and $L(S)$ share the same sign whenever $f(S) \ne g(S)$. Summing across all $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)).$$ Both sums on the right vanish by hypotheses (1) and (2), yielding $\sum_S (f(S) - g(S)) L(S) = 0$. Since each summand is non-negative, every summand must vanish, which forces $f(S) = g(S)$ for all $S$, settled in Lean as weighted_game_eq_of_chow_parameters_eq.
Combining the Arguments: Theorem weighted_game_eq_of_swing_table_eq combines these results directly. Hypotheses (hf : is_simple_game f), (hg : is_simple_game g), and (h : ∀ i k, swing_table f i k = swing_table g i k) supply the inputs to Lemma 1 (simple_game_card_winning_eq_of_swing_table_eq) and Lemma 2 (simple_game_card_winning_mem_eq_of_swing_table_eq). Together with (hfw : is_weighted_game f), these provide the exact preconditions for Lemma 3 (weighted_game_eq_of_chow_parameters_eq), settling $f = g$.
Verification on an Instance: Consider $n = 3$ players with the majority game $f$, weighted by $w = (1, 1, 1)$ with quota $q = 2$. Winning coalitions are $\{ \{0, 1\}, \{0, 2\}, \{1, 2\}, \{0, 1, 2\} \}$, giving $w_0 = 0, w_1 = 0, w_2 = 3, w_3 = 1$ (total 4). Winning coalitions containing player $0$ are $\{0, 1\}, \{0, 2\}, \{0, 1, 2\}$ (total 3). The swing table entries for player $0$ are: - $k = 0$: $S = \emptyset$; $f(\emptyset) = \text{false}, f(\{0\}) = \text{false}$, so $T(0, 0) = 0$. - $k = 1$: $S \in \{\{1\}, \{2\}\}$; each is losing and adding $0$ wins, so $T(0, 1) = 2$. - $k = 2$: $S = \{1, 2\}$ is winning, so $T(0, 2) = 0$. By symmetry, $T(i, 0) = 0, T(i, 1) = 2, T(i, 2) = 0$ for all $i$. Applying Lemma 1 with $w_0 = 0$: - $w_1 = (3 \cdot 0 + 0) / 1 = 0$; - $w_2 = (2 \cdot 0 + 6) / 2 = 3$; - $w_3 = (1 \cdot 3 + 0) / 3 = 1$. The total count is $0 + 0 + 3 + 1 = 4$. Applying Lemma 2 for player $0$ with $|W_{0, 0}| = 0$: - $|W_{1, 0}| = 0 + 0 - 0 = 0$; - $|W_{2, 0}| = 2 + 0 - 0 = 2$; - $|W_{3, 0}| = 0 + 3 - 2 = 1$. The total containing player $0$ is $0 + 2 + 1 = 3$. Any simple game $g$ with this swing table produces identical counts, forcing $g = f$.
5. Discussion
The theorem weighted_game_eq_of_swing_table_eq provides an affirmative answer to Conjecture 10.2 in arXiv:2607.07013 (the swing-rigidity conjecture), settling the open problem highlighted in Section 11 of that paper. The result establishes that weighted voting games are completely rigid under the swing table map: no weighted simple game can share its swing table with any other simple game, weighted or otherwise.
It should be emphasized what this result does not cover. The rigidity phenomenon established here is specific to the class of weighted games. As established in arXiv:2607.07013, general simple games are not swing-rigid: there exist pairs of distinct non-weighted simple games that share the exact same swing table. Because any semivalue evaluates player power via a linear combination of swing table entries across sizes, such non-weighted pairs are entirely indistinguishable by every semivalue. The theorem weighted_game_eq_of_swing_table_eq demonstrates that this ambiguity is strictly confined to non-weighted games: a weighted game can never be confused with a non-weighted game, nor can two distinct weighted games have identical swing tables.
Furthermore, the recurrence relations established in simple_game_card_winning_eq_of_swing_table_eq and simple_game_card_winning_mem_eq_of_swing_table_eq depend crucially on the properties of is_simple_game, specifically the monotonicity condition ($S \subseteq T \implies v(S) = \text{true} \implies v(T) = \text{true}$) and the boundary condition $v(\emptyset) = \text{false}$. Without monotonicity, the identity expressing winning augmentations in terms of winning base coalitions and swings fails, as a player's entry could turn a winning coalition into a losing one.
The resolution of Conjecture 10.2 directs attention to the broader questions posed in Section 11 of arXiv:2607.07013 regarding the structure of the swing table map. When two non-weighted simple games share a swing table, what additional non-anonymous marginal information is required to distinguish them? Beyond weighted games, are there other natural subfamilies of simple games that exhibit swing rigidity? The computational census at $n = 5$ and searches at $n = 6, 7$ documented in arXiv:2607.07013 mapped out the initial instances of games sharing swing tables; characterizing the complete fibers of the swing table map on the space of simple games remains an active direction of inquiry.
Why it is research-level
- settles OP-49 (Swing rigidity of weighted voting games)
Lean declarations
- 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.
References
- arXiv:2607.07013 — What Semivalues Cannot See: The Information Content of Anonymous Marginal Values
Drafted by gemini-3.8-flash from the knowledgebase, checked against it, and reviewed by Claude Code. Only the Lean is verified; the prose is a reading of it.