AFTD Auto-Formalizing Theoretical Domains

efx_nondeg_cycle_no_self

theoremverified

No agent has an inclusion-minimal self-champion set in the nondegenerate cycle instance.

Statement

theorem efx_nondeg_cycle_no_self (i : Fin 4) (T : Finset (Fin 13)) :
  ¬ efx_nondeg_cycle_champion i i T
Source
Nondegenerate three-source champion two-cycle exchange obstruction for OP-7, experiments 11481–11487; related arXiv:2002.05119 Section 3.1.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7

The proof, explained

The theorem states that no agent possesses a self-champion set in the nondegenerate cycle instance. The proof first uses `decide` to exhaustively check that none of the 16 candidate subbundles for any of the 4 agents satisfies the champion criteria against the agent itself. Assuming for contradiction that an arbitrary self-champion bundle exists, the completeness lemma `efx_min_cycle_subset_complete` expresses it as one of these 16 subbundles, immediately contradicting the exhaustive check.

  1. No subset parameterized by an agent i and a boolean vector b satisfies the champion criteria for agent i against itself. automation

    The local lemma `key` states that for every agent i ∈ Fin 4 and every boolean mask b : Fin 4 → Bool, the corresponding subset cannot simultaneously be contained in the candidate goods, exceed agent i's baseline value, and have every one-good removal bounded above by the baseline for all agents. Because the domains Fin 4 and Fin 4 → Bool are finite (with 4 and 16 elements respectively), this universal statement is decidable, and the `decide` tactic proves it by exhaustive evaluation.

    lines 3–8

      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_nondeg_cycle_baseline i < efx_nondeg_cycle_value i (efx_min_cycle_subset i b) ∧
            ∀ (k : Fin 4), ∀ g ∈ efx_min_cycle_subset i b,
              efx_nondeg_cycle_value k ((efx_min_cycle_subset i b).erase g) ≤ efx_nondeg_cycle_baseline k) := by
        decide
  2. There is no self-champion bundle T for any agent i.

    Assume for contradiction that agent i has a self-champion bundle T (hypothesis h). By definition, T is a subset of {12} ∪ efx_no_self_three_split_old(i). By `efx_min_cycle_subset_complete`, any such subset is equal to efx_min_cycle_subset(i, b) for some boolean mask b. Replacing T with efx_min_cycle_subset(i, b) shows that this subset satisfies all champion criteria, which directly contradicts `key i b`.

    lines 9–11

    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 {12} ∪ efx_no_self_three_split_old(j) can be represented as efx_min_cycle_subset(j, b) for some boolean selection vector 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_nondeg_cycle_no_self (i : Fin 4) (T : Finset (Fin 13)) :  ¬ efx_nondeg_cycle_champion i i T := by  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_nondeg_cycle_baseline i < efx_nondeg_cycle_value i (efx_min_cycle_subset i b) ∧        ∀ (k : Fin 4), ∀ g ∈ efx_min_cycle_subset i b,          efx_nondeg_cycle_value k ((efx_min_cycle_subset i b).erase g) ≤ efx_nondeg_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