efx_three_bonus_distinct_no_0_nat
No feasible allocation in the specified natural matrix gives old good 0 to agent 0.
Statement
theorem efx_three_bonus_distinct_no_0_nat (σ : Fin 7 → Fin 4) (h : σ 0 = 0) : ¬ 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 states that no feasible allocation in the specified natural valuation matrix can assign good 0 to agent 0. With good 0 fixed to agent 0, the remaining six goods have only 4^6 = 4096 possible agent assignments, a finite search space that the `decide` tactic exhaustively rules out by computation. The theorem then follows by expressing any allocation σ with σ(0) = 0 in explicit vector notation and applying this exhaustive non-feasibility result.
No allocation assigning item 0 to agent 0 can be feasible. automation
Unfolding the definition of `efx_three_bonus_distinct_feasible_nat` exposes the feasibility conditions: the first four items are assigned to distinct agents, the next three items are assigned to distinct agents, every agent receives a bundle with total value at least 38, and the allocation is envy-free up to any good (EFX). Since the remaining six items each have 4 possible owners, there are 4^6 = 4096 configurations. The `decide` tactic evaluates the decidable predicate for all 4096 cases by computation, confirming that none satisfy all conditions.
have key : ∀ a b c d e f : Fin 4, ¬ efx_three_bonus_distinct_feasible_nat ![0, a, b, c, d, e, f] := by unfold efx_three_bonus_distinct_feasible_nat decide
The allocation σ is identical to the explicit vector ![0, σ 1, σ 2, σ 3, σ 4, σ 5, σ 6].
By function extensionality (`funext`), two allocations are identical if they agree on each good i in Fin 7. A case split on the index i (`fin_cases`) produces seven cases. For item 0, the first vector entry is 0, which equals σ 0 by the assumption h. For items 1 through 6, the i-th vector entry evaluates definitionally to σ i.
have hσ : σ = ![0, σ 1, σ 2, σ 3, σ 4, σ 5, σ 6] := by funext i fin_cases i <;> simp [h]
σ is not feasible, completing the theorem.
Rewriting σ using its vector representation reduces the goal to ¬ efx_three_bonus_distinct_feasible_nat ![0, σ 1, ..., σ 6]. This matches the key lemma instantiated with the owners a = σ 1, ..., f = σ 6.
rw [hσ] exact key _ _ _ _ _ _
- The core non-feasibility step (line 6) is established by computational reflection: the `decide` tactic evaluates the decidable feasibility predicate across all 4^6 = 4096 possible assignments of the remaining six items, closing the goal via exhaustive search without intermediate proofs.
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_0_nat (σ : Fin 7 → Fin 4) (h : σ 0 = 0) : ¬ efx_three_bonus_distinct_feasible_nat σ := by -- With item 0 fixed to agent 0, the remaining six owners form a finite space; -- decide checks all 4^6 = 4096 cases against the feasible predicate. have key : ∀ a b c d e f : Fin 4, ¬ efx_three_bonus_distinct_feasible_nat ![0, a, b, c, d, e, f] := by unfold efx_three_bonus_distinct_feasible_nat decide have hσ : σ = ![0, σ 1, σ 2, σ 3, σ 4, σ 5, σ 6] := by funext i fin_cases i <;> simp [h] rw [hσ] exact key _ _ _ _ _ _