efx_nondeg_cycle_sanity
All values are positive, the old allocation with good 12 unallocated is EFX with the stated baselines, and the only envy edges are 0→3 and 2→3; thus agents 0,1,2 are sources.
Statement
theorem efx_nondeg_cycle_sanity :
(∀ i g, 0 < efx_nondeg_cycle_values i g) ∧
(∀ i, efx_nondeg_cycle_value i (efx_no_self_three_split_old i) = efx_nondeg_cycle_baseline i) ∧
efx_partial_nat efx_nondeg_cycle_values ![(0 : Fin 5),0,0,1,1,1,2,2,2,3,3,3,4] ∧
(∀ i j : Fin 4, i ≠ j →
(efx_nondeg_cycle_value i (efx_no_self_three_split_old i) < efx_nondeg_cycle_value i (efx_no_self_three_split_old j) ↔
(i = 0 ∧ j = 3) ∨ (i = 2 ∧ j = 3)))- Source
- Nondegenerate three-source champion two-cycle exchange obstruction for OP-7, experiments 11481–11487; related arXiv:2002.05119 Section 3.1.
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- efx_nondeg_cycle_valuesThe nondegenerate perturbation of the minimum-cardinality champion-cycle matrix.
- efx_nondeg_cycle_valueThe natural additive value of a set in the nondegenerate cycle instance.
- efx_nondeg_cycle_baselineThe four old-bundle utilities in the nondegenerate cycle instance.
- efx_no_self_three_split_oldThe old partial allocation consists of four consecutive triples; good 12 is unallocated.
- efx_partial_natNatural EFX inequalities for a partial allocation whose last owner label denotes unallocated goods.
- efx_partial_nat_utilityNatural utility in a partial allocation whose last owner label denotes unallocated goods.
The proof, explained
The theorem verifies four sanity conditions for a 4-agent, 13-good fair division instance: all item valuations are strictly positive, each agent's initial 3-item bundle matches a specified baseline value, leaving good 12 unallocated produces an EFX partial allocation, and the only envy edges in the old allocation are 0 → 3 and 2 → 3. Because all agents and goods belong to finite index types and all valuations are concrete natural numbers, the assertion is a decidable proposition. Unfolding the definition of partial EFX exposes the bounded quantifiers so that Lean's decision procedure (`decide`) completes the proof by exhaustive computation.
The valuation profile has strictly positive entries, bundle values match their designated baselines, the partial allocation is EFX, and the only envy pairs are 0 envying 3 and 2 envying 3. automation
Unfolding the definitions of `efx_partial_nat` and `efx_partial_nat_utility` expands the partial EFX condition into explicit finite sums and inequalities over agents and goods. Because the agents and goods belong to finite sets (4 agents and 13 goods) and all valuations are concrete natural numbers, the entire proposition consists of decidable arithmetic checks. Lean's `decide` tactic verifies all inequalities, equalities, and logical equivalences by exhaustive finite evaluation.
unfold efx_partial_nat efx_partial_nat_utility decide
- The unfolding of `efx_partial_nat` and `efx_partial_nat_utility` is a formal prerequisite to expose finite bounded quantifiers for Lean's typeclass resolution, after which the entire arithmetic verification is discharged computationally by `decide` without producing step-by-step paper deductions.
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_sanity : (∀ i g, 0 < efx_nondeg_cycle_values i g) ∧ (∀ i, efx_nondeg_cycle_value i (efx_no_self_three_split_old i) = efx_nondeg_cycle_baseline i) ∧ efx_partial_nat efx_nondeg_cycle_values ![(0 : Fin 5),0,0,1,1,1,2,2,2,3,3,3,4] ∧ (∀ i j : Fin 4, i ≠ j → (efx_nondeg_cycle_value i (efx_no_self_three_split_old i) < efx_nondeg_cycle_value i (efx_no_self_three_split_old j) ↔ (i = 0 ∧ j = 3) ∨ (i = 2 ∧ j = 3))) := by unfold efx_partial_nat efx_partial_nat_utility decide