efx_three_split_sanity
All values are positive. In the initial partial allocation (0,0,1,1,2,2,3,3), each agent values all four old bundles equally, values the unallocated ninth good no more than her own bundle, and the allocation is EFX. The complete allocation (0,0,1,3,1,2,0,2,3) is EFX.
Statement
theorem efx_three_split_sanity : (∀ i g, 0 < efx_three_split_values i g) ∧ (∀ (i j : Fin 4), additive_valuation (fun g : Fin 8 => (efx_three_split_values i g.castSucc : ℝ)) (bundle_of ![(0 : Fin 4),0,1,1,2,2,3,3] j) = additive_valuation (fun g : Fin 8 => (efx_three_split_values i g.castSucc : ℝ)) (bundle_of ![(0 : Fin 4),0,1,1,2,2,3,3] i)) ∧ (∀ i : Fin 4, (efx_three_split_values i 8 : ℝ) ≤ additive_valuation (fun g : Fin 8 => (efx_three_split_values i g.castSucc : ℝ)) (bundle_of ![(0 : Fin 4),0,1,1,2,2,3,3] i)) ∧ is_efx_goods (fun i (g : Fin 8) => (efx_three_split_values i g.castSucc : ℝ)) ![(0 : Fin 4),0,1,1,2,2,3,3] ∧ is_efx_goods (fun i g => (efx_three_split_values i g : ℝ)) ![(0 : Fin 4),0,1,3,1,2,0,2,3]
- Source
- Finite equal-pair obstruction to OP-7 completion routes, experiments 11408, 11409, 11411, 11412.
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- efx_three_split_valuesThe natural-valued four-agent nine-good matrix with rows (3,14,3,14,1,16,4,13,5), (1,5,5,1,5,1,2,4,3), (14,3,16,1,3,14,4,13,5), and…
- 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 verifies five sanity properties of an explicit fair-division instance with four agents and nine goods: strict positivity of all valuations, equal valuation across all four initial bundles by each agent, an upper bound on the unallocated ninth good's value relative to an agent's bundle, and envy-freeness up to any good (EFX) for both the initial 8-good and the full 9-good allocations. Because all valuations are explicit natural numbers on finite sets of agents and items, each claim is decided by computational reflection in Lean's kernel (`decide +kernel`). For bundle equalities and the ninth-good bound, the natural-number sums are evaluated by the kernel and cast to the real numbers, while the two EFX conditions are first reduced to natural-number inequalities via `is_efx_goods_nat_cast_iff` before kernel evaluation.
All valuation entries are strictly positive, leaving four remaining sanity conditions to be established.
The goal is a conjunction of five statements. Line 15 splits the conjunction using `refine`, providing an immediate proof for the first conjunct: that all valuation entries in `efx_three_split_values` are strictly positive. Since the four agents and nine goods form finite types and the matrix entries are concrete natural numbers, this first goal is evaluated and discharged directly by the kernel (`decide +kernel`).
refine ⟨by decide +kernel, ?_, ?_, ?_, ?_⟩
Under the initial allocation of eight goods, every agent values every agent's bundle equally.
An auxiliary statement `h` is introduced and proven over the natural numbers: for every pair of agents i and j, the sum of agent i's values for the items in bundle j equals that for bundle i. The kernel verifies this finite computation (`decide +kernel`). Then, introducing arbitrary agents i and j, unfolding `additive_valuation` into a sum over the bundle, and casting `h i j` from ℕ to ℝ using `exact_mod_cast` proves the equality in the real numbers.
· have h : ∀ (i j : Fin 4), (∑ g ∈ bundle_of ![(0 : Fin 4),0,1,1,2,2,3,3] j, efx_three_split_values i g.castSucc) = (∑ g ∈ bundle_of ![(0 : Fin 4),0,1,1,2,2,3,3] i, efx_three_split_values i g.castSucc) := by decide +kernel intro i j dsimp [additive_valuation] exact_mod_cast h i j
Every agent values the unallocated ninth good at most as much as their own bundle in the initial allocation.
An auxiliary statement `h` establishes that for each agent i, the natural-number valuation of good 8 is at most the sum of valuations of the goods in agent i's own bundle. This is verified by finite kernel computation (`decide +kernel`). Unfolding `additive_valuation` and casting `h i` from ℕ to ℝ via `exact_mod_cast` completes the step.
· have h : ∀ i : Fin 4, efx_three_split_values i 8 ≤ (∑ g ∈ bundle_of ![(0 : Fin 4),0,1,1,2,2,3,3] i, efx_three_split_values i g.castSucc) := by decide +kernel intro i dsimp [additive_valuation] exact_mod_cast h i
The initial allocation of the first eight goods is envy-free up to any good (EFX). automation
Applying `is_efx_goods_nat_cast_iff` transforms the real-valued EFX property into an equivalent finite condition on natural numbers: for any distinct agents i ≠ j and any good g in bundle j, the sum of bundle j to agent i is bounded by the sum of bundle i plus the value of g to agent i. The kernel checks every combination exhaustively (`decide +kernel`), closing the goal.
uses
is_efx_goods_nat_cast_iff· apply (is_efx_goods_nat_cast_iff (fun i (g : Fin 8) => efx_three_split_values i g.castSucc) _).mpr decide +kernel
The complete allocation of all nine goods is envy-free up to any good (EFX). automation
Just as in the previous step, `is_efx_goods_nat_cast_iff` reduces the EFX condition on all nine goods to a finite system of inequalities over natural numbers. The kernel evaluates all cases directly (`decide +kernel`), completing the proof.
uses
is_efx_goods_nat_cast_iff· apply (is_efx_goods_nat_cast_iff (fun i (g : Fin 9) => efx_three_split_values i g) _).mpr decide +kernel
is_efx_goods_nat_cast_iff- An allocation of goods with natural-number valuations satisfies EFX (envy-freeness up to any good) with real valuations if and only if for all distinct agents i ≠ j and each item g in j's bundle, the sum of values of bundle j to agent i is at most the sum of values of bundle i to agent i plus the value of g to agent i.
- All five properties reduce to finite combinatorial checks on an explicit 4 × 9 matrix of natural numbers. Lean carries out these checks computationally within the kernel using `decide +kernel`. Because valuations in the theorem statement are real-valued while the underlying matrix entries are natural numbers, casts via `exact_mod_cast` and the equivalence `is_efx_goods_nat_cast_iff` bridge the two settings.
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_three_split_sanity : (∀ i g, 0 < efx_three_split_values i g) ∧ (∀ (i j : Fin 4), additive_valuation (fun g : Fin 8 => (efx_three_split_values i g.castSucc : ℝ)) (bundle_of ![(0 : Fin 4),0,1,1,2,2,3,3] j) = additive_valuation (fun g : Fin 8 => (efx_three_split_values i g.castSucc : ℝ)) (bundle_of ![(0 : Fin 4),0,1,1,2,2,3,3] i)) ∧ (∀ i : Fin 4, (efx_three_split_values i 8 : ℝ) ≤ additive_valuation (fun g : Fin 8 => (efx_three_split_values i g.castSucc : ℝ)) (bundle_of ![(0 : Fin 4),0,1,1,2,2,3,3] i)) ∧ is_efx_goods (fun i (g : Fin 8) => (efx_three_split_values i g.castSucc : ℝ)) ![(0 : Fin 4),0,1,1,2,2,3,3] ∧ is_efx_goods (fun i g => (efx_three_split_values i g : ℝ)) ![(0 : Fin 4),0,1,3,1,2,0,2,3] := by refine ⟨by decide +kernel, ?_, ?_, ?_, ?_⟩ · have h : ∀ (i j : Fin 4), (∑ g ∈ bundle_of ![(0 : Fin 4),0,1,1,2,2,3,3] j, efx_three_split_values i g.castSucc) = (∑ g ∈ bundle_of ![(0 : Fin 4),0,1,1,2,2,3,3] i, efx_three_split_values i g.castSucc) := by decide +kernel intro i j dsimp [additive_valuation] exact_mod_cast h i j · have h : ∀ i : Fin 4, efx_three_split_values i 8 ≤ (∑ g ∈ bundle_of ![(0 : Fin 4),0,1,1,2,2,3,3] i, efx_three_split_values i g.castSucc) := by decide +kernel intro i dsimp [additive_valuation] exact_mod_cast h i · apply (is_efx_goods_nat_cast_iff (fun i (g : Fin 8) => efx_three_split_values i g.castSucc) _).mpr decide +kernel · apply (is_efx_goods_nat_cast_iff (fun i (g : Fin 9) => efx_three_split_values i g) _).mpr decide +kernel