exists_simple_games_ne_of_swing_table_eq
theoremverifiedformalization
Example 10.1 of arXiv:2607.07013: the five-player simple games with minimal winning coalitions {1,2,3}, {0,2,4}, {0,3,4}, {1,3,4} and {0,1,2}, {0,3,4}, {1,3,4}, {2,3,4} are different simple games with the same swing table.
Statement
theorem exists_simple_games_ne_of_swing_table_eq :
∃ f g : Finset (Fin 5) → Bool, is_simple_game f ∧ is_simple_game g ∧
(∀ i k, swing_table f i k = swing_table g i k) ∧ f ≠ g- Formalizes
- arXiv:2607.07013, Example 10.1 (the displayed collision pair); checked by the Lean kernel by the operator (Claude), 2026-10-02
- Verified
- 02 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- swing_table_eq_zero_of_ltIn a game on n players, T(i, k) = 0 whenever k > n.
- 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…
- 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.
- Used by 1
- exists_not_weighted_simple_games_ne_of_swing_table_eqThe weighted hypothesis in swing rigidity cannot be dropped: there are two different five-player simple games, neither of them weighted,…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- Example 10.1 of arXiv:2607.07013: the simple games on five players with minimal winning coalitions {123, 024, 034, 134} and {012, 034, 134, 234} are different but have the same swing table. -/theorem exists_simple_games_ne_of_swing_table_eq : ∃ f g : Finset (Fin 5) → Bool, is_simple_game f ∧ is_simple_game g ∧ (∀ i k, swing_table f i k = swing_table g i k) ∧ f ≠ g := by refine ⟨fun S => decide ({1, 2, 3} ⊆ S ∨ {0, 2, 4} ⊆ S ∨ {0, 3, 4} ⊆ S ∨ {1, 3, 4} ⊆ S), fun S => decide ({0, 1, 2} ⊆ S ∨ {0, 3, 4} ⊆ S ∨ {1, 3, 4} ⊆ S ∨ {2, 3, 4} ⊆ S), ⟨?_, by decide, by decide⟩, ⟨?_, by decide, by decide⟩, ?_, ?_⟩ · intro S T hST hS simp only [decide_eq_true_eq] at hS ⊢ rcases hS with h | h | h | h exacts [Or.inl (h.trans hST), Or.inr (Or.inl (h.trans hST)), Or.inr (Or.inr (Or.inl (h.trans hST))), Or.inr (Or.inr (Or.inr (h.trans hST)))] · intro S T hST hS simp only [decide_eq_true_eq] at hS ⊢ rcases hS with h | h | h | h exacts [Or.inl (h.trans hST), Or.inr (Or.inl (h.trans hST)), Or.inr (Or.inr (Or.inl (h.trans hST))), Or.inr (Or.inr (Or.inr (h.trans hST)))] · intro i k rcases Nat.lt_or_ge 5 k with hk | hk · rw [swing_table_eq_zero_of_lt _ i k hk, swing_table_eq_zero_of_lt _ i k hk] · interval_cases k <;> revert i <;> decide +kernel · intro h have := congrFun h {1, 2, 3} revert this decide