efx_min_cycle_two_cycle_classification
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.
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.
revert i j b unfold efx_min_cycle_champion efx_min_cycle_subset decide
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.
uses
efx_min_cycle_two_cycle_classification_enumhave 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
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).
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
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.
revert b unfold efx_min_cycle_champion efx_min_cycle_subset decide
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.
revert b unfold efx_min_cycle_champion efx_min_cycle_subset decide
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.
uses
efx_min_cycle_two_cycle_classification_pairrcases efx_min_cycle_two_cycle_classification_pair i j b c hij hijc hjic with ⟨rfl, rfl⟩ | ⟨rfl, rfl⟩
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.
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⟩
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.
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.
- The lemmas `efx_min_cycle_two_cycle_classification_enum`, `efx_min_cycle_two_cycle_classification_target01`, and `efx_min_cycle_two_cycle_classification_target10` are established entirely by Lean's computational kernel (`decide`), which exhaustively checks all finitely many agent pairs and subset masks against the valuation baselines.
- The step closing 36 cases in `efx_min_cycle_two_cycle_classification_pair` relies on the `omega` decision procedure to discard every pair of indices with incompatible equality constraints over `Fin 4`.
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.
/-- 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⟩