efx_three_bonus_distinct_no_3_nat
No feasible allocation in the specified natural matrix gives old good 0 to agent 3.
Statement
theorem efx_three_bonus_distinct_no_3_nat (σ : Fin 7 → Fin 4) (h : σ 0 = 3) : ¬ efx_three_bonus_distinct_feasible_nat σ- Source
- Finite obstruction to the distinct-recipient exchange route for OP-7, experiments 11403, 11405 and 11406.
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- efx_three_bonus_distinct_feasible_natA seven-good allocation gives the four old goods to distinct agents and the three bonuses to distinct agents, gives each agent natural…
- efx_three_bonus_distinct_valuesThe natural-valued four-agent, seven-good matrix whose rows are (38,36,58,56,1,1,17), (18,38,54,36,1,1,17), (18,38,38,36,17,1,1), and…
- Used by 1
- efx_three_bonus_distinct_no_natNo assignment in the explicit matrix simultaneously keeps old and bonus recipients respectively distinct, satisfies EFX, and preserves…
The proof, explained
The theorem establishes that in the specified fair division setting with 4 agents and 7 goods, no feasible allocation can assign good 0 to agent 3. Using the hypothesis σ 0 = 3, the allocation σ is rewritten as an explicit 7-tuple with its first coordinate fixed to 3. The remaining six coordinates are generalized to arbitrary choices in Fin 4, reducing the goal to a universal statement over all 4^6 = 4096 possible completions. Lean's kernel decision procedure then exhaustively verifies that none of these allocations satisfies all feasibility conditions.
The allocation function σ is equal to the explicit vector (3, σ 1, σ 2, σ 3, σ 4, σ 5, σ 6).
By function extensionality, two assignments on the seven-element domain Fin 7 are identical if they agree on every element. A case split on the index i leaves seven cases: for good 0, the hypothesis h gives σ 0 = 3; for goods 1 through 6, both sides are identical by definition.
have hp : σ = ![3, σ 1, σ 2, σ 3, σ 4, σ 5, σ 6] := by funext i fin_cases i · exact h · rfl · rfl · rfl · rfl · rfl · rfl
It suffices to show that no allocation of the form (3, b, c, d, e, f, g) is feasible for any choice of b, c, d, e, f, g ∈ Fin 4.
Substituting the explicit vector form for σ, the specific values σ 1 through σ 6 are replaced by arbitrary variables b, c, d, e, f, g in Fin 4 and quantified universally. This reduces the problem to showing that fixing good 0 to agent 3 precludes feasibility regardless of how the remaining six goods are distributed.
rw [hp] generalize σ 1 = b, σ 2 = c, σ 3 = d, σ 4 = e, σ 5 = f, σ 6 = g revert b c d e f g
No allocation with good 0 assigned to agent 3 satisfies the feasibility conditions. automation
Expanding the definitions of feasibility and the valuation matrix yields a bounded first-order sentence over the finite set (Fin 4)^6 of size 4^6 = 4096. Lean's kernel decision procedure (`decide +kernel`) evaluates the predicate exhaustively over all 4096 combinations, verifying that each one violates at least one feasibility constraint (injectivity on base or bonus goods, the minimum utility threshold of 38, or the EFX condition).
unfold efx_three_bonus_distinct_feasible_nat efx_three_bonus_distinct_values decide +kernel
- The final step relies on Lean's kernel decision procedure (`decide +kernel`), which finishes the proof by exhaustive computational verification over all 4^6 = 4096 candidate assignments for the remaining six goods.
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_three_bonus_distinct_no_3_nat (σ : Fin 7 → Fin 4) (h : σ 0 = 3) : ¬ efx_three_bonus_distinct_feasible_nat σ := by have hp : σ = ![3, σ 1, σ 2, σ 3, σ 4, σ 5, σ 6] := by funext i fin_cases i · exact h · rfl · rfl · rfl · rfl · rfl · rfl rw [hp] generalize σ 1 = b, σ 2 = c, σ 3 = d, σ 4 = e, σ 5 = f, σ 6 = g revert b c d e f g unfold efx_three_bonus_distinct_feasible_nat efx_three_bonus_distinct_values decide +kernel