efx_source_two_full_efx
The explicit complete EFX allocation preserves the other three initial utilities.
Statement
theorem efx_source_two_full_efx : is_efx_goods (fun i g => (efx_source_two_values i g : ℝ)) efx_source_two_witness ∧ (∀ i : Fin 3, (efx_partial_nat_utility efx_source_two_values efx_source_two_start i.castSucc : ℝ) ≤ additive_valuation (fun g => (efx_source_two_values i.castSucc g : ℝ)) (bundle_of efx_source_two_witness i.castSucc))
- Source
- Nine-good isolated-source completion obstruction derived from the three-agent partial Pareto barrier in arXiv:2002.05119, Section 5; experiments 11561–11562.
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- efx_source_two_valuesStrictly positive four-agent values for seven old goods and two unequal locks.
- efx_source_two_startThe initial old-good allocation, with both locks at agent 3 and good 6 unallocated.
- efx_source_two_witnessA complete EFX allocation witness.
- efx_partial_nat_utilityNatural utility in a partial allocation whose last owner label denotes unallocated goods.
- is_efx_goods_nat_cast_iffFor natural-number item values, EFX after casting values to the reals is equivalent to all natural-number inequalities comparing each…
- 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.
The proof, explained
The theorem establishes that a specific complete allocation of nine goods among four agents is envy-free up to any good (EFX) and preserves the utilities of the first three agents from an initial partial allocation. The proof splits the conjunction into two goals. First, the real-valued EFX property is reduced via `is_efx_goods_nat_cast_iff` to an equivalent condition over natural numbers and verified by exhaustive finite computation. Second, the utility preservation condition is proved over natural numbers by finite computation and then lifted to the reals by unfolding the definition of additive valuation.
The complete allocation `efx_source_two_witness` is envy-free up to any good (EFX).
Splitting the conjunction reduces the theorem to two independent goals. For the first goal, rewriting with `is_efx_goods_nat_cast_iff` converts the EFX condition on real valuations into an equivalent condition over natural numbers: for every pair of distinct agents i ≠ j and every item g in j's bundle, agent i's valuation of j's bundle is at most agent i's valuation of their own bundle plus their valuation of g. Since there are 4 agents and 9 goods with explicit valuations, this universal statement over finite domains is checked by exhaustive computation (`decide`).
uses
is_efx_goods_nat_cast_iffconstructor · rw [is_efx_goods_nat_cast_iff] decide
In natural numbers, each of the first three agents receives at least as much utility in the witness allocation as in the starting partial allocation.
We establish an intermediate lemma `hh` asserting that for every agent i ∈ {0, 1, 2}, their utility in the starting partial allocation (`efx_partial_nat_utility`) is bounded by the sum of their valuations of the goods in their allocated bundle (`bundle_of efx_source_two_witness i.castSucc`). Because this involves only three agents and explicitly defined numerical tables, it is verified by exhaustive computation (`decide`).
· have hh : ∀ i : Fin 3, efx_partial_nat_utility efx_source_two_values efx_source_two_start i.castSucc ≤ ∑ g ∈ bundle_of efx_source_two_witness i.castSucc, efx_source_two_values i.castSucc g := by decide
The utility preservation property holds over the real numbers.
Fixing an arbitrary agent i ∈ {0, 1, 2}, unfolding the definition of additive valuation expresses their real utility as the sum over their bundle of their real-valued valuations. Applying the natural number inequality from `hh` to agent i and casting from ℕ to ℝ using `exact_mod_cast` closes the remaining goal.
intro i simp only [additive_valuation] exact_mod_cast hh i
is_efx_goods_nat_cast_iff- An allocation of goods is EFX with respect to real valuations cast from natural numbers if and only if for every pair of distinct agents i ≠ j and each item g in j's bundle, agent i's valuation of j's bundle is at most agent i's valuation of their own bundle plus their valuation of g.
- The verification of the EFX condition and the utility lower bounds is delegated to `decide`, which checks all finite combinations of agents and goods by direct kernel computation rather than presenting explicit manual arithmetic.
- The three initial agents are indexed by `Fin 3` and embedded into the four agents of the final allocation (`Fin 4`) via the inclusion map `.castSucc`.
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.
theorem efx_source_two_full_efx : is_efx_goods (fun i g => (efx_source_two_values i g : ℝ)) efx_source_two_witness ∧ (∀ i : Fin 3, (efx_partial_nat_utility efx_source_two_values efx_source_two_start i.castSucc : ℝ) ≤ additive_valuation (fun g => (efx_source_two_values i.castSucc g : ℝ)) (bundle_of efx_source_two_witness i.castSucc)) := by constructor · rw [is_efx_goods_nat_cast_iff] decide · have hh : ∀ i : Fin 3, efx_partial_nat_utility efx_source_two_values efx_source_two_start i.castSucc ≤ ∑ g ∈ bundle_of efx_source_two_witness i.castSucc, efx_source_two_values i.castSucc g := by decide intro i simp only [additive_valuation] exact_mod_cast hh i