AFTD Auto-Formalizing Theoretical Domains

efx_min_cycle_two_cycle_classification

theoremverified

Every inclusion-minimal two-cycle is the pair of agents 0 and 1, with target-0 set {0,1,12} and target-1 set either {3,4,12} or {4,5,12}. The Boolean masks cover every subset by efx_min_cycle_subset_complete.

Statement

theorem efx_min_cycle_two_cycle_classification (i j : Fin 4) (b c : Fin 4 → Bool)
  (hij : i ≠ j)
  (hijc : efx_min_cycle_champion i j (efx_min_cycle_subset j b))
  (hjic : efx_min_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
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 8
  • efx_min_cycle_championAn inclusion-minimal envied set T in the extension of old bundle j: agent i strictly prefers it and no agent prefers it after any deletion.
  • 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_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

To classify all inclusion-minimal two-cycles in the envy graph, the proof first enumerates all possible directed champion configurations via exhaustive finite verification (`decide`), showing that only agents 0 and 1 can champion a bundle against anyone. Requiring mutual championship between two distinct agents eliminates all incompatible index pairs via integer arithmetic (`omega`), forcing the pair of agents to be {0, 1}. Finally, targeted finite evaluations determine the unique champion bundle agent 1 envies from agent 0 (namely {0, 1, 12}) and the two bundles agent 0 envies from agent 1 (namely {3, 4, 12} and {4, 5, 12}), proving the classification in each orientation.

  1. Any champion bundle for agent i against agent j must fall into one of six specific configurations, with i ∈ {0, 1}. automation

    Reverting the parameters and unfolding the definitions of `efx_min_cycle_champion` and `efx_min_cycle_subset` turns the claim into a finite check over all 4 × 4 × 2⁴ = 256 combinations of agents i, j and Boolean masks b. The `decide` tactic checks this finite kernel by direct computation, verifying that only six configurations satisfy the champion criteria.

    lines 10–12

      revert i j b
      unfold efx_min_cycle_champion efx_min_cycle_subset
      decide
  2. Both directed champion pairs (i, j) and (j, i) must each satisfy one of the six enumerated champion configurations.

    Applying `efx_min_cycle_two_cycle_classification_enum` to the hypothesis that i champions j with mask b, and to the hypothesis that j champions i with mask c, yields hypotheses `h1` and `h2`, each asserting a six-way disjunction of valid champion configurations.

    lines 20–21

    uses efx_min_cycle_two_cycle_classification_enum

      have h1 := efx_min_cycle_two_cycle_classification_enum i j b hijc
      have h2 := efx_min_cycle_two_cycle_classification_enum j i c hjic
  3. The pair of mutual champion agents (i, j) must be either (0, 1) or (1, 0). automation

    Case-splitting on the 6 alternatives in `h1` and the 6 alternatives in `h2` generates 36 subgoals. In every case where {i, j} ≠ {0, 1}, the index equalities are contradictory (for example, i = 0 ∧ j = 2 together with j = 0 ∧ i = 2 implies 0 = 2). The `omega` tactic dispatches all contradictory branches by Presburger arithmetic, leaving only the two consistent pairs (0, 1) and (1, 0).

    lines 22–24

      rcases h1 with ⟨a1, b1, _⟩ | ⟨a1, b1, _⟩ | ⟨a1, b1, _⟩ | ⟨a1, b1, _⟩ | ⟨a1, b1, _⟩ | ⟨a1, b1, _⟩ <;>
        rcases h2 with ⟨a2, b2, _⟩ | ⟨a2, b2, _⟩ | ⟨a2, b2, _⟩ | ⟨a2, b2, _⟩ | ⟨a2, b2, _⟩ | ⟨a2, b2, _⟩ <;>
        omega
  4. If agent 0 champions a subset of agent 1's goods, that subset is either {3, 4, 12} or {4, 5, 12}. automation

    After reverting the mask b and unfolding definitions, the statement is a decidable predicate over the 2⁴ = 16 candidate subsets of agent 1's goods. The `decide` tactic verifies by computation that only {3, 4, 12} and {4, 5, 12} satisfy the champion criteria.

    lines 30–32

      revert b
      unfold efx_min_cycle_champion efx_min_cycle_subset
      decide
  5. If agent 1 champions a subset of agent 0's goods, that subset is {0, 1, 12}. automation

    Similarly, reverting b and unfolding definitions reduces the claim to verifying the 16 candidate subsets of agent 0's goods. The `decide` tactic confirms by computation that {0, 1, 12} is the unique champion subset.

    lines 38–40

      revert b
      unfold efx_min_cycle_champion efx_min_cycle_subset
      decide
  6. The mutual champion agents are either i = 0, j = 1 or i = 1, j = 0.

    Applying `efx_min_cycle_two_cycle_classification_pair` to the distinctness hypothesis i ≠ j and the mutual championship hypotheses splits the theorem into two cases via `rcases`: i = 0, j = 1 and i = 1, j = 0.

    line 51

    uses efx_min_cycle_two_cycle_classification_pair

      rcases efx_min_cycle_two_cycle_classification_pair i j b c hij hijc hjic with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩
  7. When i = 0 and j = 1, the target bundle against agent 1 is {3, 4, 12} or {4, 5, 12}, and the target bundle against agent 0 is {0, 1, 12}.

    We select the left disjunct of the theorem with `Or.inl`. Trivial reflexivity proofs establish 0 = 0 and 1 = 1, while `efx_min_cycle_two_cycle_classification_target01` provides the target bundle against agent 1 and `efx_min_cycle_two_cycle_classification_target10` provides the target bundle against agent 0.

    lines 52–53

    uses Or.inl, efx_min_cycle_two_cycle_classification_target01, efx_min_cycle_two_cycle_classification_target10

      · exact Or.inl ⟨rfl, rfl, efx_min_cycle_two_cycle_classification_target01 b hijc,
          efx_min_cycle_two_cycle_classification_target10 c hjic⟩
  8. When i = 1 and j = 0, the target bundle against agent 0 is {0, 1, 12}, and the target bundle against agent 1 is {3, 4, 12} or {4, 5, 12}.

    We select the right disjunct of the theorem with `Or.inr`. Reflexivity establishes 1 = 1 and 0 = 0, while `efx_min_cycle_two_cycle_classification_target10` provides the target bundle against agent 0 and `efx_min_cycle_two_cycle_classification_target01` provides the target bundle against agent 1.

    lines 54–55

    uses Or.inr, efx_min_cycle_two_cycle_classification_target10, efx_min_cycle_two_cycle_classification_target01

      · exact Or.inr ⟨rfl, rfl, efx_min_cycle_two_cycle_classification_target10 b hijc,
          efx_min_cycle_two_cycle_classification_target01 c hjic⟩
efx_min_cycle_two_cycle_classification_enum
Any champion bundle for agent i against agent j must be one of six specific cases: agent 0 against agent 1 with {3,4,12} or {4,5,12}; agent 0 against agent 2 with {8,12}; agent 0 against agent 3 with {9,12}; agent 1 against agent 0 with {0,1,12}; agent 1 against agent 2 with {6,12}; or agent 1 against agent 3 with {11,12}.
efx_min_cycle_two_cycle_classification_pair
If two distinct agents i and j mutually champion subsets of each other's bundles, then the pair (i, j) must be either (0, 1) or (1, 0).
efx_min_cycle_two_cycle_classification_target01
If agent 0 champions a subset of agent 1's bundle, that subset must be either {3, 4, 12} or {4, 5, 12}.
efx_min_cycle_two_cycle_classification_target10
If agent 1 champions a subset of agent 0's bundle, that subset must be {0, 1, 12}.
Or.inl
If proposition a holds, then the disjunction a ∨ b holds.
Or.inr
If proposition b holds, then the disjunction a ∨ b holds.

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

/-- Exhaustive classification of the possible champions (a finite kernel check). -/private lemma efx_min_cycle_two_cycle_classification_enum (i j : Fin 4) (b : Fin 4 → Bool)    (h : efx_min_cycle_champion i j (efx_min_cycle_subset j b)) :    (i = 0 ∧ j = 1 ∧ (efx_min_cycle_subset j b = {3,4,12} ∨ efx_min_cycle_subset j b = {4,5,12})) ∨    (i = 0 ∧ j = 2 ∧ efx_min_cycle_subset j b = {8,12}) ∨    (i = 0 ∧ j = 3 ∧ efx_min_cycle_subset j b = {9,12}) ∨    (i = 1 ∧ j = 0 ∧ efx_min_cycle_subset j b = {0,1,12}) ∨    (i = 1 ∧ j = 2 ∧ efx_min_cycle_subset j b = {6,12}) ∨    (i = 1 ∧ j = 3 ∧ efx_min_cycle_subset j b = {11,12}) := by  revert i j b  unfold efx_min_cycle_champion efx_min_cycle_subset  decide/-- Two mutual champions can only be the pair of agents 0 and 1. -/private lemma efx_min_cycle_two_cycle_classification_pair (i j : Fin 4) (b c : Fin 4 → Bool)    (_hij : i ≠ j)    (hijc : efx_min_cycle_champion i j (efx_min_cycle_subset j b))    (hjic : efx_min_cycle_champion j i (efx_min_cycle_subset i c)) :    (i = 0 ∧ j = 1) ∨ (i = 1 ∧ j = 0) := by  have h1 := efx_min_cycle_two_cycle_classification_enum i j b hijc  have h2 := efx_min_cycle_two_cycle_classification_enum j i c hjic  rcases h1 with ⟨a1, b1, _⟩ | ⟨a1, b1, _⟩ | ⟨a1, b1, _⟩ | ⟨a1, b1, _⟩ | ⟨a1, b1, _⟩ | ⟨a1, b1, _⟩ <;>    rcases h2 with ⟨a2, b2, _⟩ | ⟨a2, b2, _⟩ | ⟨a2, b2, _⟩ | ⟨a2, b2, _⟩ | ⟨a2, b2, _⟩ | ⟨a2, b2, _⟩ <;>    omega/-- The only champions of agent 0 against old bundle 1 are `{3,4,12}` and `{4,5,12}`. -/private lemma efx_min_cycle_two_cycle_classification_target01 (b : Fin 4 → Bool)    (h : efx_min_cycle_champion 0 1 (efx_min_cycle_subset 1 b)) :    efx_min_cycle_subset 1 b = {3,4,12} ∨ efx_min_cycle_subset 1 b = {4,5,12} := by  revert b  unfold efx_min_cycle_champion efx_min_cycle_subset  decide/-- The only champion of agent 1 against old bundle 0 is `{0,1,12}`. -/private lemma efx_min_cycle_two_cycle_classification_target10 (b : Fin 4 → Bool)    (h : efx_min_cycle_champion 1 0 (efx_min_cycle_subset 0 b)) :    efx_min_cycle_subset 0 b = {0,1,12} := by  revert b  unfold efx_min_cycle_champion efx_min_cycle_subset  decidetheorem efx_min_cycle_two_cycle_classification (i j : Fin 4) (b c : Fin 4 → Bool)  (hij : i ≠ j)  (hijc : efx_min_cycle_champion i j (efx_min_cycle_subset j b))  (hjic : efx_min_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  rcases efx_min_cycle_two_cycle_classification_pair i j b c hij hijc hjic with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩  · exact Or.inl ⟨rfl, rfl, efx_min_cycle_two_cycle_classification_target01 b hijc,      efx_min_cycle_two_cycle_classification_target10 c hjic⟩  · exact Or.inr ⟨rfl, rfl, efx_min_cycle_two_cycle_classification_target10 b hijc,      efx_min_cycle_two_cycle_classification_target01 c hjic⟩
See it in the graphDiscuss this resultChallenge it