AFTD Auto-Formalizing Theoretical Domains

efx_three_split_sanity

theoremverified

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.

  1. 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`).

    line 15

      refine ⟨by decide +kernel, ?_, ?_, ?_, ?_⟩
  2. 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.

    lines 16–22

      · 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
  3. 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.

    lines 23–28

      · 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
  4. 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.

    lines 29–30

    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
  5. 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.

    lines 31–32

    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.

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

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
See it in the graphDiscuss this resultChallenge it