AFTD Auto-Formalizing Theoretical Domains

efx_allsource_three_pair_perturbed_strict_sanity

theoremverified

The perturbed partial state is strictly envy-free, and the explicit complete allocation remains EFX.

Statement

theorem efx_allsource_three_pair_perturbed_strict_sanity :
  (∀ i g, 0 < efx_allsource_three_pair_perturbed_values i g) ∧
  (∀ (i j : Fin 4), i ≠ j →
    efx_allsource_three_pair_perturbed_values i (![0,2,4,6] j) + efx_allsource_three_pair_perturbed_values i (![1,3,5,7] j) <
      efx_allsource_three_pair_perturbed_values i (![0,2,4,6] i) + efx_allsource_three_pair_perturbed_values i (![1,3,5,7] i)) ∧
  is_efx_goods (fun i g => (efx_allsource_three_pair_perturbed_values i g : ℝ)) ![(0 : Fin 4),0,1,3,2,0,1,2,3]
Source
Binary perturbation of the four-agent three-split barrier; experiment 11706 and the integer-gap projection.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • efx_allsource_three_pair_perturbed_valuesA binary nondegenerate perturbation of the four-pair instance.
  • 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.

The proof, explained

The theorem establishes three sanity properties for a perturbed valuation matrix of 4 agents and 9 goods: positivity of valuations, strict envy-freeness of a partial allocation where each agent holds a pair of goods, and the EFX property of an explicit complete allocation. The first two properties are finite decidable checks verified directly by kernel computation. The third property is reduced from real valuations to natural-number sums via `is_efx_goods_nat_cast_iff` and then likewise closed by kernel evaluation.

  1. All valuations are strictly positive, the initial paired allocation of the first eight goods is strictly envy-free, and it remains only to show that the complete allocation is EFX.

    The theorem is a three-part conjunction. The first conjunct asserts that all 36 entries of the valuation matrix are strictly positive. The second asserts that for all 12 pairs of distinct agents i ≠ j, agent i strictly prefers their assigned pair of goods {2i, 2i + 1} to agent j's pair {2j, 2j + 1}. Both are finite boolean checks over explicit numbers, and are proved immediately by kernel computation (`decide +kernel`), leaving the third conjunct—EFX of the complete allocation—as the only remaining goal.

    line 7

      refine ⟨by decide +kernel, by decide +kernel, ?_⟩
  2. To prove that the complete allocation is EFX under real utilities, it suffices to verify the equivalent additive inequality over the natural-number valuations.

    Applying the backward direction of `is_efx_goods_nat_cast_iff` translates the definition of EFX—originally stated over real valuations with set subtraction—into an equivalent arithmetic condition on ℕ: for every pair of distinct agents i ≠ j and each good g in j's bundle, ∑_{h ∈ bundle(j)} v(i, h) ≤ ∑_{h ∈ bundle(i)} v(i, h) + v(i, g).

    line 8

    uses is_efx_goods_nat_cast_iff

      apply (is_efx_goods_nat_cast_iff _ _).mpr
  3. The complete allocation is EFX. automation

    The goal is now a bounded universal quantifier over the finite sets of agents and goods checking simple linear inequalities of natural numbers. The Lean kernel computes the valuations and sums directly (`decide +kernel`), confirming that every required inequality holds.

    line 9

      decide +kernel
is_efx_goods_nat_cast_iff
an allocation is envy-free up to any good (EFX) under real-valued additive utilities given by natural-number valuations if and only if for every pair of distinct agents i and j and every good g assigned to j, the total value agent i assigns to j's bundle is at most the total value i assigns to their own bundle plus the value of g to 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_allsource_three_pair_perturbed_strict_sanity :  (∀ i g, 0 < efx_allsource_three_pair_perturbed_values i g) ∧  (∀ (i j : Fin 4), i ≠ j →    efx_allsource_three_pair_perturbed_values i (![0,2,4,6] j) + efx_allsource_three_pair_perturbed_values i (![1,3,5,7] j) <      efx_allsource_three_pair_perturbed_values i (![0,2,4,6] i) + efx_allsource_three_pair_perturbed_values i (![1,3,5,7] i)) ∧  is_efx_goods (fun i g => (efx_allsource_three_pair_perturbed_values i g : ℝ)) ![(0 : Fin 4),0,1,3,2,0,1,2,3] := by  refine ⟨by decide +kernel, by decide +kernel, ?_⟩  apply (is_efx_goods_nat_cast_iff _ _).mpr  decide +kernel
See it in the graphDiscuss this resultChallenge it