efx_min_cycle_sanity
Every value is positive; each agent values all old bundles equally, values each good of her own old bundle at least as much as good 12, and each old bundle has a good that some foreign agent values less than good 12. The old partial allocation is EFX.
Statement
theorem efx_min_cycle_sanity :
(∀ i g, 0 < efx_min_cycle_values i g) ∧
(∀ i j, efx_min_cycle_value i (efx_no_self_three_split_old j) = efx_min_cycle_baseline i) ∧
(∀ i g, g ∈ efx_no_self_three_split_old i → efx_min_cycle_values i 12 ≤ efx_min_cycle_values i g) ∧
(∀ j, ∃ i : Fin 4, i ≠ j ∧ ∃ g ∈ efx_no_self_three_split_old j, efx_min_cycle_values i g < efx_min_cycle_values i 12) ∧
efx_min_cycle_partial_efx efx_no_self_three_split_old- Source
- Minimum-cardinality champion-cycle swap obstruction for OP-7, experiments 11442–11449; comparison with arXiv:2002.05119 Section 3.1.
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- 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),…
- efx_min_cycle_valueNatural additive value of a set in the explicit matrix.
- efx_no_self_three_split_oldThe old partial allocation consists of four consecutive triples; good 12 is unallocated.
- efx_min_cycle_baselineThe initial utilities of the four agents.
- efx_min_cycle_partial_efxNatural EFX inequalities for a possibly partial four-bundle allocation.
The proof, explained
The theorem verifies five sanity properties for an explicit fair-division instance with four agents and thirteen goods, where four bundles of three goods are allocated and good 12 remains unallocated. The properties state that all valuations are positive, every agent values all four bundles equally at her baseline value, each agent values every good in her own bundle at least as much as good 12, each bundle contains a good that an outside agent values strictly less than good 12, and the allocation is EFX. Because the agent and item sets are finite, the proof splits the conjunction into five subgoals and resolves each by exhaustive case analysis and direct arithmetic evaluation.
The proof reduces to verifying the five conjuncts independently.
The goal is a conjunction of five statements. Splitting the conjunction yields five separate subgoals corresponding to the five sanity conditions.
refine ⟨?_, ?_, ?_, ?_, ?_⟩Every agent assigns a strictly positive value to every good. automation
Introducing an arbitrary agent i and good g, exhaustive case analysis on i ∈ {0, 1, 2, 3} and g ∈ {0, ..., 12} produces 52 cases. In each case, Lean evaluates 0 < v_i(g) from the concrete valuation matrix by direct arithmetic computation.
· intro i g fin_cases i <;> fin_cases g <;> decide
Each agent values all four initial bundles equally, matching that agent's baseline value. automation
Introducing an agent i and bundle index j, case exhaustion generates all 16 pairs (i, j). For each pair, the sum of values of the goods in bundle A(j) is computed and confirmed to equal the baseline value b_i (18 for agents 0, 1, and 3, and 36 for agent 2).
· intro i j fin_cases i <;> fin_cases j <;> decide
Every agent values each good in her own bundle at least as much as good 12. automation
Assuming g ∈ A(i), case exhaustion enumerates all 52 pairs (i, g). Whenever g ∉ A(i), the membership hypothesis reduces to False and closes the branch. Whenever g ∈ A(i), simplifying the valuation matrix definitions confirms the inequality v_i(12) ≤ v_i(g).
· intro i g hg fin_cases i <;> fin_cases g <;> simp_all [efx_no_self_three_split_old, efx_min_cycle_values]
For every bundle, some other agent values an item in that bundle strictly less than good 12. automation
For each bundle j ∈ {0, 1, 2, 3}, the existential condition asks for an outside agent i ≠ j and an item g ∈ A(j) such that v_i(g) < v_i(12). Because the domains are finite, the decision procedure exhaustively searches for and verifies such a witness pair.
· intro j fin_cases j <;> decide
The initial allocation is envy-free up to any good (EFX). automation
By definition, the allocation is EFX if for all distinct agents i ≠ j and every good g ∈ A(j), v_i(A(j) \ {g}) ≤ v_i(A(i)). Case analysis enumerates all tuples (i, j, g); invalid tuples with i = j or g ∉ A(j) are dismissed by the hypotheses, and for all valid tuples the bundle sums are evaluated and shown to satisfy the inequality.
· intro i j hij g hg fin_cases i <;> fin_cases j <;> fin_cases g <;> simp_all [efx_min_cycle_value, efx_no_self_three_split_old, efx_min_cycle_values] <;> decide
- Every step of the proof is verified by computational reflection and finite case exhaustion over the finite sets Fin 4 and Fin 13.
- In the fourth conjunct (Step 5), the existential witnesses are found and verified automatically by finite search within the decision procedure.
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_min_cycle_sanity : (∀ i g, 0 < efx_min_cycle_values i g) ∧ (∀ i j, efx_min_cycle_value i (efx_no_self_three_split_old j) = efx_min_cycle_baseline i) ∧ (∀ i g, g ∈ efx_no_self_three_split_old i → efx_min_cycle_values i 12 ≤ efx_min_cycle_values i g) ∧ (∀ j, ∃ i : Fin 4, i ≠ j ∧ ∃ g ∈ efx_no_self_three_split_old j, efx_min_cycle_values i g < efx_min_cycle_values i 12) ∧ efx_min_cycle_partial_efx efx_no_self_three_split_old := by refine ⟨?_, ?_, ?_, ?_, ?_⟩ · intro i g fin_cases i <;> fin_cases g <;> decide · intro i j fin_cases i <;> fin_cases j <;> decide · intro i g hg fin_cases i <;> fin_cases g <;> simp_all [efx_no_self_three_split_old, efx_min_cycle_values] · intro j fin_cases j <;> decide · intro i j hij g hg fin_cases i <;> fin_cases j <;> fin_cases g <;> simp_all [efx_min_cycle_value, efx_no_self_three_split_old, efx_min_cycle_values] <;> decide