AFTD Auto-Formalizing Theoretical Domains

efx_no_self_three_split_perturbed_full

theoremverified

The nondegenerate perturbation admits a complete EFX allocation with owners (2,1,2,1,3,2,3,1,0,0,0,0,0).

Statement

theorem efx_no_self_three_split_perturbed_full :
  is_efx_goods (fun i g => (efx_no_self_three_split_perturbed_values i g : ℝ))
    ![(2 : Fin 4),1,2,1,3,2,3,1,0,0,0,0,0]
Source
Nondegenerate strengthening of the OP-7 no-self three-split obstruction, experiments 11492–11494; related perturbation argument arXiv:2002.05119 Lemma 1.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • efx_no_self_three_split_perturbed_valuesThe nondegenerate perturbation of the thirteen-good no-self three-split matrix.
  • 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

To show that the given allocation of 13 goods among 4 agents is envy-free up to any good (EFX), the proof first reduces the real-valued EFX condition to an equivalent inequality over the natural numbers using `is_efx_goods_nat_cast_iff`. Since all agent valuations and bundle assignments are explicitly given concrete numbers on finite sets, the resulting universal statement is decidable. The `decide` tactic then confirms the claim by exhaustive finite computation.

  1. The EFX condition is restated as an equivalent system of inequalities over natural numbers.

    Applying the lemma `is_efx_goods_nat_cast_iff` replaces the real-valued EFX definition with an equivalent integer inequality: for every pair of distinct agents i ≠ j and every good g allocated to agent j, the sum of agent i's valuations of the goods in j's bundle cannot exceed the sum of agent i's valuations of i's own bundle plus agent i's valuation of g.

    line 4

    uses is_efx_goods_nat_cast_iff

      rw [is_efx_goods_nat_cast_iff]
  2. The allocation satisfies the EFX inequalities for all pairs of agents and all goods. automation

    Because the set of 4 agents and 13 goods is finite and the valuation functions and bundle assignments are explicitly defined, the quantified condition is a finite decidable statement. The `decide` tactic checks every combination of agents and goods by direct arithmetic evaluation.

    line 5

      decide
is_efx_goods_nat_cast_iff
An allocation of goods with natural-number valuations (cast into ℝ) is EFX if and only if for all distinct agents i ≠ j and each good g in j's bundle, the sum of i's valuations for items in j's bundle is at most the sum of i's valuations for i's own bundle plus i's valuation of g.

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_no_self_three_split_perturbed_full :  is_efx_goods (fun i g => (efx_no_self_three_split_perturbed_values i g : ℝ))    ![(2 : Fin 4),1,2,1,3,2,3,1,0,0,0,0,0] := by  rw [is_efx_goods_nat_cast_iff]  decide
See it in the graphDiscuss this resultChallenge it