is_efx_goods_permute_of_utility_le
A bundle permutation that weakly improves every agent's own additive value preserves EFX for nonnegative item values.
Statement
theorem is_efx_goods_permute_of_utility_le {m n : ℕ} (u : Fin n → Fin m → ℝ) (hu : ∀ i g, 0 ≤ u i g) (σ : Fin m → Fin n) (hσ : is_efx_goods u σ) (p : Equiv.Perm (Fin n)) (hp : ∀ i, additive_valuation (u i) (bundle_of σ i) ≤ additive_valuation (u i) (bundle_of σ (p i))) : is_efx_goods u (fun g => p.symm (σ g))
- Source
- Helper for efx_four_agents_additive_exists (OP-7), campaign session IN-404, 2026-11-01. Standard cycle elimination and ordered insertion, arXiv:1707.04769v3 Lemma 6.1 and Appendix B; no novelty claim.
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- bundle_of_permute_agentsReassigning every good by the inverse of an agent permutation makes the bundle of agent i equal to the old bundle of the permuted agent.
- is_efx_goods_all_pairsFor nonnegative additive values, the EFX inequalities also hold when the observer and the target agent coincide.
- is_efx_goodsAn allocation is EFX if for every pair of distinct agents i and j, and every good g in j's bundle, agent i values her own bundle at least…
- 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.
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- Used by 1
- 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…
The proof, explained
To show that the permuted allocation is EFX, we consider any two distinct agents $i$ and $j$ and an item $g$ in $j$'s new bundle, which under the permutation corresponds to $p(j)$'s original bundle. Because the original allocation was EFX and valuations are non-negative, agent $i$ values $p(j)$'s bundle without $g$ at most as much as their own original bundle. Since every agent weakly prefers their new bundle to their original bundle by assumption, the EFX inequality for the permuted allocation follows by transitivity.
For any distinct agents $i \neq j$ and any item $g$ in agent $j$'s permuted bundle, the EFX condition reduces to showing that $u_i(\text{bundle\_of}(\sigma, p(j)) \setminus \{g\}) \le u_i(\text{bundle\_of}(\sigma, p(i)))$.
To show that the new allocation $p^{-1} \circ \sigma$ is EFX, we fix distinct agents $i$ and $j$ and an item $g$ allocated to $j$. Applying `bundle_of_permute_agents` rewrites the bundle of each agent $k$ under $p^{-1} \circ \sigma$ as the bundle $\text{bundle\_of}(\sigma, p(k))$ assigned to $p(k)$ under $\sigma$. This rewrites both the assumption that $g$ belongs to $j$'s new bundle and the goal into the corresponding bundles under the original allocation $\sigma$.
uses
bundle_of_permute_agentsintro i j hij g hg simp only [bundle_of_permute_agents] at hg ⊢
The valuation inequality holds, completing the proof that the permuted allocation is EFX.
Because the original allocation $\sigma$ is EFX and item valuations are non-negative, `is_efx_goods_all_pairs` guarantees that agent $i$ values $p(j)$'s original bundle without item $g$ at most as much as agent $i$'s own original bundle $\text{bundle\_of}(\sigma, i)$. By the improvement hypothesis `hp`, agent $i$ values their newly assigned bundle $\text{bundle\_of}(\sigma, p(i))$ at least as much as their original bundle $\text{bundle\_of}(\sigma, i)$. The result follows by transitivity of $\le$.
uses
is_efx_goods_all_pairsexact (is_efx_goods_all_pairs u hu σ hσ i (p j) g hg).trans (hp i)
bundle_of_permute_agents- Under the permuted allocation $p^{-1} \circ \sigma$, the bundle received by agent $i$ is identical to the bundle originally allocated to agent $p(i)$ under $\sigma$.
is_efx_goods_all_pairs- For non-negative additive valuations, an EFX allocation satisfies the EFX inequality for all pairs of agents (even when both agents are identical): removing any item from agent $j$'s bundle leaves a bundle whose value to agent $i$ is at most agent $i$'s value for their own bundle.
- The lemma `is_efx_goods_all_pairs` is required because even though $i \neq j$, the permutation might map $j$ to $i$ (that is, $p(j) = i$). Non-negativity of item values ensures that the EFX inequality $u_i(A \setminus \{g\}) \le u_i(A)$ holds even when comparing an agent's valuation of their own bundle to itself.
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 is_efx_goods_permute_of_utility_le {m n : ℕ} (u : Fin n → Fin m → ℝ) (hu : ∀ i g, 0 ≤ u i g) (σ : Fin m → Fin n) (hσ : is_efx_goods u σ) (p : Equiv.Perm (Fin n)) (hp : ∀ i, additive_valuation (u i) (bundle_of σ i) ≤ additive_valuation (u i) (bundle_of σ (p i))) : is_efx_goods u (fun g => p.symm (σ g)) := by intro i j hij g hg simp only [bundle_of_permute_agents] at hg ⊢ exact (is_efx_goods_all_pairs u hu σ hσ i (p j) g hg).trans (hp i)