AFTD Auto-Formalizing Theoretical Domains

efx_nondeg_cycle_classification

theoremverified

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
Used by 1

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.

  1. 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`.

    lines 1–3

    instance efx_nondeg_cycle_classification_dec (i j : Fin 4) (T : Finset (Fin 13)) :
        Decidable (efx_nondeg_cycle_champion i j T) :=
      inferInstanceAs (Decidable (_ ∧ _ ∧ _))
  2. 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.

    lines 5–15

    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
  3. 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`.

    lines 17–25

    uses efx_nondeg_cycle_classification_key

    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})) := 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}.

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

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
See it in the graphDiscuss this resultChallenge it