AFTD Auto-Formalizing Theoretical Domains

efx_no_self_three_split_full_efx

theoremverified

A complete EFX allocation of the matrix has owners (2,1,2,1,3,2,3,1,0,0,0,0,0).

Statement

theorem efx_no_self_three_split_full_efx :
  is_efx_goods (fun i g => (efx_no_self_three_split_values i g : ℝ))
    ![(2 : Fin 4),1,2,1,3,2,3,1,0,0,0,0,0]
Source
Positive equal-triple no-self-champion obstruction to the OP-7 two-bundle exchange route, experiments 11462–11471.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • efx_no_self_three_split_valuesThe positive natural-valued matrix with rows (3,23,43,1,38,30,35,1,33,2,47,20,3), (1,25,44,40,9,21,1,41,28,34,1,35,3),…
  • 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 rewrites the definition into an equivalent arithmetic inequality over the natural numbers. This eliminates subtraction by adding the value of the removed good to the right-hand side. Lean then checks the finitely many resulting inequalities by direct computation.

  1. It suffices to verify the EFX condition as a natural-number inequality without subtraction for each pair of distinct agents and each good.

    The definition of an EFX allocation requires that agent i values agent j's bundle with any item g removed at no more than i's own bundle. Rewriting with `is_efx_goods_nat_cast_iff` converts this real-valued condition into the equivalent natural-number condition: for all distinct i and j and every g in j's bundle, ∑_{h ∈ bundle(j)} v(i, h) ≤ ∑_{h ∈ bundle(i)} v(i, h) + v(i, g), eliminating set erasure and subtraction.

    line 4

    uses is_efx_goods_nat_cast_iff

      rw [is_efx_goods_nat_cast_iff]
  2. The candidate allocation satisfies the EFX inequalities for all agents and items. automation

    Because the number of agents (4) and goods (13) is finite and the valuation matrix and allocation vector are concrete, the universal quantification over all pairs of distinct agents and all assigned items is a decidable property. The `decide` tactic checks every case by finite evaluation and arithmetic computation.

    line 5

      decide
is_efx_goods_nat_cast_iff
For natural-number valuations, an allocation is EFX if and only if for all distinct agents i ≠ j and each item g in j's bundle, the sum of i's valuations for j's bundle is at most the sum of i's valuations for i's own bundle plus i's valuation for 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_full_efx :  is_efx_goods (fun i g => (efx_no_self_three_split_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