efx_allsource_three_pair_sanity
The partial allocation is envy-free; all values are positive and charity is owner-small; the explicit full EFX allocation preserves all starting utilities.
Statement
theorem efx_allsource_three_pair_sanity : (∀ i g, 0 < efx_allsource_three_pair_values i g) ∧ (∀ (i j : Fin 4), efx_allsource_three_pair_values i (![0,2,4,6] j) + efx_allsource_three_pair_values i (![1,3,5,7] j) ≤ 10) ∧ (∀ (i : Fin 4), efx_allsource_three_pair_values i (![0,2,4,6] i) + efx_allsource_three_pair_values i (![1,3,5,7] i) = 10) ∧ (∀ (i : Fin 4), efx_allsource_three_pair_values i 8 ≤ efx_allsource_three_pair_values i (![0,2,4,6] i) ∧ efx_allsource_three_pair_values i 8 ≤ efx_allsource_three_pair_values i (![1,3,5,7] i)) ∧ is_efx_goods (fun i (g : Fin 8) => (efx_allsource_three_pair_values i g.castSucc : ℝ)) ![(0 : Fin 4),0,1,1,2,2,3,3] ∧ is_efx_goods (fun i g => (efx_allsource_three_pair_values i g : ℝ)) ![(0 : Fin 4),0,1,3,2,0,1,2,3] ∧ (∀ i : Fin 4, (10 : ℝ) ≤ additive_valuation (fun g => (efx_allsource_three_pair_values i g : ℝ)) (bundle_of ![(0 : Fin 4),0,1,3,2,0,1,2,3] i))
- Source
- Four-agent envy-free one-charity three-split barrier for OP-7; SMT experiment 11699 and independent enumeration 11701. Both are evidence, not Lean proofs.
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- efx_allsource_three_pair_valuesPositive four-agent values for four original pairs and one charity good.
- 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.
- Used by 1
- efx_three_pair_anchor_sanityThe starting allocation is envy-free with r+2 goods per bundle and one charity good; the lifted complete witness is EFX.
The proof, explained
The theorem verifies that a concrete valuation profile on 4 agents and 9 goods satisfies several structural sanity conditions, that both an initial 8-good pairing and an explicit 9-good complete allocation are envy-free up to any good (EFX), and that every agent achieves at least their starting utility of 10 in the complete allocation. The first four sanity conditions (positivity, pair valuation upper bounds, exact starting utilities, and charity item size) are verified directly by exhaustive kernel computation. Both EFX conditions are reduced from real-valued statements to decidable integer inequalities using `is_efx_goods_nat_cast_iff` and decided by the kernel. Finally, the utility bound is proved by case analysis over all four agents and computing the concrete bundle values.
The valuation profile is strictly positive, all agents value every initial two-good bundle at at most 10, each agent values their own initial bundle at exactly 10, and unallocated good 8 is weakly smaller than each good in an agent's own bundle.
The goal is a conjunction of seven statements. The `refine` tactic splits it into seven subgoals and immediately discharges the first four using `decide +kernel`. Because there are only 4 agents and 9 goods with explicit concrete integer values, these four universal quantifications over finite sets are decidable propositions that Lean's kernel verifies by exhaustive enumeration.
refine ⟨by decide +kernel, by decide +kernel, by decide +kernel, by decide +kernel, ?_, ?_, ?_⟩
The initial partial allocation of the first 8 goods into pairs (allocating goods {0,1} to agent 0, {2,3} to agent 1, {4,5} to agent 2, and {6,7} to agent 3) is EFX. automation
We apply the equivalence lemma `is_efx_goods_nat_cast_iff` to rephrase the real-valued EFX condition into an equivalent inequality over natural numbers: for every pair of distinct agents i ≠ j and every good g in j's bundle, the sum of values of bundle j to agent i is bounded by the sum of values of bundle i plus the value of g. Because all sets and values are finite, the kernel decision procedure `decide +kernel` verifies this condition by exhaustive computation.
uses
is_efx_goods_nat_cast_iff· apply (is_efx_goods_nat_cast_iff _ _).mpr decide +kernel
The complete allocation of all 9 goods (allocating {0, 1, 5} to agent 0, {2, 6} to agent 1, {4, 7} to agent 2, and {3, 8} to agent 3) is EFX. automation
As with the partial allocation, we apply `is_efx_goods_nat_cast_iff` to reduce the real-valued EFX property for this complete 9-good allocation to a finite check over natural numbers, which `decide +kernel` closes by exhaustive kernel evaluation.
uses
is_efx_goods_nat_cast_iff· apply (is_efx_goods_nat_cast_iff _ _).mpr decide +kernel
Every agent receives a bundle with total additive valuation of at least 10 in the complete allocation. automation
We introduce an arbitrary agent i and simplify the definition of `additive_valuation` into a sum over the bundle allocated to agent i. We then split into the four possible agents via `fin_cases i`. In each case, `norm_cast` calculates the bundle value and confirms it is at least 10: agent 0 receives {0, 1, 5} with value 4 + 6 + 8 = 18; agent 1 receives {2, 6} with value 6 + 7 = 13; agent 2 receives {4, 7} with value 6 + 7 = 13; and agent 3 receives {3, 8} with value 8 + 5 = 13.
· intro i dsimp [additive_valuation] fin_cases i <;> norm_cast
is_efx_goods_nat_cast_iff- An allocation of goods with natural-number valuations satisfies the real-valued EFX (envy-free up to any good) condition if and only if for every pair of distinct agents i ≠ j and each good g in j's bundle, the sum of i's valuations for goods in j's bundle is at most the sum of i's valuations for goods in i's bundle plus i's valuation for g.
- The proof relies heavily on computational reflection via Lean's kernel (`decide +kernel`), which evaluates finite quantifications and arithmetic over small finite domains by exhaustive computation rather than generating symbolic deduction steps.
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_sanity : (∀ i g, 0 < efx_allsource_three_pair_values i g) ∧ (∀ (i j : Fin 4), efx_allsource_three_pair_values i (![0,2,4,6] j) + efx_allsource_three_pair_values i (![1,3,5,7] j) ≤ 10) ∧ (∀ (i : Fin 4), efx_allsource_three_pair_values i (![0,2,4,6] i) + efx_allsource_three_pair_values i (![1,3,5,7] i) = 10) ∧ (∀ (i : Fin 4), efx_allsource_three_pair_values i 8 ≤ efx_allsource_three_pair_values i (![0,2,4,6] i) ∧ efx_allsource_three_pair_values i 8 ≤ efx_allsource_three_pair_values i (![1,3,5,7] i)) ∧ is_efx_goods (fun i (g : Fin 8) => (efx_allsource_three_pair_values i g.castSucc : ℝ)) ![(0 : Fin 4),0,1,1,2,2,3,3] ∧ is_efx_goods (fun i g => (efx_allsource_three_pair_values i g : ℝ)) ![(0 : Fin 4),0,1,3,2,0,1,2,3] ∧ (∀ i : Fin 4, (10 : ℝ) ≤ additive_valuation (fun g => (efx_allsource_three_pair_values i g : ℝ)) (bundle_of ![(0 : Fin 4),0,1,3,2,0,1,2,3] i)) := by refine ⟨by decide +kernel, by decide +kernel, by decide +kernel, by decide +kernel, ?_, ?_, ?_⟩ · apply (is_efx_goods_nat_cast_iff _ _).mpr decide +kernel · apply (is_efx_goods_nat_cast_iff _ _).mpr decide +kernel · intro i dsimp [additive_valuation] fin_cases i <;> norm_cast