efx_nondeg_cycle_no_self
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
- efx_nondeg_cycle_championAn inclusion-minimal envied set for the nondegenerate cycle instance.
- efx_min_cycle_subsetEncode an arbitrary subset of the four goods in old bundle j plus good 12 using four Boolean flags.
- efx_min_cycle_subset_completeEvery subset of an old triple plus good 12 has a Boolean-mask encoding.
- 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.
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.
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.
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
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`.
uses
efx_min_cycle_subset_completeintro 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.
- The computational check in `key` is verified by the automated `decide` tactic, which exhaustively checks all 4 agents and all 16 boolean selection vectors (64 combinations in total) by kernel evaluation.
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_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)