AFTD Auto-Formalizing Theoretical Domains

simple_game_card_winning_mem_eq_of_swing_table_eq

theoremverified

If two simple games have the same swing table, then for every player i they have the same number of winning coalitions containing i.

Statement

theorem simple_game_card_winning_mem_eq_of_swing_table_eq {n : ℕ} (f g : Finset (Fin n) → Bool)
    (hf : is_simple_game f) (hg : is_simple_game g)
    (h : ∀ i k, swing_table f i k = swing_table g i k) (i : Fin n) :
    (Finset.univ.filter fun S : Finset (Fin n) => i ∈ S ∧ f S = true).card
      = (Finset.univ.filter fun S : Finset (Fin n) => i ∈ S ∧ g S = true).card
Source
step towards weighted_game_eq_of_swing_table_eq (swing rigidity, What Semivalues Cannot See: The Information Content of Anonymous Marginal Values, arXiv:2607.07013, Conj. 10.2)
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • 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.
  • 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.
  • sum_range_swing_table_eqFor a monotone game, player i's total swing count (the sum of T(i, k) over k) equals 2 A_i - |W|, where A_i is the number of winning…
Used by 1
  • 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…

Lean source view module on GitHub

/-- Two simple games with the same swing table have, for every player `i`, the same number of winning coalitions containing `i`. -/theorem simple_game_card_winning_mem_eq_of_swing_table_eq {n : ℕ} (f g : Finset (Fin n) → Bool)    (hf : is_simple_game f) (hg : is_simple_game g)    (h : ∀ i k, swing_table f i k = swing_table g i k) (i : Fin n) :    (Finset.univ.filter fun S : Finset (Fin n) => i ∈ S ∧ f S = true).card      = (Finset.univ.filter fun S : Finset (Fin n) => i ∈ S ∧ g S = true).card := by  have hs : ∑ k ∈ Finset.range (n + 1), (swing_table f i k : ℝ)      = ∑ k ∈ Finset.range (n + 1), (swing_table g i k : ℝ) := by simp [h]  rw [sum_range_swing_table_eq f hf.1 i, sum_range_swing_table_eq g hg.1 i,    simple_game_card_winning_eq_of_swing_table_eq f g hf hg h] at hs  exact_mod_cast (by linarith : ((Finset.univ.filter fun S : Finset (Fin n) => i ∈ S ∧ f S = true).card : ℝ)      = (Finset.univ.filter fun S : Finset (Fin n) => i ∈ S ∧ g S = true).card)
See it in the graphDiscuss this resultChallenge it