efx_allsource_three_pair_perturbed_strict_sanity
The perturbed partial state is strictly envy-free, and the explicit complete allocation remains EFX.
Statement
theorem efx_allsource_three_pair_perturbed_strict_sanity : (∀ i g, 0 < efx_allsource_three_pair_perturbed_values i g) ∧ (∀ (i j : Fin 4), i ≠ j → efx_allsource_three_pair_perturbed_values i (![0,2,4,6] j) + efx_allsource_three_pair_perturbed_values i (![1,3,5,7] j) < efx_allsource_three_pair_perturbed_values i (![0,2,4,6] i) + efx_allsource_three_pair_perturbed_values i (![1,3,5,7] i)) ∧ is_efx_goods (fun i g => (efx_allsource_three_pair_perturbed_values i g : ℝ)) ![(0 : Fin 4),0,1,3,2,0,1,2,3]
- Source
- Binary perturbation of the four-agent three-split barrier; experiment 11706 and the integer-gap projection.
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- efx_allsource_three_pair_perturbed_valuesA binary nondegenerate perturbation of the four-pair instance.
- 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.
The proof, explained
The theorem establishes three sanity properties for a perturbed valuation matrix of 4 agents and 9 goods: positivity of valuations, strict envy-freeness of a partial allocation where each agent holds a pair of goods, and the EFX property of an explicit complete allocation. The first two properties are finite decidable checks verified directly by kernel computation. The third property is reduced from real valuations to natural-number sums via `is_efx_goods_nat_cast_iff` and then likewise closed by kernel evaluation.
All valuations are strictly positive, the initial paired allocation of the first eight goods is strictly envy-free, and it remains only to show that the complete allocation is EFX.
The theorem is a three-part conjunction. The first conjunct asserts that all 36 entries of the valuation matrix are strictly positive. The second asserts that for all 12 pairs of distinct agents i ≠ j, agent i strictly prefers their assigned pair of goods {2i, 2i + 1} to agent j's pair {2j, 2j + 1}. Both are finite boolean checks over explicit numbers, and are proved immediately by kernel computation (`decide +kernel`), leaving the third conjunct—EFX of the complete allocation—as the only remaining goal.
refine ⟨by decide +kernel, by decide +kernel, ?_⟩
To prove that the complete allocation is EFX under real utilities, it suffices to verify the equivalent additive inequality over the natural-number valuations.
Applying the backward direction of `is_efx_goods_nat_cast_iff` translates the definition of EFX—originally stated over real valuations with set subtraction—into an equivalent arithmetic condition on ℕ: for every pair of distinct agents i ≠ j and each good g in j's bundle, ∑_{h ∈ bundle(j)} v(i, h) ≤ ∑_{h ∈ bundle(i)} v(i, h) + v(i, g).
uses
is_efx_goods_nat_cast_iffapply (is_efx_goods_nat_cast_iff _ _).mprThe complete allocation is EFX. automation
The goal is now a bounded universal quantifier over the finite sets of agents and goods checking simple linear inequalities of natural numbers. The Lean kernel computes the valuations and sums directly (`decide +kernel`), confirming that every required inequality holds.
decide +kernel
is_efx_goods_nat_cast_iff- an allocation is envy-free up to any good (EFX) under real-valued additive utilities given by natural-number valuations if and only if for every pair of distinct agents i and j and every good g assigned to j, the total value agent i assigns to j's bundle is at most the total value i assigns to their own bundle plus the value of g to i
- The proof delegates all finite numerical verifications—positivity of the valuations, strict envy-freeness between agent pairs, and the EFX inequalities—to direct Lean kernel evaluation (`decide +kernel`).
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_allsource_three_pair_perturbed_strict_sanity : (∀ i g, 0 < efx_allsource_three_pair_perturbed_values i g) ∧ (∀ (i j : Fin 4), i ≠ j → efx_allsource_three_pair_perturbed_values i (![0,2,4,6] j) + efx_allsource_three_pair_perturbed_values i (![1,3,5,7] j) < efx_allsource_three_pair_perturbed_values i (![0,2,4,6] i) + efx_allsource_three_pair_perturbed_values i (![1,3,5,7] i)) ∧ is_efx_goods (fun i g => (efx_allsource_three_pair_perturbed_values i g : ℝ)) ![(0 : Fin 4),0,1,3,2,0,1,2,3] := by refine ⟨by decide +kernel, by decide +kernel, ?_⟩ apply (is_efx_goods_nat_cast_iff _ _).mpr decide +kernel