AFTD Auto-Formalizing Theoretical Domains

efx_nondeg_cycle_full_efx

theoremverified

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

Statement

theorem efx_nondeg_cycle_full_efx :
  is_efx_goods (fun i g => (efx_nondeg_cycle_values i g : ℝ))
    ![(0 : Fin 4),0,0,0,1,3,2,2,2,3,2,1,1]
Source
Nondegenerate three-source champion two-cycle exchange obstruction for OP-7, experiments 11481–11487; related arXiv:2002.05119 Section 3.1.
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • efx_nondeg_cycle_valuesThe nondegenerate perturbation of the minimum-cardinality champion-cycle 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

The theorem asserts that the specified allocation of 13 goods among 4 agents is envy-free up to any good (EFX) for the valuation profile `efx_nondeg_cycle_values`. The proof first uses `is_efx_goods_nat_cast_iff` to reduce the real-valued EFX condition to an equivalent inequality on natural numbers. Because the allocation and valuations are fully explicit over finite domains, the resulting finite set of inequalities is verified by exhaustive computation using `decide`.

  1. The real-valued EFX condition is equivalent to a natural-number inequality for each pair of distinct agents and each allocated good.

    By rewriting with `is_efx_goods_nat_cast_iff`, the definition of EFX on real valuations—that agent i values bundle j minus any good g at most as much as bundle i—is converted into an equivalent condition on natural numbers: for every pair of distinct agents i and j and every good g in j's bundle, the sum of values of items in bundle j is at most the sum of values of items in bundle i plus the value of g.

    line 4

    uses is_efx_goods_nat_cast_iff

      rw [is_efx_goods_nat_cast_iff]
  2. The EFX inequality holds for every pair of distinct agents and every good in the other agent's bundle. automation

    With 4 agents and 13 goods, and with the allocation σ and the valuation matrix `efx_nondeg_cycle_values` explicitly defined, this universal statement over finite domains is decidable. The `decide` tactic checks all cases by direct arithmetic computation.

    line 5

      decide
is_efx_goods_nat_cast_iff
An allocation of goods with additive valuations given by natural numbers cast to the reals is EFX if and only if for all distinct agents i and j, and every item g in j's bundle, the total valuation of j's bundle by i is at most the valuation of i's own bundle by i plus the valuation of g by 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_nondeg_cycle_full_efx :  is_efx_goods (fun i g => (efx_nondeg_cycle_values i g : ℝ))    ![(0 : Fin 4),0,0,0,1,3,2,2,2,3,2,1,1] := by  rw [is_efx_goods_nat_cast_iff]  decide
See it in the graphDiscuss this resultChallenge it