AFTD Auto-Formalizing Theoretical Domains

is_efx_goods_permute_of_utility_le

theoremverified

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.

  1. 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$.

    lines 9–10

    uses bundle_of_permute_agents

      intro i j hij g hg
      simp only [bundle_of_permute_agents] at hg ⊢
  2. 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$.

    line 11

    uses is_efx_goods_all_pairs

      exact (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.

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 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)
See it in the graphDiscuss this resultChallenge it