AFTD Auto-Formalizing Theoretical Domains

efx_allsource_pair_sanity

theoremverified

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

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

    lines 11–14

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

    lines 15–17

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

    lines 18–20

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

    lines 21–23

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

    lines 24–35

    uses Nat.cast_sum

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

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