efx_nondeg_cycle_minimum_cardinality
The three selected inclusion-minimal champion sets have size three, and no subset of at most two goods in either target extension is envied by any agent; thus these are minimum-cardinality champions.
Statement
theorem efx_nondeg_cycle_minimum_cardinality :
efx_nondeg_cycle_champion 0 1 {3,4,12} ∧
efx_nondeg_cycle_champion 0 1 {4,5,12} ∧
efx_nondeg_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_nondeg_cycle_value i {g,h} ≤ efx_nondeg_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_nondeg_cycle_value i {g,h} ≤ efx_nondeg_cycle_baseline i)- Source
- Nondegenerate minimum-cardinality champion check, experiment 11482; related arXiv:2002.05119 Section 3.1.
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- 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_no_self_three_split_oldThe old partial allocation consists of four consecutive triples; good 12 is unallocated.
- efx_nondeg_cycle_classificationThe only inclusion-minimal champion two-cycle in the nondegenerate instance is 0↔1 with the two listed choices of sets.
The proof, explained
The theorem verifies that three specific three-element bundles are champion sets (subsets whose value strictly exceeds an agent's baseline, but dropping any item leaves every agent at or below their baseline) and that no pair of goods in either extended bundle exceeds any agent's baseline. Because the agent set, good set, and extended bundles are all finite and the valuation functions and baselines are explicitly defined, the goal is a finite decidable property. The proof is completed in a single step by computational evaluation using the `decide` tactic.
The bundles {3, 4, 12} and {4, 5, 12} are champions for agent 0 against agent 1, {0, 1, 12} is a champion for agent 1 against agent 0, and no subset of size at most two in either agent's extended bundle exceeds any agent's baseline value. automation
All sets, agents, valuations, and baselines are defined explicitly over the finite types Fin 4 and Fin 13. Because all quantifiers and set operations are over finite sets and bounded integers, the whole conjunction is a decidable proposition. The `decide` tactic computes each valuation sum and verifies every condition by exhaustive evaluation.
decide
- The entire proof is executed via computational reflection by Lean's `decide` tactic, checking all conditions exhaustively on concrete finite data without generating intermediate proof terms.
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_nondeg_cycle_minimum_cardinality : efx_nondeg_cycle_champion 0 1 {3,4,12} ∧ efx_nondeg_cycle_champion 0 1 {4,5,12} ∧ efx_nondeg_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_nondeg_cycle_value i {g,h} ≤ efx_nondeg_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_nondeg_cycle_value i {g,h} ≤ efx_nondeg_cycle_baseline i) := by decide