local_no_swap_of_in_core
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.
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.
uses
mem_image,mem_filter,Equiv.symm_apply_apply,Equiv.apply_symm_apply,mem_univdsimp [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⟩
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.
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_ltext 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
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.
uses
local_no_swap_of_in_core_mem_order_prefix_iff,Equiv.symm_apply_apply,not_lt_of_gerw [local_no_swap_of_in_core_mem_order_prefix_iff, Equiv.symm_apply_apply] exact not_lt_of_ge hkm
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.
uses
Equiv.symm_apply_applydsimp [predecessors, order_prefix] rw [Equiv.symm_apply_apply] rfl
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.
uses
order_prefix_zerointro k induction' k with k ih · intro _ rw [order_prefix_zero] simp
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.
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
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.
uses
local_no_swap_of_in_core_not_mem_order_prefix_of_ge,Finset.sum_insertintro 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
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).
uses
local_no_swap_of_in_core_sum_marginal_vector_order_prefix,sub_zerohave 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
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).
uses
local_no_swap_of_in_core_predecessors_apply,local_no_swap_of_in_core_order_prefix_succ,congrArghave 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
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.
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₂).
- Presburger arithmetic reasoning on finite indices (such as k + 1 < Fintype.card α and k ≤ k + 1) is closed silently by the `omega` tactic on lines 74, 75, 77, and 91.
- The ordering of players is formalized as an equivalence e : Fin (Fintype.card α) ≃ α, which introduces technical coercion steps between Fin and ℕ with no counterpart in standard mathematical notation.
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
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.
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