efx_nondeg_cycle_full_efx
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`.
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.
uses
is_efx_goods_nat_cast_iffrw [is_efx_goods_nat_cast_iff]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.
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.
- The exhaustive verification across all pairs of agents and all assigned goods is handled entirely by automated computation via `decide`.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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