AFTD Auto-Formalizing Theoretical Domains

is_efx_goods_exists_unenvied

theoremverified

For a positive number of agents, any EFX allocation of nonnegative additive goods can be changed to another EFX allocation that weakly improves every own utility and has an unenvied agent.

Statement

theorem is_efx_goods_exists_unenvied {m n : ℕ} (hn : 0 < n) (u : Fin n → Fin m → ℝ)
    (hu : ∀ i g, 0 ≤ u i g) (σ : Fin m → Fin n) (hσ : is_efx_goods u σ) :
    ∃ τ : Fin m → Fin n, is_efx_goods u τ ∧
      (∀ i, additive_valuation (u i) (bundle_of σ i) ≤
        additive_valuation (u i) (bundle_of τ i)) ∧
      ∃ s : Fin n, ∀ i, additive_valuation (u i) (bundle_of τ s) ≤
        additive_valuation (u i) (bundle_of τ i)
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 6
  • finite_unenvied_permutationEvery finite nonempty matrix of real bundle values admits a permutation that weakly improves each diagonal value and has an unenvied…
  • 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_permute_of_utility_leA bundle permutation that weakly improves every agent's own additive value preserves EFX for nonnegative item values.
  • 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
  • efx_exists_of_universal_least_goodFor a positive number of agents and nonnegative additive values, if the last good is weakly least valuable for every agent, existence of…

The proof, explained

The proof uses envy-cycle elimination on the agents' bundles. Given an initial EFX allocation σ, we consider the matrix of utilities each agent assigns to every other agent's bundle and invoke finite_unenvied_permutation to find a permutation p and an agent s such that trading bundles along p weakly improves every agent's utility, while bundle p(s) is weakly dispreferred by everyone to their own new bundle. Defining the new allocation by assigning good g to p⁻¹(σ(g)) preserves the EFX property by is_efx_goods_permute_of_utility_le, and leaves agent s unenvied.

  1. The agent population Fin n is nonempty.

    Using classical reasoning and the assumption that n > 0, we deduce n ≠ 0 via Nat.ne_of_gt, establishing that Fin n is a nonempty type.

    lines 10–11

    uses Nat.ne_of_gt

      classical
      letI : NeZero n := ⟨Nat.ne_of_gt hn⟩
  2. There exist an agent permutation p and a candidate agent s such that reassigning bundle p(i) to agent i weakly improves every agent's utility, and no agent prefers bundle p(s) to their own bundle p(i).

    Consider the matrix w(i, j) = additive_valuation (u i) (bundle_of σ j) representing agent i's valuation of agent j's bundle under σ. Applying finite_unenvied_permutation to w yields a permutation p of agents and an agent s such that for all i, w(i, i) ≤ w(i, p(i)) (each agent weakly prefers bundle p(i) to their own) and w(i, p(s)) ≤ w(i, p(i)) (each agent weakly prefers bundle p(i) to bundle p(s)).

    lines 12–13

    uses finite_unenvied_permutation

      obtain ⟨p, hp, s, hs⟩ := finite_unenvied_permutation
        (fun i j => additive_valuation (u i) (bundle_of σ j))
  3. The reallocated assignment τ(g) = p⁻¹(σ(g)) is EFX, and agent s will serve as the unenvied agent.

    We choose τ to be the allocation where good g is assigned to p⁻¹(σ(g)), which gives agent i the bundle originally held by p(i). By is_efx_goods_permute_of_utility_le, because σ is EFX, goods have non-negative utilities, and p weakly improves every agent's valuation of their own bundle, τ is also EFX. We also provide s as the unenvied agent, leaving two goals: that utilities weakly increase and that s is unenvied under τ.

    line 14

    uses is_efx_goods_permute_of_utility_le

      refine ⟨fun g => p.symm (σ g), is_efx_goods_permute_of_utility_le u hu σ hσ p hp, ?_, s, ?_⟩
  4. Every agent weakly prefers their bundle under τ to their initial bundle under σ.

    By bundle_of_permute_agents, agent i's bundle under τ = p⁻¹ ∘ σ is precisely bundle_of σ (p i). Rewriting with this lemma transforms the goal into the hypothesis hp from the permutation construction, which states that each agent weakly prefers bundle p(i) to bundle i.

    line 15

    uses bundle_of_permute_agents

      · simpa only [bundle_of_permute_agents] using hp
  5. Agent s is unenvied under τ: every agent weakly prefers their own bundle to the bundle of s.

    Using bundle_of_permute_agents, the bundles of s and i under τ simplify to bundle_of σ (p s) and bundle_of σ (p i). The condition then reduces exactly to hypothesis hs from the permutation construction, which guarantees that no agent values bundle p(s) more than bundle p(i).

    line 16

    uses bundle_of_permute_agents

      · simpa only [bundle_of_permute_agents] using hs
Nat.ne_of_gt
If a natural number is strictly greater than another, they are not equal; in particular, a positive natural number is nonzero.
finite_unenvied_permutation
For any finite nonempty set of agents and any utility matrix w, there exists a permutation p such that every agent weakly prefers their assigned element p(i) to i, and some agent s is unenvied (every agent weakly prefers p(i) to p(s)).
is_efx_goods_permute_of_utility_le
For non-negative additive valuations, permuting the bundles of an EFX allocation according to a permutation that weakly increases each agent's utility yields another EFX allocation.
bundle_of_permute_agents
Under the permuted allocation g ↦ p⁻¹(σ(g)), the bundle assigned to agent i is the bundle that originally belonged to agent p(i).

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_exists_unenvied {m n : ℕ} (hn : 0 < n) (u : Fin n → Fin m → ℝ)    (hu : ∀ i g, 0 ≤ u i g) (σ : Fin m → Fin n) (hσ : is_efx_goods u σ) :    ∃ τ : Fin m → Fin n, is_efx_goods u τ ∧      (∀ i, additive_valuation (u i) (bundle_of σ i) ≤        additive_valuation (u i) (bundle_of τ i)) ∧      ∃ s : Fin n, ∀ i, additive_valuation (u i) (bundle_of τ s) ≤        additive_valuation (u i) (bundle_of τ i) := by  classical  letI : NeZero n := ⟨Nat.ne_of_gt hn⟩  obtain ⟨p, hp, s, hs⟩ := finite_unenvied_permutation    (fun i j => additive_valuation (u i) (bundle_of σ j))  refine ⟨fun g => p.symm (σ g), is_efx_goods_permute_of_utility_le u hu σ hσ p hp, ?_, s, ?_⟩  · simpa only [bundle_of_permute_agents] using hp  · simpa only [bundle_of_permute_agents] using hs
See it in the graphDiscuss this resultChallenge it