efx_min_cycle_no_self
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
- efx_min_cycle_championAn inclusion-minimal envied set T in the extension of old bundle j: agent i strictly prefers it and no agent prefers it after any deletion.
- 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_min_cycle_valuesThe four rows of the positive natural valuation matrix are (3,3,12,2,15,1,1,1,16,16,1,1,3), (3,14,1,3,3,12,16,1,1,1,1,16,3),…
- efx_min_cycle_valueNatural additive value of a set in the explicit matrix.
- efx_no_self_three_split_oldThe old partial allocation consists of four consecutive triples; good 12 is unallocated.
- efx_min_cycle_baselineThe initial utilities of the four agents.
- efx_min_cycle_partial_efxNatural EFX inequalities for a possibly partial four-bundle allocation.
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.
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.
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
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.
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 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.
- The key lemma is proved by `decide`, which exhaustively evaluates all 64 combinations (4 agents × 16 subsets) computationally rather than through an algebraic deduction.
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_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)