efx_min_cycle_minimum_cardinality
The three listed sets are inclusion-minimal envied sets with the stated champions, while every subset of at most two goods in the two relevant extensions has value at most the observer’s baseline. Consequently all three are minimum-cardinality champion sets.
Statement
theorem efx_min_cycle_minimum_cardinality :
efx_min_cycle_champion 0 1 {3,4,12} ∧
efx_min_cycle_champion 0 1 {4,5,12} ∧
efx_min_cycle_champion 1 0 {0,1,12} ∧
(∀ (i : Fin 4) (g h : Fin 13), g ∈ insert 12 (efx_no_self_three_split_old 0) → h ∈ insert 12 (efx_no_self_three_split_old 0) →
efx_min_cycle_value i {g,h} ≤ efx_min_cycle_baseline i) ∧
(∀ (i : Fin 4) (g h : Fin 13), g ∈ insert 12 (efx_no_self_three_split_old 1) → h ∈ insert 12 (efx_no_self_three_split_old 1) →
efx_min_cycle_value i {g,h} ≤ efx_min_cycle_baseline i)- 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 6
- 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_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 asserts that three specific 3-item bundles are inclusion-minimal envied sets (champions) between the first two agents, and that every bundle of at most two items from the relevant extended bundles has value at most the observer's baseline, guaranteeing that these champion sets have minimum possible cardinality. The proof proceeds by unfolding the definition of a champion set and delegating the entire verification to Lean's decision procedure (`decide`), which checks all subset inclusions and arithmetic inequalities by direct finite computation.
The goal is expanded by expressing the champion condition in terms of explicit valuations, subset inclusions, and single-item deletions.
Unfolding the definition `efx_min_cycle_champion` replaces each champion assertion with three explicit conditions: the set T must be a subset of the target agent's bundle with item 12 adjoined, the observing agent's valuation of T must strictly exceed their baseline, and removing any element from T must leave a bundle whose valuation is at most the baseline for every agent.
uses
efx_min_cycle_championdsimp [efx_min_cycle_champion]The three candidate sets are inclusion-minimal envied sets, and all two-element subsets of the extended bundles are bounded by the baselines. automation
Because all domains are finite (4 agents and 13 goods) and all operations—finite set membership, subset testing, summation of additive valuations, and comparisons in ℕ—are computable, the entire goal is a decidable proposition. The `decide` tactic evaluates all cases exhaustively and closes the goal.
decide
efx_min_cycle_champion- A set of goods T is a champion set for agent i against agent j if T is contained in j's bundle plus item 12, agent i strictly envies T over their baseline, and removing any item from T reduces its value to at most the baseline for every agent.
- The entire verification is carried out by computational reflection (`decide`) over finite domains, evaluating the explicit numerical values and set operations rather than presenting an analytical paper proof.
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_minimum_cardinality : efx_min_cycle_champion 0 1 {3,4,12} ∧ efx_min_cycle_champion 0 1 {4,5,12} ∧ efx_min_cycle_champion 1 0 {0,1,12} ∧ (∀ (i : Fin 4) (g h : Fin 13), g ∈ insert 12 (efx_no_self_three_split_old 0) → h ∈ insert 12 (efx_no_self_three_split_old 0) → efx_min_cycle_value i {g,h} ≤ efx_min_cycle_baseline i) ∧ (∀ (i : Fin 4) (g h : Fin 13), g ∈ insert 12 (efx_no_self_three_split_old 1) → h ∈ insert 12 (efx_no_self_three_split_old 1) → efx_min_cycle_value i {g,h} ≤ efx_min_cycle_baseline i) := by dsimp [efx_min_cycle_champion] decide