efx_allsource_pair_no_self
The envy-free partial allocation has no self champions for the unallocated good.
Statement
theorem efx_allsource_pair_no_self (i : Fin 4) (T : Finset (Fin 9))
(hT : T ⊆ insert 8 ({![0,2,4,6] i, ![1,3,5,7] i} : Finset (Fin 9)))
(hprefer : efx_allsource_pair_baseline i < ∑ g ∈ T, efx_allsource_pair_values i g) :
∃ (j : Fin 4) (g : Fin 9), g ∈ T ∧ efx_allsource_pair_baseline j <
∑ h ∈ T.erase g, efx_allsource_pair_values j h- Source
- Three-valued all-source no-self two-split EFX obstruction for OP-7; experiments 11638–11642.
- Verified
- 02 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- efx_allsource_pair_valuesThree-valued positive four-agent values for four old pairs and one charity good.
- efx_allsource_pair_baselineThe four starting utilities.
The proof, explained
The theorem states that in a specific fair division instance with 4 agents and 9 goods, whenever an agent i strictly prefers a bundle T ⊆ {8, 2i, 2i+1} to their baseline, some agent j strictly prefers T \ {g} to their baseline for some item g ∈ T. Because there are only 4 agents and each candidate bundle is a subset of a 3-element set of goods, the problem reduces to checking at most 32 cases. Reverting the parameters yields a closed sentence over finite domains, which Lean's `decide` tactic verifies by exhaustive computation.
Every candidate pair of agent i and bundle T is verified to admit a champion agent j and good g. automation
The assertion is purely finite: the agent i belongs to the 4-element set `Fin 4`, and T ranges over the power set of the 3-element set `{8, ![0,2,4,6] i, ![1,3,5,7] i}`, for a total of at most 4 × 2³ = 32 possible configurations. Reverting i and T presents the statement as a closed, universally quantified proposition over finite types, which Lean's `decide` tactic verifies by exhaustive computation.
revert i T decide
- The proof operates entirely via the `decide` tactic, which evaluates the finite decision problem by computational reflection in the Lean kernel.
- The strict preference hypothesis `efx_allsource_pair_baseline i < ∑ g ∈ T, efx_allsource_pair_values i g` is satisfied only when T is the full 3-element set `{8, ![0,2,4,6] i, ![1,3,5,7] i}`; in each of these four cases, exhaustive search finds a witness agent j strictly distinct from i, confirming there are no self-champions.
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_allsource_pair_no_self (i : Fin 4) (T : Finset (Fin 9)) (hT : T ⊆ insert 8 ({![0,2,4,6] i, ![1,3,5,7] i} : Finset (Fin 9))) (hprefer : efx_allsource_pair_baseline i < ∑ g ∈ T, efx_allsource_pair_values i g) : ∃ (j : Fin 4) (g : Fin 9), g ∈ T ∧ efx_allsource_pair_baseline j < ∑ h ∈ T.erase g, efx_allsource_pair_values j h := by revert i T decide