efx_allsource_pair_sanity
The old state is envy-free with all values positive and charity small for each owner; the explicit complete witness is EFX and IR.
Statement
theorem efx_allsource_pair_sanity : (∀ i g, 0 < efx_allsource_pair_values i g) ∧ (∀ (i j : Fin 4), efx_allsource_pair_values i (![0,2,4,6] j) + efx_allsource_pair_values i (![1,3,5,7] j) = efx_allsource_pair_baseline i) ∧ (∀ (i : Fin 4), efx_allsource_pair_values i 8 ≤ efx_allsource_pair_values i (![0,2,4,6] i) ∧ efx_allsource_pair_values i 8 ≤ efx_allsource_pair_values i (![1,3,5,7] i)) ∧ is_efx_goods (fun i (g : Fin 8) => (efx_allsource_pair_values i g.castSucc : ℝ)) ![(0 : Fin 4),0,1,1,2,2,3,3] ∧ is_efx_goods (fun i g => (efx_allsource_pair_values i g : ℝ)) ![(0 : Fin 4),0,1,0,1,2,3,3,2] ∧ (∀ i : Fin 4, (efx_allsource_pair_baseline i : ℝ) ≤ additive_valuation (fun g => (efx_allsource_pair_values i g : ℝ)) (bundle_of ![(0 : Fin 4),0,1,0,1,2,3,3,2] i))
- Source
- Three-valued all-source no-self two-split EFX obstruction for OP-7; experiments 11638–11642.
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- efx_allsource_pair_valuesThree-valued positive four-agent values for four old pairs and one charity good.
- efx_allsource_pair_baselineThe four starting utilities.
- 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 proof verifies that an explicit 4-agent, 9-good valuation instance satisfies six sanity conditions: positivity of all valuations, pair-sum baseline equality, charity item bounds, EFX of the 8-item allocation, and both EFX and baseline individual rationality for the 9-item allocation. After decomposing the conjunction, the first three elementary properties are verified directly by finite evaluation (`decide`). The EFX conditions for both the 8-item and 9-item allocations are transferred from the reals to natural numbers using `is_efx_goods_nat_cast_iff` and then verified by `decide`. Finally, individual rationality for the 9-item allocation is verified over the natural numbers by `decide` and lifted to real additive valuations using `Nat.cast_sum`.
The goal decomposes into six subgoals, and the first three elementary properties hold: all valuations are strictly positive, each complementary pair of goods sums to the baseline value 4 for every agent, and the charity item 8 is valued at most as much as either item in an agent's own pair.
The overarching 6-way conjunction is decomposed into six separate subgoals. The first three subgoals are finitary checks on the explicit valuation table `efx_allsource_pair_values` and baseline vector `efx_allsource_pair_baseline`. Because these properties quantify over the finite types `Fin 4` and `Fin 9`, Lean's `decide` tactic checks every instance by exhaustive finite evaluation.
refine ⟨?_, ?_, ?_, ?_, ?_, ?_⟩ · decide · decide · decide
The initial 8-item allocation is EFX with respect to the real-valued valuations.
By lemma `is_efx_goods_nat_cast_iff`, the EFX condition for real valuations cast from natural numbers is equivalent to an explicit inequality over the natural numbers: for all distinct agents i ≠ j and each item g in j's bundle, the valuation of j's bundle is at most that of i's bundle plus the value of g. Since there are only 4 agents and 8 items, `decide` verifies this finite condition by exhaustive computation.
uses
is_efx_goods_nat_cast_iff· refine (is_efx_goods_nat_cast_iff (v := fun i (g : Fin 8) => efx_allsource_pair_values i g.castSucc) _).mpr ?_ decide
The complete 9-item allocation is EFX with respect to the real-valued valuations.
Similarly, `is_efx_goods_nat_cast_iff` reduces the EFX condition on the 9-item allocation to the corresponding inequality over natural numbers. Lean's `decide` tactic then verifies this finite combinatorial check across all agent pairs and goods by direct evaluation.
uses
is_efx_goods_nat_cast_iff· refine (is_efx_goods_nat_cast_iff (v := fun i (g : Fin 9) => efx_allsource_pair_values i g) _).mpr ?_ decide
In the 9-item allocation, the sum of natural-number valuations in each agent's bundle is at least that agent's baseline value.
We establish an intermediate lemma (`hnat`) asserting that for every agent i ∈ {0, 1, 2, 3}, the sum of the natural-number values of items in agent i's bundle is at least the baseline value 4. This is a finite check over the four agents and is closed directly by `decide`.
· have hnat : ∀ i : Fin 4, efx_allsource_pair_baseline i ≤ ∑ g ∈ bundle_of ![(0 : Fin 4),0,1,0,1,2,3,3,2] i, efx_allsource_pair_values i g := by decide
In the 9-item allocation, every agent's real additive valuation is at least their baseline value.
Fix an arbitrary agent i. Casting the natural-number inequality `hnat i` to the real numbers yields `hcast`. Unfolding `additive_valuation` and distributing the coercion across the finite sum via `Nat.cast_sum` shows that the real additive valuation equals the cast of the natural sum (`hsum`). Rewriting the goal with `hsum` and applying `hcast` establishes that agent i achieves at least their baseline valuation in ℝ.
uses
Nat.cast_sumintro i have hcast : ((efx_allsource_pair_baseline i : ℕ) : ℝ) ≤ ((∑ g ∈ bundle_of ![(0 : Fin 4),0,1,0,1,2,3,3,2] i, efx_allsource_pair_values i g : ℕ) : ℝ) := by exact_mod_cast hnat i have hsum : additive_valuation (fun g => (efx_allsource_pair_values i g : ℝ)) (bundle_of ![(0 : Fin 4),0,1,0,1,2,3,3,2] i) = ((∑ g ∈ bundle_of ![(0 : Fin 4),0,1,0,1,2,3,3,2] i, efx_allsource_pair_values i g : ℕ) : ℝ) := by simp [additive_valuation, Nat.cast_sum] rw [hsum] exact hcast
is_efx_goods_nat_cast_iff- An allocation of goods with valuations cast from natural numbers to the reals is EFX if and only if for all distinct agents i ≠ j and every item g in j's bundle, the sum of i's values for j's bundle is at most the sum of i's values for their own bundle plus i's value for g.
Nat.cast_sum- The cast of a finite sum of natural numbers into an additive structure with one (such as the real numbers) equals the sum of the casts of the individual terms.
- Because Lean distinguishes natural numbers (ℕ) from real numbers (ℝ), and the decision procedure `decide` operates only on computable operations over finite types, the proofs of EFX and individual rationality work by checking the underlying inequalities over ℕ and lifting the results to ℝ using `is_efx_goods_nat_cast_iff`, `exact_mod_cast`, and `Nat.cast_sum`.
- The verification of all finite combinatorial conditions (positivity, pair sums, charity item bounds, EFX conditions, and baseline sums) is performed entirely by Lean's computational kernel via `decide`.
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_pair_sanity : (∀ i g, 0 < efx_allsource_pair_values i g) ∧ (∀ (i j : Fin 4), efx_allsource_pair_values i (![0,2,4,6] j) + efx_allsource_pair_values i (![1,3,5,7] j) = efx_allsource_pair_baseline i) ∧ (∀ (i : Fin 4), efx_allsource_pair_values i 8 ≤ efx_allsource_pair_values i (![0,2,4,6] i) ∧ efx_allsource_pair_values i 8 ≤ efx_allsource_pair_values i (![1,3,5,7] i)) ∧ is_efx_goods (fun i (g : Fin 8) => (efx_allsource_pair_values i g.castSucc : ℝ)) ![(0 : Fin 4),0,1,1,2,2,3,3] ∧ is_efx_goods (fun i g => (efx_allsource_pair_values i g : ℝ)) ![(0 : Fin 4),0,1,0,1,2,3,3,2] ∧ (∀ i : Fin 4, (efx_allsource_pair_baseline i : ℝ) ≤ additive_valuation (fun g => (efx_allsource_pair_values i g : ℝ)) (bundle_of ![(0 : Fin 4),0,1,0,1,2,3,3,2] i)) := by refine ⟨?_, ?_, ?_, ?_, ?_, ?_⟩ · decide · decide · decide · refine (is_efx_goods_nat_cast_iff (v := fun i (g : Fin 8) => efx_allsource_pair_values i g.castSucc) _).mpr ?_ decide · refine (is_efx_goods_nat_cast_iff (v := fun i (g : Fin 9) => efx_allsource_pair_values i g) _).mpr ?_ decide · have hnat : ∀ i : Fin 4, efx_allsource_pair_baseline i ≤ ∑ g ∈ bundle_of ![(0 : Fin 4),0,1,0,1,2,3,3,2] i, efx_allsource_pair_values i g := by decide intro i have hcast : ((efx_allsource_pair_baseline i : ℕ) : ℝ) ≤ ((∑ g ∈ bundle_of ![(0 : Fin 4),0,1,0,1,2,3,3,2] i, efx_allsource_pair_values i g : ℕ) : ℝ) := by exact_mod_cast hnat i have hsum : additive_valuation (fun g => (efx_allsource_pair_values i g : ℝ)) (bundle_of ![(0 : Fin 4),0,1,0,1,2,3,3,2] i) = ((∑ g ∈ bundle_of ![(0 : Fin 4),0,1,0,1,2,3,3,2] i, efx_allsource_pair_values i g : ℕ) : ℝ) := by simp [additive_valuation, Nat.cast_sum] rw [hsum] exact hcast