AFTD Auto-Formalizing Theoretical Domains

efx_min_cycle_minimum_cardinality

theoremverified

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

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.

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

    line 9

    uses efx_min_cycle_champion

      dsimp [efx_min_cycle_champion]
  2. 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.

    line 10

      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.

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

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