efx_nondeg_cycle_classification
The only inclusion-minimal champion two-cycle in the nondegenerate instance is 0↔1 with the two listed choices of sets.
Statement
theorem efx_nondeg_cycle_classification (i j : Fin 4) (b c : Fin 4 → Bool)
(hij : i ≠ j)
(hijc : efx_nondeg_cycle_champion i j (efx_min_cycle_subset j b))
(hjic : efx_nondeg_cycle_champion j i (efx_min_cycle_subset i c)) :
(i = 0 ∧ j = 1 ∧
(efx_min_cycle_subset j b = {3,4,12} ∨ efx_min_cycle_subset j b = {4,5,12}) ∧
efx_min_cycle_subset i c = {0,1,12}) ∨
(i = 1 ∧ j = 0 ∧ efx_min_cycle_subset j b = {0,1,12} ∧
(efx_min_cycle_subset i c = {3,4,12} ∨ efx_min_cycle_subset i c = {4,5,12}))- 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 7
- efx_nondeg_cycle_championAn inclusion-minimal envied set for the nondegenerate cycle instance.
- 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_min_cycle_subsetEncode an arbitrary subset of the four goods in old bundle j plus good 12 using four Boolean flags.
- efx_min_cycle_goodsFor each target old bundle, list its three goods followed by the unallocated good.
- efx_no_self_three_split_oldThe old partial allocation consists of four consecutive triples; good 12 is unallocated.
- Used by 1
- efx_nondeg_cycle_minimum_cardinalityThe three selected inclusion-minimal champion sets have size three, and no subset of at most two goods in either target extension is…
The proof, explained
The theorem classifies all mutual inclusion-minimal champion sets (two-cycles) between distinct agents in a 4-agent, 13-good fair division instance. Since each agent is associated with 4 candidate goods, there are only finitely many agent pairs and candidate subsets to consider. Because the champion condition is decidable, the classification lemma is proved by exhaustive computational verification (`decide`) over all 3,072 possible configurations. The main theorem then immediately specializes this key lemma to the assumed hypotheses.
The predicate `efx_nondeg_cycle_champion i j T` is decidable for all agents `i, j` and subsets `T`.
The champion condition is defined as the conjunction of three decidable properties: a subset inclusion of finite sets, a strict inequality of natural numbers, and a bounded universal quantifier over the finite type `Fin 4` and the finite set `T`. Lean's typeclass synthesis automatically constructs the decision procedure for this conjunction via `inferInstanceAs`.
instance efx_nondeg_cycle_classification_dec (i j : Fin 4) (T : Finset (Fin 13)) : Decidable (efx_nondeg_cycle_champion i j T) := inferInstanceAs (Decidable (_ ∧ _ ∧ _))Mutual champion subsets between distinct agents can only occur between agents 0 and 1 with the specified subsets. automation
The statement quantifies over the finite types `Fin 4` (for agents) and `Fin 4 → Bool` (for subset selection masks). Since each agent has 4 candidate goods, there are only 12 pairs of distinct agents and 16 possible subsets per agent, yielding 3,072 configurations. The `decide` tactic checks every configuration by finite evaluation and confirms that the implication holds universally.
lemma efx_nondeg_cycle_classification_key : ∀ (i j : Fin 4) (b c : Fin 4 → Bool), i ≠ j → efx_nondeg_cycle_champion i j (efx_min_cycle_subset j b) → efx_nondeg_cycle_champion j i (efx_min_cycle_subset i c) → (i = 0 ∧ j = 1 ∧ (efx_min_cycle_subset j b = {3,4,12} ∨ efx_min_cycle_subset j b = {4,5,12}) ∧ efx_min_cycle_subset i c = {0,1,12}) ∨ (i = 1 ∧ j = 0 ∧ efx_min_cycle_subset j b = {0,1,12} ∧ (efx_min_cycle_subset i c = {3,4,12} ∨ efx_min_cycle_subset i c = {4,5,12})) := by decide
The classification theorem holds for the given agents and subsets.
The main theorem specializes the universally quantified key lemma `efx_nondeg_cycle_classification_key` by applying it directly to the distinctness hypothesis `hij` and the two mutual champion hypotheses `hijc` and `hjic`.
uses
efx_nondeg_cycle_classification_keytheorem efx_nondeg_cycle_classification (i j : Fin 4) (b c : Fin 4 → Bool) (hij : i ≠ j) (hijc : efx_nondeg_cycle_champion i j (efx_min_cycle_subset j b)) (hjic : efx_nondeg_cycle_champion j i (efx_min_cycle_subset i c)) : (i = 0 ∧ j = 1 ∧ (efx_min_cycle_subset j b = {3,4,12} ∨ efx_min_cycle_subset j b = {4,5,12}) ∧ efx_min_cycle_subset i c = {0,1,12}) ∨ (i = 1 ∧ j = 0 ∧ efx_min_cycle_subset j b = {0,1,12} ∧ (efx_min_cycle_subset i c = {3,4,12} ∨ efx_min_cycle_subset i c = {4,5,12})) := efx_nondeg_cycle_classification_key i j b c hij hijc hjic
efx_nondeg_cycle_classification_key- For any distinct agents i and j and any selection masks b and c, if the selected subsets are mutual champions, then the agents are 0 and 1, with agent 1's set being {3, 4, 12} or {4, 5, 12} and agent 0's set being {0, 1, 12}.
- The key classification lemma is proved entirely by finite computational reflection via `decide`: Lean evaluates the proposition over all 3,072 combinations of distinct agents and subset selection masks rather than performing a pen-and-paper combinatorial deduction.
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.
instance efx_nondeg_cycle_classification_dec (i j : Fin 4) (T : Finset (Fin 13)) : Decidable (efx_nondeg_cycle_champion i j T) := inferInstanceAs (Decidable (_ ∧ _ ∧ _))lemma efx_nondeg_cycle_classification_key : ∀ (i j : Fin 4) (b c : Fin 4 → Bool), i ≠ j → efx_nondeg_cycle_champion i j (efx_min_cycle_subset j b) → efx_nondeg_cycle_champion j i (efx_min_cycle_subset i c) → (i = 0 ∧ j = 1 ∧ (efx_min_cycle_subset j b = {3,4,12} ∨ efx_min_cycle_subset j b = {4,5,12}) ∧ efx_min_cycle_subset i c = {0,1,12}) ∨ (i = 1 ∧ j = 0 ∧ efx_min_cycle_subset j b = {0,1,12} ∧ (efx_min_cycle_subset i c = {3,4,12} ∨ efx_min_cycle_subset i c = {4,5,12})) := by decidetheorem efx_nondeg_cycle_classification (i j : Fin 4) (b c : Fin 4 → Bool) (hij : i ≠ j) (hijc : efx_nondeg_cycle_champion i j (efx_min_cycle_subset j b)) (hjic : efx_nondeg_cycle_champion j i (efx_min_cycle_subset i c)) : (i = 0 ∧ j = 1 ∧ (efx_min_cycle_subset j b = {3,4,12} ∨ efx_min_cycle_subset j b = {4,5,12}) ∧ efx_min_cycle_subset i c = {0,1,12}) ∨ (i = 1 ∧ j = 0 ∧ efx_min_cycle_subset j b = {0,1,12} ∧ (efx_min_cycle_subset i c = {3,4,12} ∨ efx_min_cycle_subset i c = {4,5,12})) := efx_nondeg_cycle_classification_key i j b c hij hijc hjic