efx_no_self_three_split_full_efx
A complete EFX allocation of the matrix has owners (2,1,2,1,3,2,3,1,0,0,0,0,0).
Statement
theorem efx_no_self_three_split_full_efx : is_efx_goods (fun i g => (efx_no_self_three_split_values i g : ℝ)) ![(2 : Fin 4),1,2,1,3,2,3,1,0,0,0,0,0]
- Source
- Positive equal-triple no-self-champion obstruction to the OP-7 two-bundle exchange route, experiments 11462–11471.
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- efx_no_self_three_split_valuesThe positive natural-valued matrix with rows (3,23,43,1,38,30,35,1,33,2,47,20,3), (1,25,44,40,9,21,1,41,28,34,1,35,3),…
- 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
To show that the given allocation of 13 goods among 4 agents is envy-free up to any good (EFX), the proof first rewrites the definition into an equivalent arithmetic inequality over the natural numbers. This eliminates subtraction by adding the value of the removed good to the right-hand side. Lean then checks the finitely many resulting inequalities by direct computation.
It suffices to verify the EFX condition as a natural-number inequality without subtraction for each pair of distinct agents and each good.
The definition of an EFX allocation requires that agent i values agent j's bundle with any item g removed at no more than i's own bundle. Rewriting with `is_efx_goods_nat_cast_iff` converts this real-valued condition into the equivalent natural-number condition: for all distinct i and j and every g in j's bundle, ∑_{h ∈ bundle(j)} v(i, h) ≤ ∑_{h ∈ bundle(i)} v(i, h) + v(i, g), eliminating set erasure and subtraction.
uses
is_efx_goods_nat_cast_iffrw [is_efx_goods_nat_cast_iff]The candidate allocation satisfies the EFX inequalities for all agents and items. automation
Because the number of agents (4) and goods (13) is finite and the valuation matrix and allocation vector are concrete, the universal quantification over all pairs of distinct agents and all assigned items is a decidable property. The `decide` tactic checks every case by finite evaluation and arithmetic computation.
decide
is_efx_goods_nat_cast_iff- For natural-number valuations, an allocation is EFX if and only if for all distinct agents i ≠ j and each item g in j's bundle, the sum of i's valuations for j's bundle is at most the sum of i's valuations for i's own bundle plus i's valuation for g.
- The proof completes via computational reflection (`decide`), evaluating the EFX condition on all ordered pairs of distinct agents and all goods in their bundles by direct arithmetic.
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_no_self_three_split_full_efx : is_efx_goods (fun i g => (efx_no_self_three_split_values i g : ℝ)) ![(2 : Fin 4),1,2,1,3,2,3,1,0,0,0,0,0] := by rw [is_efx_goods_nat_cast_iff] decide