AFTD Auto-Formalizing Theoretical Domains

efx_three_small_goods_obstruction_sanity

theoremverified

In the explicit eleven-good instance all natural item values are strictly positive, and each of goods 8,9,10 is no more valuable than every old good 0 through 7 for every agent. The starting allocation of the first ten goods is (0,0,1,1,2,2,3,3,0,1); it is EFX after casting to reals and has own utilities (883,1992,800,800). The full allocation (0,0,1,1,2,2,3,3,0,0,1) is EFX after casting to reals and has own utilities (998,1604,800,800). Assigning the first eight goods in adjacent pairs to the four agents in order gives old-only utilities (800,1600,800,800).

Statement

theorem efx_three_small_goods_obstruction_sanity :
    (∀ i g, 0 < efx_three_small_goods_obstruction_values i g) ∧
    (∀ (i : Fin 4) (g : Fin 3) (h : Fin 8),
      efx_three_small_goods_obstruction_values i (Fin.natAdd 8 g) ≤ efx_three_small_goods_obstruction_values i (Fin.castAdd 3 h)) ∧
    is_efx_goods (fun i (g : Fin 10) => (efx_three_small_goods_obstruction_values i g.castSucc : ℝ))
      ![(0 : Fin 4),0,1,1,2,2,3,3,0,1] ∧
    (∀ i, additive_valuation (fun g : Fin 10 => (efx_three_small_goods_obstruction_values i g.castSucc : ℝ))
      (bundle_of ![(0 : Fin 4),0,1,1,2,2,3,3,0,1] i) = (efx_three_small_goods_obstruction_threshold i : ℝ)) ∧
    is_efx_goods (fun i g => (efx_three_small_goods_obstruction_values i g : ℝ))
      ![(0 : Fin 4),0,1,1,2,2,3,3,0,0,1] ∧
    (∀ i, additive_valuation (fun g => (efx_three_small_goods_obstruction_values i g : ℝ))
      (bundle_of ![(0 : Fin 4),0,1,1,2,2,3,3,0,0,1] i) =
        (![998,1604,800,800] i : ℝ)) ∧
    (∀ i, additive_valuation (fun g : Fin 8 => (efx_three_small_goods_obstruction_values i (Fin.castAdd 3 g) : ℝ))
      (bundle_of ![(0 : Fin 4),0,1,1,2,2,3,3] i) =
        (efx_three_small_goods_obstruction_original_threshold i : ℝ))
Source
Route obstruction for efx_four_agents_additive_exists (OP-7), campaign IN-404, 2026-11-01. Experiments 11265, 11268, and 11269. The last independently exhausts all 16384 full coarse assignments and all 1152 old-permutation two-bonus states; a row scaling removes a welfare-maximizer tie. General Pareto-monotone EFX completion barriers are already known in arXiv:2002.05119v3 Section 5. This explicit three-universally-small-goods example constrains maximum-sum two-bonus completion, not EFX existence or the original-diagonal three-bonus conjecture, and carries no research-level novelty claim.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • efx_three_small_goods_obstruction_valuesThe explicit positive four-agent eleven-good natural-valued matrix from experiment 11269, with four old adjacent pairs among goods 0…
  • efx_three_small_goods_obstruction_thresholdThe four current utility thresholds (883,1992,800,800), attained by the starting EFX allocation of the first ten goods in the explicit…
  • efx_three_small_goods_obstruction_original_thresholdThe four original old-only utilities (800,1600,800,800), attained by assigning the first eight goods in adjacent pairs to the four agents…
  • 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 that an explicit 4-agent, 11-good instance satisfies the structural conditions and utility thresholds required for an EFX obstruction. The seven conjuncts assert strict positivity of all item values, that the three added goods are valued at most as much as any of the eight original goods, the EFX property of two candidate allocations (on 10 and 11 goods), and the exact bundle utilities across three allocations. The proof resolves these subgoals by direct computation: the positivity and size bounds are discharged by kernel evaluation, the EFX claims are converted from real to natural arithmetic via `is_efx_goods_nat_cast_iff` and decided by the kernel, and the bundle valuations are verified by case-exhaustion over all four agents.

  1. All 44 valuation values are strictly positive, and each of the three additional goods (goods 8, 9, 10) is valued at most as much as any of the eight original goods (goods 0 through 7) by every agent. automation

    The proof breaks the 7-part conjunction into subgoals using `refine`. The first two conjuncts are universal quantifications over finite domains (4 agents and 11 goods for positivity; 4 agents, 3 small goods, and 8 original goods for the size inequality). Because the valuation table `efx_three_small_goods_obstruction_values` is explicitly defined by natural numbers, both claims are discharged immediately by finite kernel evaluation (`decide +kernel`).

    line 19

      refine ⟨by decide +kernel, by decide +kernel, ?_, ?_, ?_, ?_, ?_⟩
  2. The starting allocation of the first ten goods, σ = (0, 0, 1, 1, 2, 2, 3, 3, 0, 1), is EFX. automation

    Applying the equivalence lemma `is_efx_goods_nat_cast_iff` reduces the EFX condition on real valuations to an equivalent check on natural numbers, avoiding real arithmetic. Since the number of agents and items is finite, Lean's kernel evaluator (`decide +kernel`) checks all envy-freeness up to any good inequalities across all pairs of agents and bundle items.

    lines 20–21

    uses is_efx_goods_nat_cast_iff

      · apply (is_efx_goods_nat_cast_iff _ _).mpr
        decide +kernel
  3. In the 10-good allocation, the four agents receive bundles with total utilities 883, 1992, 800, and 800, respectively.

    For an arbitrary agent i, `dsimp [additive_valuation]` unfolds the bundle valuation as a sum of values over agent i's allocated items. Exhaustive case analysis on the four agents (`fin_cases i`) followed by `norm_cast` computes the sum for each agent from the concrete table and verifies that the results match the threshold vector (883, 1992, 800, 800).

    lines 22–24

      · intro i
        dsimp [additive_valuation]
        fin_cases i <;> norm_cast
  4. The full allocation of all eleven goods, σ = (0, 0, 1, 1, 2, 2, 3, 3, 0, 0, 1), is EFX. automation

    As with the 10-good allocation, applying `is_efx_goods_nat_cast_iff` rephrases the EFX property as a finite set of inequalities over natural numbers. Kernel computation (`decide +kernel`) exhaustively verifies that no agent envies another up to the removal of any item.

    lines 25–26

    uses is_efx_goods_nat_cast_iff

      · apply (is_efx_goods_nat_cast_iff _ _).mpr
        decide +kernel
  5. In the full 11-good allocation, the four agents receive bundles with total utilities 998, 1604, 800, and 800, respectively.

    Unfolding `additive_valuation` expresses each agent's utility as the sum of values of their assigned goods in the full 11-good allocation. Testing all four agents via `fin_cases i` and computing the sums with `norm_cast` confirms they equal 998, 1604, 800, and 800.

    lines 27–29

      · intro i
        dsimp [additive_valuation]
        fin_cases i <;> norm_cast
  6. Under the baseline allocation assigning the first eight goods in pairs to the four agents, the agents receive utilities 800, 1600, 800, and 800, respectively.

    Unfolding `additive_valuation` and performing case analysis over the four agents (`fin_cases i` with `norm_cast`) calculates the sum of values of the two assigned original goods for each agent, confirming they match the original threshold vector (800, 1600, 800, 800).

    lines 30–32

      · intro i
        dsimp [additive_valuation]
        fin_cases i <;> norm_cast
is_efx_goods_nat_cast_iff
An allocation σ is EFX under real-cast additive valuations with natural-number values if and only if for every pair of distinct agents i ≠ j and every good g in j's bundle, the sum of values of j's bundle to agent i is at most the sum of values of i's bundle 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

open Function Finsettheorem efx_three_small_goods_obstruction_sanity :    (∀ i g, 0 < efx_three_small_goods_obstruction_values i g) ∧    (∀ (i : Fin 4) (g : Fin 3) (h : Fin 8),      efx_three_small_goods_obstruction_values i (Fin.natAdd 8 g) ≤ efx_three_small_goods_obstruction_values i (Fin.castAdd 3 h)) ∧    is_efx_goods (fun i (g : Fin 10) => (efx_three_small_goods_obstruction_values i g.castSucc : ℝ))      ![(0 : Fin 4),0,1,1,2,2,3,3,0,1] ∧    (∀ i, additive_valuation (fun g : Fin 10 => (efx_three_small_goods_obstruction_values i g.castSucc : ℝ))      (bundle_of ![(0 : Fin 4),0,1,1,2,2,3,3,0,1] i) = (efx_three_small_goods_obstruction_threshold i : ℝ)) ∧    is_efx_goods (fun i g => (efx_three_small_goods_obstruction_values i g : ℝ))      ![(0 : Fin 4),0,1,1,2,2,3,3,0,0,1] ∧    (∀ i, additive_valuation (fun g => (efx_three_small_goods_obstruction_values i g : ℝ))      (bundle_of ![(0 : Fin 4),0,1,1,2,2,3,3,0,0,1] i) =        (![998,1604,800,800] i : ℝ)) ∧    (∀ i, additive_valuation (fun g : Fin 8 => (efx_three_small_goods_obstruction_values i (Fin.castAdd 3 g) : ℝ))      (bundle_of ![(0 : Fin 4),0,1,1,2,2,3,3] i) =        (efx_three_small_goods_obstruction_original_threshold i : ℝ)) := by  refine ⟨by decide +kernel, by decide +kernel, ?_, ?_, ?_, ?_, ?_⟩  · apply (is_efx_goods_nat_cast_iff _ _).mpr    decide +kernel  · intro i    dsimp [additive_valuation]    fin_cases i <;> norm_cast  · apply (is_efx_goods_nat_cast_iff _ _).mpr    decide +kernel  · intro i    dsimp [additive_valuation]    fin_cases i <;> norm_cast  · intro i    dsimp [additive_valuation]    fin_cases i <;> norm_cast
See it in the graphDiscuss this resultChallenge it