efx_no_self_three_split_sanity
The matrix is positive; each agent values every old triple equally at her baseline, values every good in her own triple at least as much as charity, and each triple has a good that some foreign agent values below charity. The initial partial allocation is EFX.
Statement
theorem efx_no_self_three_split_sanity : (∀ i g, 0 < efx_no_self_three_split_values i g) ∧ (∀ i j, efx_no_self_three_split_value i (efx_no_self_three_split_old j) = efx_no_self_three_split_baseline i) ∧ (∀ i g, g ∈ efx_no_self_three_split_old i → efx_no_self_three_split_values i 12 ≤ efx_no_self_three_split_values i g) ∧ (∀ j, ∃ i : Fin 4, i ≠ j ∧ ∃ g ∈ efx_no_self_three_split_old j, efx_no_self_three_split_values i g < efx_no_self_three_split_values i 12) ∧ is_efx_goods (fun i (g : Fin 12) => (efx_no_self_three_split_values i g.castSucc : ℝ)) ![(0 : Fin 4),0,0,1,1,1,2,2,2,3,3,3]
- 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 7
- 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),…
- efx_no_self_three_split_valueThe natural additive value to i of the goods in S.
- efx_no_self_three_split_oldThe old partial allocation consists of four consecutive triples; good 12 is unallocated.
- efx_no_self_three_split_baselineEach agent’s value of every old triple, and hence her initial utility.
- 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.
- Used by 1
- efx_no_self_three_split_no_self_championNo owner self-champions even under inclusion-minimality: every subset of her old triple plus charity that she prefers is strongly envied…
The proof, explained
The theorem verifies that a concrete 4-agent, 13-good valuation matrix and initial partition of the first 12 goods satisfy the five structural properties required of a counterexample in fair division. The proof decomposes the conjunction into five finite verification goals: positivity, equal triple valuation at baseline, lower bounds on own items versus charity, existence of items valued strictly below charity by an outside agent, and EFX of the partial allocation. Each condition is verified by finite exhaustive computation via `decide`, with the EFX property first rewritten from real arithmetic to natural arithmetic via `is_efx_goods_nat_cast_iff`.
The goal is decomposed into five independent sanity conditions.
Using `refine ⟨...⟩`, the conjunction is split into five subgoals: strict positivity of all valuations, equality of bundle values to baseline, lower bounds on own goods relative to charity, existence in each bundle of a good valued below charity by an outside agent, and envy-freeness up to any good (EFX) of the initial allocation.
refine ⟨?_, ?_, ?_, ?_, ?_⟩All entries in the valuation matrix are strictly positive.
For all 4 agents and 13 goods, the valuation satisfies 0 < v_{i,g}. Direct evaluation across the finite matrix via `decide` confirms the claim.
· decideEach agent values every triple bundle equally at her baseline.
For every agent i and each of the four triples j, the sum of agent i's valuations for the items in bundle j equals agent i's baseline value (69, 70, 51, and 37 for agents 0 through 3, respectively). All 16 equalities are verified by computation with `decide`.
· decideEach agent values every good in her own bundle at least as much as the charity good.
For each agent i and every item g in bundle i, the inequality v_{i, 12} ≤ v_{i, g} holds, where good 12 is the charity item. This is verified across all 12 allocated goods by direct evaluation with `decide`.
· decideEvery bundle contains a good that some foreign agent values strictly below charity.
For each bundle j, there exists an agent i ≠ j and an item g in bundle j such that v_{i, g} < v_{i, 12}. Lean's `decide` tactic checks this existential condition by exhaustively searching over the finite agent and item domains.
· decideThe initial allocation of the first 12 goods is envy-free up to any good (EFX).
Rewriting with `is_efx_goods_nat_cast_iff` converts the EFX condition on real valuations into an equivalent inequality on natural numbers: for every pair of distinct agents i ≠ j and every item g in bundle j, the value of bundle j to agent i is bounded by the value of bundle i to agent i plus the value of g to agent i. The resulting finite set of arithmetic checks is closed by exhaustive evaluation (`decide`).
uses
is_efx_goods_nat_cast_iff· rw [is_efx_goods_nat_cast_iff] decide
is_efx_goods_nat_cast_iff- An allocation of goods is EFX under real-valued valuations given by casting from natural numbers if and only if for all distinct agents i ≠ j and each good g in agent j's bundle, agent i's total valuation for bundle j is at most her valuation for bundle i plus her valuation for g.
- The proof relies on exhaustive finite verification via `decide`, which evaluates each decidable proposition by direct computation in Lean's kernel.
- Goods 0 through 11 are embedded into the 13-good universe via `.castSucc`, leaving good 12 as the unallocated charity item.
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_sanity : (∀ i g, 0 < efx_no_self_three_split_values i g) ∧ (∀ i j, efx_no_self_three_split_value i (efx_no_self_three_split_old j) = efx_no_self_three_split_baseline i) ∧ (∀ i g, g ∈ efx_no_self_three_split_old i → efx_no_self_three_split_values i 12 ≤ efx_no_self_three_split_values i g) ∧ (∀ j, ∃ i : Fin 4, i ≠ j ∧ ∃ g ∈ efx_no_self_three_split_old j, efx_no_self_three_split_values i g < efx_no_self_three_split_values i 12) ∧ is_efx_goods (fun i (g : Fin 12) => (efx_no_self_three_split_values i g.castSucc : ℝ)) ![(0 : Fin 4),0,0,1,1,1,2,2,2,3,3,3] := by refine ⟨?_, ?_, ?_, ?_, ?_⟩ · decide · decide · decide · decide · rw [is_efx_goods_nat_cast_iff] decide