AFTD Auto-Formalizing Theoretical Domains

local_no_swap_of_in_core

theoremverified

For any cooperative game v on a finite type α satisfying v(∅) = 0 and any ordering bijection e : Fin (Fintype.card α) ≃ α, if the marginal worth vector marginal_vector v e belongs to the core of v (is_in_core v (marginal_vector v e)), then the local no-swap condition local_no_swap v e holds.

Statement

theorem local_no_swap_of_in_core {α : Type*} [DecidableEq α] [Fintype α]
    (v : Finset α → ℝ) (hv0 : v ∅ = 0) (e : Fin (Fintype.card α) ≃ α)
    (h_core : is_in_core v (marginal_vector v e)) :
    local_no_swap v e
Source
arXiv:2611.16207, Lemma 2
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • is_in_coreAn allocation x belongs to the core of a cooperative game v on finite player set α if the total payoff equals v(univ) and every coalition…
  • marginal_vectorFor a cooperative game v : Finset α → ℝ on a finite type α with decidable equality and an ordering bijection e : Fin (Fintype.card α) ≃ α,…
  • local_no_swapFor a cooperative game v on a finite type α and an ordering bijection e : Fin (Fintype.card α) ≃ α, local_no_swap v e states that for all…
  • order_prefixGiven a finite type α with decidable equality, an ordering bijection e : Fin (Fintype.card α) ≃ α, and a natural number k, order_prefix e…
  • predecessorsGiven a finite type α with decidable equality, an ordering bijection e : Fin (Fintype.card α) ≃ α mapping indices to players, and a player…
  • order_prefix_zeroFor any ordering bijection e of a finite type α, the prefix of length zero is empty: order_prefix e 0 = ∅.

Read back from the Lean

For any finite type α with decidable equality, any set function v : Finset α → ℝ satisfying v ∅ = 0, and any ordering of α represented as an equivalence e : Fin (Fintype.card α) ≃ α: if the marginal vector of v associated with e is in the core of v, then v and e satisfy the local no-swap condition (local_no_swap v e).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To prove that a core marginal worth vector satisfies the local no-swap condition at position k, the proof considers the coalition S obtained by adding the player e(k+1) to the prefix of length k. Because this player does not belong to the prefix, the core inequality v(S) ≤ ∑_{i ∈ S} x_i separates into the value x_{e(k+1)} plus the sum of x over the prefix. An induction lemma establishes that the sum of the marginal vector over any prefix telescopes to the coalition's value minus v(∅) = 0, while x_{e(k+1)} is by definition the marginal difference v(order_prefix e (k+2)) - v(order_prefix e (k+1)). Combining these evaluations into the core inequality yields the local no-swap condition.

  1. An element x belongs to order_prefix e k if and only if e⁻¹(x) < k.

    By definition, order_prefix e k is the image under e of all indices j < k. For the forward direction, an element in the image has a preimage a < k, and applying e⁻¹ gives e⁻¹(x) = a < k. For the reverse direction, setting a = e⁻¹(x) provides a preimage with a < k whose image under e is x.

    lines 6–16

    uses mem_image, mem_filter, Equiv.symm_apply_apply, Equiv.apply_symm_apply, mem_univ

      dsimp [order_prefix]
      rw [mem_image]
      constructor
      · rintro ⟨a, ha, rfl⟩
        rw [mem_filter] at ha
        rw [Equiv.symm_apply_apply]
        exact ha.2
      · intro h
        refine ⟨e.symm x, ?_, Equiv.apply_symm_apply e x⟩
        rw [mem_filter]
        exact ⟨mem_univ _, h⟩
  2. For k < |α|, order_prefix e (k + 1) = {e(k)} ∪ order_prefix e k.

    By set extensionality, an element x belongs to order_prefix e (k + 1) if and only if e⁻¹(x) < k + 1. This condition is equivalent to e⁻¹(x) < k (membership in order_prefix e k) or e⁻¹(x) = k (meaning x = e(k)). In the reverse direction, both cases immediately imply e⁻¹(x) < k + 1.

    lines 21–33

    uses local_no_swap_of_in_core_mem_order_prefix_iff, mem_insert, Nat.lt_succ_iff_lt_or_eq.mp, Fin.ext, Equiv.apply_symm_apply, Equiv.symm_apply_apply, Nat.lt_succ_self, Nat.lt_succ_of_lt

      ext x
      rw [local_no_swap_of_in_core_mem_order_prefix_iff, mem_insert, local_no_swap_of_in_core_mem_order_prefix_iff]
      constructor
      · intro h
        rcases Nat.lt_succ_iff_lt_or_eq.mp h with hlt | heq
        · right; exact hlt
        · left
          have : e.symm x = ⟨k, hk⟩ := Fin.ext heq
          rw [← this, Equiv.apply_symm_apply]
      · rintro (rfl | hlt)
        · rw [Equiv.symm_apply_apply]
          exact Nat.lt_succ_self k
        · exact Nat.lt_succ_of_lt hlt
  3. If k ≤ m and m < |α|, then e(m) ∉ order_prefix e k.

    By the prefix membership criterion, e(m) ∈ order_prefix e k would mean e⁻¹(e(m)) = m < k, which contradicts the hypothesis k ≤ m.

    lines 38–39

    uses local_no_swap_of_in_core_mem_order_prefix_iff, Equiv.symm_apply_apply, not_lt_of_ge

      rw [local_no_swap_of_in_core_mem_order_prefix_iff, Equiv.symm_apply_apply]
      exact not_lt_of_ge hkm
  4. For any index m, predecessors e (e m) = order_prefix e m.

    Unfolding the definitions, the predecessors of e(m) are the image under e of all indices strictly smaller than e⁻¹(e(m)). Since e⁻¹(e(m)) = m, this coincides with order_prefix e m.

    lines 44–46

    uses Equiv.symm_apply_apply

      dsimp [predecessors, order_prefix]
      rw [Equiv.symm_apply_apply]
      rfl
  5. For k = 0, the sum of the marginal worth vector over order_prefix e 0 equals v(order_prefix e 0) - v(∅).

    The prefix of length 0 is the empty set (order_prefix_zero), so the sum over it is 0, which matches v(∅) - v(∅) = 0.

    lines 52–56

    uses order_prefix_zero

      intro k
      induction' k with k ih
      · intro _
        rw [order_prefix_zero]
        simp
  6. For any k ≤ |α|, the sum of the marginal worth vector over order_prefix e k equals v(order_prefix e k) - v(∅).

    By induction on k: for k + 1 ≤ |α|, decompose order_prefix e (k + 1) into {e(k)} ∪ order_prefix e k. Since e(k) is not in the prefix of length k, the sum separates into the marginal vector value at e(k) plus the sum over order_prefix e k. By the induction hypothesis, the latter is v(order_prefix e k) - v(∅). By definition of the marginal vector, the contribution of e(k) is v(order_prefix e (k + 1)) - v(order_prefix e k), so the intermediate terms cancel algebraically.

    lines 57–66

    uses Nat.lt_of_succ_le, Nat.le_of_lt, local_no_swap_of_in_core_order_prefix_succ, sum_insert, local_no_swap_of_in_core_not_mem_order_prefix_of_ge, le_rfl, local_no_swap_of_in_core_predecessors_apply

      · intro hk
        have hk_lt : k < Fintype.card α := Nat.lt_of_succ_le hk
        have hk_le : k ≤ Fintype.card α := Nat.le_of_lt hk_lt
        rw [local_no_swap_of_in_core_order_prefix_succ e k hk_lt]
        rw [sum_insert (local_no_swap_of_in_core_not_mem_order_prefix_of_ge e hk_lt le_rfl)]
        rw [ih hk_le]
        dsimp [marginal_vector]
        rw [local_no_swap_of_in_core_predecessors_apply e ⟨k, hk_lt⟩]
        rw [← local_no_swap_of_in_core_order_prefix_succ e k hk_lt]
        ring
  7. For k + 2 ≤ |α|, letting S = {e(k+1)} ∪ order_prefix e k, the core condition implies v(S) ≤ x(e(k+1)) + ∑_{i ∈ order_prefix e k} x(i), where x is the marginal worth vector.

    Since k ≤ k + 1, e(k + 1) does not belong to order_prefix e k. The core condition applied to coalition S states that v(S) ≤ ∑_{i ∈ S} x(i). Because e(k + 1) ∉ order_prefix e k, this sum splits into the value at e(k + 1) plus the sum over order_prefix e k.

    lines 73–82

    uses local_no_swap_of_in_core_not_mem_order_prefix_of_ge, Finset.sum_insert

      intro k hk
      have hk1 : k + 1 < Fintype.card α := by omega
      have hk_le : k ≤ Fintype.card α := by omega
      have hk_not_mem : e ⟨k + 1, hk1⟩ ∉ order_prefix e k :=
        local_no_swap_of_in_core_not_mem_order_prefix_of_ge e hk1 (by omega)
      let S := insert (e ⟨k + 1, hk1⟩) (order_prefix e k)
      have hS_le : v S ≤ ∑ i ∈ S, marginal_vector v e i := h_core.2 S
      have h_sum_S : ∑ i ∈ S, marginal_vector v e i =
          marginal_vector v e (e ⟨k + 1, hk1⟩) + ∑ i ∈ order_prefix e k, marginal_vector v e i :=
        Finset.sum_insert hk_not_mem
  8. The sum of the marginal worth vector over order_prefix e k equals v(order_prefix e k).

    The prefix summation theorem gives ∑_{i ∈ order_prefix e k} x(i) = v(order_prefix e k) - v(∅). Since v(∅) = 0 by assumption, subtracting 0 simplifies this expression to v(order_prefix e k).

    lines 83–86

    uses local_no_swap_of_in_core_sum_marginal_vector_order_prefix, sub_zero

      have h_sum_k : ∑ i ∈ order_prefix e k, marginal_vector v e i = v (order_prefix e k) := by
        have := local_no_swap_of_in_core_sum_marginal_vector_order_prefix v e k hk_le
        rw [hv0, sub_zero] at this
        exact this
  9. The marginal worth vector value at e(k+1) equals v(order_prefix e (k + 2)) - v(order_prefix e (k + 1)).

    By definition, x(e(k+1)) is the marginal contribution of e(k+1) to its predecessors. The predecessors of e(k+1) are order_prefix e (k+1), and inserting e(k+1) into that prefix produces order_prefix e (k+2).

    lines 87–93

    uses local_no_swap_of_in_core_predecessors_apply, local_no_swap_of_in_core_order_prefix_succ, congrArg

      have h_mv : marginal_vector v e (e ⟨k + 1, hk1⟩) =
          v (order_prefix e (k + 2)) - v (order_prefix e (k + 1)) := by
        dsimp [marginal_vector]
        rw [local_no_swap_of_in_core_predecessors_apply e ⟨k + 1, hk1⟩]
        have hk1_lt : k + 1 < Fintype.card α := by omega
        have hsucc := local_no_swap_of_in_core_order_prefix_succ e (k + 1) hk1_lt
        exact congrArg (fun s => v s - v (order_prefix e (k + 1))) hsucc.symm
  10. The local no-swap inequality v(S) - v(order_prefix e k) ≤ v(order_prefix e (k + 2)) - v(order_prefix e (k + 1)) holds. automation

    Linear arithmetic over the real numbers (`linarith`) combines the coalition core inequality with the evaluations of the prefix sum and the marginal worth of e(k+1) to close the inequality.

    line 94

      linarith
mem_image
An element b belongs to the image f(s) of a finite set s if and only if b = f(a) for some a ∈ s.
mem_filter
An element a belongs to {x ∈ s | p(x)} if and only if a ∈ s and p(a) holds.
Equiv.symm_apply_apply
Applying an equivalence e and then its inverse e.symm returns the original element: e.symm (e x) = x.
Equiv.apply_symm_apply
Applying the inverse equivalence e.symm and then e returns the original element: e (e.symm x) = x.
mem_univ
Every element of a finite type belongs to the universal finset `Finset.univ`.
local_no_swap_of_in_core_mem_order_prefix_iff
An element x belongs to order_prefix e k if and only if its index under e.symm is strictly less than k.
mem_insert
An element belongs to insert b s if and only if it equals b or belongs to s.
Nat.lt_succ_iff_lt_or_eq.mp
For natural numbers, a < b + 1 implies a < b or a = b.
Fin.ext
Two elements of Fin n are equal if their underlying natural values are equal.
Nat.lt_succ_self
For any natural number n, n < n + 1.
Nat.lt_succ_of_lt
If a < b, then a < b + 1.
not_lt_of_ge
If a ≤ b, then it is not the case that b < a.
order_prefix_zero
The prefix of length 0 under any ordering is the empty set.
Nat.lt_of_succ_le
If n + 1 ≤ m, then n < m.
Nat.le_of_lt
If n < m, then n ≤ m.
local_no_swap_of_in_core_order_prefix_succ
For k < Fintype.card α, the prefix of length k + 1 equals {e(k)} ∪ order_prefix e k.
sum_insert
If a ∉ s, then the sum of f over insert a s equals f(a) plus the sum of f over s.
local_no_swap_of_in_core_not_mem_order_prefix_of_ge
If k ≤ m and m < Fintype.card α, then e(m) does not belong to order_prefix e k.
le_rfl
For any preorder, a ≤ a holds by reflexivity.
local_no_swap_of_in_core_predecessors_apply
The set of predecessors of e(m) under ordering e equals order_prefix e m.
Finset.sum_insert
If a ∉ s, then the sum of f over insert a s equals f(a) plus the sum of f over s (qualified with Finset).
local_no_swap_of_in_core_sum_marginal_vector_order_prefix
For any k ≤ Fintype.card α, the sum of the marginal worth vector over order_prefix e k equals v(order_prefix e k) - v(∅).
sub_zero
Subtracting zero leaves a group element unchanged: a - 0 = a.
congrArg
If a₁ = a₂, then f(a₁) = f(a₂).

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

open Finsetprivate theorem local_no_swap_of_in_core_mem_order_prefix_iff {α : Type*} [DecidableEq α] [Fintype α]    (e : Fin (Fintype.card α) ≃ α) (k : ℕ) (x : α) :    x ∈ order_prefix e k ↔ (e.symm x : ℕ) < k := by  dsimp [order_prefix]  rw [mem_image]  constructor  · rintro ⟨a, ha, rfl⟩    rw [mem_filter] at ha    rw [Equiv.symm_apply_apply]    exact ha.2  · intro h    refine ⟨e.symm x, ?_, Equiv.apply_symm_apply e x⟩    rw [mem_filter]    exact ⟨mem_univ _, h⟩private theorem local_no_swap_of_in_core_order_prefix_succ {α : Type*} [DecidableEq α] [Fintype α]    (e : Fin (Fintype.card α) ≃ α) (k : ℕ) (hk : k < Fintype.card α) :    order_prefix e (k + 1) = insert (e ⟨k, hk⟩) (order_prefix e k) := by  ext x  rw [local_no_swap_of_in_core_mem_order_prefix_iff, mem_insert, local_no_swap_of_in_core_mem_order_prefix_iff]  constructor  · intro h    rcases Nat.lt_succ_iff_lt_or_eq.mp h with hlt | heq    · right; exact hlt    · left      have : e.symm x = ⟨k, hk⟩ := Fin.ext heq      rw [← this, Equiv.apply_symm_apply]  · rintro (rfl | hlt)    · rw [Equiv.symm_apply_apply]      exact Nat.lt_succ_self k    · exact Nat.lt_succ_of_lt hltprivate theorem local_no_swap_of_in_core_not_mem_order_prefix_of_ge {α : Type*} [DecidableEq α] [Fintype α]    (e : Fin (Fintype.card α) ≃ α) {k m : ℕ} (hm : m < Fintype.card α) (hkm : k ≤ m) :    e ⟨m, hm⟩ ∉ order_prefix e k := by  rw [local_no_swap_of_in_core_mem_order_prefix_iff, Equiv.symm_apply_apply]  exact not_lt_of_ge hkmprivate theorem local_no_swap_of_in_core_predecessors_apply {α : Type*} [DecidableEq α] [Fintype α]    (e : Fin (Fintype.card α) ≃ α) (m : Fin (Fintype.card α)) :    predecessors e (e m) = order_prefix e m.val := by  dsimp [predecessors, order_prefix]  rw [Equiv.symm_apply_apply]  rflprivate theorem local_no_swap_of_in_core_sum_marginal_vector_order_prefix {α : Type*} [DecidableEq α] [Fintype α]    (v : Finset α → ℝ) (e : Fin (Fintype.card α) ≃ α) :    ∀ (k : ℕ), k ≤ Fintype.card α →      ∑ i ∈ order_prefix e k, marginal_vector v e i = v (order_prefix e k) - v ∅ := by  intro k  induction' k with k ih  · intro _    rw [order_prefix_zero]    simp  · intro hk    have hk_lt : k < Fintype.card α := Nat.lt_of_succ_le hk    have hk_le : k ≤ Fintype.card α := Nat.le_of_lt hk_lt    rw [local_no_swap_of_in_core_order_prefix_succ e k hk_lt]    rw [sum_insert (local_no_swap_of_in_core_not_mem_order_prefix_of_ge e hk_lt le_rfl)]    rw [ih hk_le]    dsimp [marginal_vector]    rw [local_no_swap_of_in_core_predecessors_apply e ⟨k, hk_lt⟩]    rw [← local_no_swap_of_in_core_order_prefix_succ e k hk_lt]    ring/-- If the marginal worth vector of an ordering is in the core, the local no-swap condition holds. -/theorem local_no_swap_of_in_core {α : Type*} [DecidableEq α] [Fintype α]    (v : Finset α → ℝ) (hv0 : v ∅ = 0) (e : Fin (Fintype.card α) ≃ α)    (h_core : is_in_core v (marginal_vector v e)) :    local_no_swap v e := by  intro k hk  have hk1 : k + 1 < Fintype.card α := by omega  have hk_le : k ≤ Fintype.card α := by omega  have hk_not_mem : e ⟨k + 1, hk1⟩ ∉ order_prefix e k :=    local_no_swap_of_in_core_not_mem_order_prefix_of_ge e hk1 (by omega)  let S := insert (e ⟨k + 1, hk1⟩) (order_prefix e k)  have hS_le : v S ≤ ∑ i ∈ S, marginal_vector v e i := h_core.2 S  have h_sum_S : ∑ i ∈ S, marginal_vector v e i =      marginal_vector v e (e ⟨k + 1, hk1⟩) + ∑ i ∈ order_prefix e k, marginal_vector v e i :=    Finset.sum_insert hk_not_mem  have h_sum_k : ∑ i ∈ order_prefix e k, marginal_vector v e i = v (order_prefix e k) := by    have := local_no_swap_of_in_core_sum_marginal_vector_order_prefix v e k hk_le    rw [hv0, sub_zero] at this    exact this  have h_mv : marginal_vector v e (e ⟨k + 1, hk1⟩) =      v (order_prefix e (k + 2)) - v (order_prefix e (k + 1)) := by    dsimp [marginal_vector]    rw [local_no_swap_of_in_core_predecessors_apply e ⟨k + 1, hk1⟩]    have hk1_lt : k + 1 < Fintype.card α := by omega    have hsucc := local_no_swap_of_in_core_order_prefix_succ e (k + 1) hk1_lt    exact congrArg (fun s => v s - v (order_prefix e (k + 1))) hsucc.symm  linarith
See it in the graphDiscuss this resultChallenge it