AFTD Auto-Formalizing Theoretical Domains

efx_nondeg_cycle_minimum_cardinality

theoremverified

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

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.

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

    line 9

      decide

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