AFTD Auto-Formalizing Theoretical Domains

efx_min_cycle_full_efx

theoremverified

The instance has a complete EFX allocation with owners (0,0,0,0,1,3,2,2,2,3,2,1,1) that strictly improves all four original utilities; it preserves old triples 0 and 2 and splits old triples 1 and 3.

Statement

theorem efx_min_cycle_full_efx :
  is_efx_goods (fun i g => (efx_min_cycle_values i g : ℝ))
    ![(0 : Fin 4),0,0,0,1,3,2,2,2,3,2,1,1] ∧
  ∀ i : Fin 4, (efx_min_cycle_baseline i : ℝ) <
    additive_valuation (fun g => (efx_min_cycle_values i g : ℝ))
      (bundle_of ![(0 : Fin 4),0,0,0,1,3,2,2,2,3,2,1,1] i)
Source
Explicit two-split completion for the OP-7 minimum-cardinality two-cycle obstruction; experiments 11452 and 11453.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • efx_min_cycle_valuesThe four rows of the positive natural valuation matrix are (3,3,12,2,15,1,1,1,16,16,1,1,3), (3,14,1,3,3,12,16,1,1,1,1,16,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.
  • efx_min_cycle_baselineThe initial utilities of the four agents.
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.

The proof, explained

The proof splits the theorem into two independent verification goals: showing that the allocation is envy-free up to any good (EFX) and showing that every agent strictly improves upon their baseline utility. For the EFX property, the equivalence lemma `is_efx_goods_nat_cast_iff` reduces the real-valued condition to an equivalent finite condition on natural numbers, which is verified by computational reflection (`decide`). For the baseline improvements, the strict inequality is likewise established on natural numbers via `decide` and then cast to the reals.

  1. It suffices to show separately that the allocation is EFX and that each agent's bundle valuation strictly improves upon their baseline.

    The theorem asserts a conjunction of two properties: the EFX condition and the baseline improvement inequality for all four agents. Applying `constructor` splits this into two independent subgoals.

    line 7

      constructor
  2. The allocation is EFX with respect to the given valuation functions. automation

    Rewriting with `is_efx_goods_nat_cast_iff` replaces the real-valued EFX property with an equivalent inequality on the underlying natural-number valuations: for all distinct agents i ≠ j and each 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 i's own bundle plus i's value for g. Because the number of agents (4) and goods (13) is finite, `decide` verifies this condition by exhaustive computation.

    lines 8–9

    uses is_efx_goods_nat_cast_iff

      · rw [is_efx_goods_nat_cast_iff]
        decide
  3. For every agent, the natural-number sum of values in their assigned bundle strictly exceeds their baseline utility. automation

    We establish an auxiliary lemma `hh` asserting that for all agents i ∈ Fin 4, `efx_min_cycle_baseline i` is strictly less than the sum of `efx_min_cycle_values i g` over g in i's bundle. Since this is a finite quantified inequality over natural numbers, `decide` proves it by direct evaluation.

    lines 10–12

      · have hh : ∀ i : Fin 4, efx_min_cycle_baseline i <
          ∑ g ∈ bundle_of ![(0 : Fin 4),0,0,0,1,3,2,2,2,3,2,1,1] i, efx_min_cycle_values i g := by
          decide
  4. For every agent, the real-valued additive valuation of their bundle strictly exceeds their real-valued baseline utility.

    Fixing an arbitrary agent i, we unfold the definition of `additive_valuation` into a sum of real values. We then apply `exact_mod_cast hh i`, which casts the natural-number strict inequality proved in the auxiliary hypothesis `hh` to the real numbers, completing the proof.

    lines 13–15

    uses additive_valuation

        intro i
        simp only [additive_valuation]
        exact_mod_cast hh i
is_efx_goods_nat_cast_iff
An allocation with natural-number valuations is EFX when cast to the real numbers if and only if for all distinct agents i and j and every good g in j's bundle, agent i's total value for j's bundle is at most i's total value for their own bundle plus i's value for g.
additive_valuation
The additive valuation of a bundle of goods, defined as the sum of the individual values of the goods in the bundle.

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_min_cycle_full_efx :  is_efx_goods (fun i g => (efx_min_cycle_values i g : ℝ))    ![(0 : Fin 4),0,0,0,1,3,2,2,2,3,2,1,1] ∧  ∀ i : Fin 4, (efx_min_cycle_baseline i : ℝ) <    additive_valuation (fun g => (efx_min_cycle_values i g : ℝ))      (bundle_of ![(0 : Fin 4),0,0,0,1,3,2,2,2,3,2,1,1] i) := by  constructor  · rw [is_efx_goods_nat_cast_iff]    decide  · have hh : ∀ i : Fin 4, efx_min_cycle_baseline i <      ∑ g ∈ bundle_of ![(0 : Fin 4),0,0,0,1,3,2,2,2,3,2,1,1] i, efx_min_cycle_values i g := by      decide    intro i    simp only [additive_valuation]    exact_mod_cast hh i
See it in the graphDiscuss this resultChallenge it