bundle_of_permute_agents
Reassigning every good by the inverse of an agent permutation makes the bundle of agent i equal to the old bundle of the permuted agent.
Statement
theorem bundle_of_permute_agents {m n : ℕ} (σ : Fin m → Fin n) (p : Equiv.Perm (Fin n)) (i : Fin n) : bundle_of (fun g => p.symm (σ g)) i = bundle_of σ (p i)
- Source
- Helper for efx_four_agents_additive_exists (OP-7), campaign session IN-404, 2026-11-01.
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
- Used by 3
- efx_exists_of_two_universal_small_goods_irLet m and n be natural numbers with n positive. There are m+2 goods with nonnegative real additive values for n agents. Each agent values…
- is_efx_goods_exists_unenviedFor a positive number of agents, any EFX allocation of nonnegative additive goods can be changed to another EFX allocation that weakly…
- is_efx_goods_permute_of_utility_leA bundle permutation that weakly improves every agent's own additive value preserves EFX for nonnegative item values.
The proof, explained
By extensionality, the two bundles are equal if and only if they contain the same goods. A good $g$ is assigned to agent $i$ under the reassignment precisely when $p^{-1}(\sigma(g)) = i$. Since $p$ is a permutation, this equality is equivalent to $\sigma(g) = p(i)$, meaning $g$ belongs to the original bundle of agent $p(i)$.
It suffices to show that any good $g$ belongs to the bundle of agent $i$ under the reassignment if and only if it belongs to the bundle of agent $p(i)$ under $\sigma$.
By set extensionality (`ext g`), two finite sets are equal if and only if they contain exactly the same elements.
ext gA good $g$ belongs to the reassigned bundle of agent $i$ if and only if it belongs to the bundle of agent $p(i)$ under $\sigma$. automation
By definition of `bundle_of`, $g$ belongs to the bundle of $i$ under the reassigned allocation if and only if $p^{-1}(\sigma(g)) = i$. By `Equiv.symm_apply_eq`, applying the permutation $p$ to both sides transforms this condition into $\sigma(g) = p(i)$, which is precisely the definition of $g$ belonging to the bundle of $p(i)$ under $\sigma$. The simplifier rewrites these definitions and equivalence to close the goal.
uses
Equiv.symm_apply_eqsimp [bundle_of, Equiv.symm_apply_eq]
Equiv.symm_apply_eq- For an equivalence or permutation $e$, $e^{-1}(x) = y$ if and only if $x = e(y)$.
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 Function Finsettheorem bundle_of_permute_agents {m n : ℕ} (σ : Fin m → Fin n) (p : Equiv.Perm (Fin n)) (i : Fin n) : bundle_of (fun g => p.symm (σ g)) i = bundle_of σ (p i) := by ext g simp [bundle_of, Equiv.symm_apply_eq]