AFTD Auto-Formalizing Theoretical Domains

efx_min_cycle_no_self

theoremverified

No source self-champions, even when champion sets are allowed to be arbitrary inclusion-minimal envied subsets.

Statement

theorem efx_min_cycle_no_self (i : Fin 4) (T : Finset (Fin 13)) :
  ¬ efx_min_cycle_champion i i T
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

The proof, explained

The theorem establishes that no agent can self-champion, even with arbitrary inclusion-minimal envied sub-bundles. The proof first verifies by finite exhaustive evaluation (decide) that none of the 16 possible sub-bundles of an agent's candidate goods satisfies the champion conditions. It then uses efx_min_cycle_subset_complete to show that any assumed self-champion bundle T must be one of these 16 sub-bundles, producing an immediate contradiction.

  1. No Boolean-mask selection of an agent's candidate goods satisfies the self-champion conditions.

    For each agent i and each of the 16 Boolean selection masks b on the agent's candidate goods (the three initial goods plus good 12), the tactic decide exhaustively checks that efx_min_cycle_subset i b cannot simultaneously exceed agent i's baseline value while also having every single-good deletion stay at or below baseline for all agents.

    lines 4–9

      have key : ∀ (i : Fin 4) (b : Fin 4 → Bool),
          ¬ (efx_min_cycle_subset i b ⊆ insert 12 (efx_no_self_three_split_old i) ∧
            efx_min_cycle_baseline i < efx_min_cycle_value i (efx_min_cycle_subset i b) ∧
            ∀ (k : Fin 4), ∀ g ∈ efx_min_cycle_subset i b,
              efx_min_cycle_value k ((efx_min_cycle_subset i b).erase g) ≤ efx_min_cycle_baseline k) := by
        decide
  2. Any candidate self-champion bundle T corresponds to a Boolean mask b, contradicting the exhaustive evaluation.

    Assuming for contradiction that agent i champions itself with bundle T (h), the first component of h shows that T is a subset of agent i's initial goods plus good 12. By efx_min_cycle_subset_complete, T must equal efx_min_cycle_subset i b for some Boolean mask b. Substituting this equality into h contradicts the key lemma key applied to i and b.

    lines 10–12

    uses efx_min_cycle_subset_complete

      intro h
      obtain ⟨b, hb⟩ := efx_min_cycle_subset_complete i T h.1
      exact key i b (hb.symm ▸ h)
efx_min_cycle_subset_complete
Every subset T of agent j's candidate goods (their three initial goods together with good 12) is equal to efx_min_cycle_subset j b for some Boolean mask b : Fin 4 → Bool.

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_no_self (i : Fin 4) (T : Finset (Fin 13)) :  ¬ efx_min_cycle_champion i i T := by  -- Reduce to the 16 Boolean-mask encodings of subsets of each old triple plus good 12.  have key : ∀ (i : Fin 4) (b : Fin 4 → Bool),      ¬ (efx_min_cycle_subset i b ⊆ insert 12 (efx_no_self_three_split_old i) ∧        efx_min_cycle_baseline i < efx_min_cycle_value i (efx_min_cycle_subset i b) ∧        ∀ (k : Fin 4), ∀ g ∈ efx_min_cycle_subset i b,          efx_min_cycle_value k ((efx_min_cycle_subset i b).erase g) ≤ efx_min_cycle_baseline k) := by    decide  intro h  obtain ⟨b, hb⟩ := efx_min_cycle_subset_complete i T h.1  exact key i b (hb.symm ▸ h)
See it in the graphDiscuss this resultChallenge it