efx_three_bonus_distinct_no_1_nat
No feasible allocation in the specified natural matrix gives old good 0 to agent 1.
Statement
theorem efx_three_bonus_distinct_no_1_nat (σ : Fin 7 → Fin 4) (h : σ 0 = 1) : ¬ 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 is proved by finite computational exhaustion. The allocation function $\sigma$ is rewritten as an explicit 7-tuple with its first coordinate fixed to agent 1 by assumption, and its remaining six coordinates are generalized to arbitrary agents. After unfolding the definitions of feasibility and the valuation matrix, the Lean kernel evaluates all $4^6 = 4096$ possible allocations with the `decide` tactic and confirms that none satisfy the feasibility requirements.
The allocation $\sigma$ is expressed explicitly as the vector $\langle 1, \sigma(1), \sigma(2), \sigma(3), \sigma(4), \sigma(5), \sigma(6)\rangle$.
By function extensionality, it suffices to verify that $\sigma$ and the explicit vector agree on all 7 goods. For good 0, $\sigma(0) = 1$ by the hypothesis $h$. For each of the remaining goods 1 through 6, both sides evaluate definitionally to $\sigma(i)$.
have hp : σ = ![1, σ 1, σ 2, σ 3, σ 4, σ 5, σ 6] := by funext i fin_cases i · exact h · rfl · rfl · rfl · rfl · rfl · rfl
The goal is reduced to showing that for all choices of agents $b, c, d, e, f, g \in \{0, 1, 2, 3\}$, the allocation $\langle 1, b, c, d, e, f, g\rangle$ is not feasible.
Rewriting $\sigma$ using this explicit vector and generalizing $\sigma(1), \dots, \sigma(6)$ to arbitrary agent variables $b, c, d, e, f, g$ rephrases the goal as a universal quantification over all assignments of the remaining six goods.
rw [hp] generalize σ 1 = b, σ 2 = c, σ 3 = d, σ 4 = e, σ 5 = f, σ 6 = g revert b c d e f g
No allocation assigning good 0 to agent 1 satisfies the feasibility conditions. automation
Unfolding the definitions of feasibility (`efx_three_bonus_distinct_feasible_nat`) and the valuation table (`efx_three_bonus_distinct_values`) turns the goal into a finite, decidable search over the $4^6 = 4096$ possible assignments to $(b, c, d, e, f, g)$. The `decide` tactic performs this check in the Lean kernel and confirms that none are feasible.
unfold efx_three_bonus_distinct_feasible_nat efx_three_bonus_distinct_values decide +kernel
- The proof relies on kernel computation (`decide +kernel`) rather than an analytic argument: Lean computes through all $4^6 = 4096$ possible allocations to verify that none satisfy the feasibility conditions.
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_1_nat (σ : Fin 7 → Fin 4) (h : σ 0 = 1) : ¬ efx_three_bonus_distinct_feasible_nat σ := by have hp : σ = ![1, σ 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