AFTD Auto-Formalizing Theoretical Domains

simple_game_card_size_eq_of_swing_table_eq

theoremverified

If two simple games have the same swing table, then for every k they have the same number of winning coalitions of size k.

Statement

theorem simple_game_card_size_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) (k : ℕ) :
    (Finset.univ.filter fun S : Finset (Fin n) => S.card = k ∧ f S = true).card
      = (Finset.univ.filter fun S : Finset (Fin n) => S.card = k ∧ 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 3
  • 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.
  • sum_swing_table_eqFor a monotone game, the sum over all players of T(i, k) equals (k+1) w(k+1) - (n-k) w(k), where w(k) is the number of winning coalitions…
Used by 1

Lean source view module on GitHub

/-- Two simple games with the same swing table have the same number of winning coalitions of each size. -/theorem simple_game_card_size_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) (k : ℕ) :    (Finset.univ.filter fun S : Finset (Fin n) => S.card = k ∧ f S = true).card      = (Finset.univ.filter fun S : Finset (Fin n) => S.card = k ∧ g S = true).card := by  induction k with  | zero =>    have e : ∀ v : Finset (Fin n) → Bool, v ∅ = false →        (Finset.univ.filter fun S : Finset (Fin n) => S.card = 0 ∧ v S = true) = ∅ := by      intro v hv      ext S      simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.card_eq_zero, Finset.notMem_empty, iff_false, not_and]      rintro rfl      simp [hv]    rw [e f hf.2.1, e g hg.2.1]  | succ k ih =>    have hs : ∑ i, (swing_table f i k : ℝ) = ∑ i, (swing_table g i k : ℝ) := by simp [h]    rw [sum_swing_table_eq f hf.1 k, sum_swing_table_eq g hg.1 k, ih] at hs    have hk : (k : ℝ) + 1 ≠ 0 := by positivity    have h2 : ((k : ℝ) + 1) * ((Finset.univ.filter fun S : Finset (Fin n) => S.card = k + 1 ∧ f S = true).card : ℝ)        = ((k : ℝ) + 1) * ((Finset.univ.filter fun S : Finset (Fin n) => S.card = k + 1 ∧ g S = true).card : ℝ) := by      linarith    exact_mod_cast mul_left_cancel₀ hk h2
See it in the graphDiscuss this resultChallenge it