efx_three_bonus_distinct_no_nat
No assignment in the explicit matrix simultaneously keeps old and bonus recipients respectively distinct, satisfies EFX, and preserves every old utility.
Statement
theorem efx_three_bonus_distinct_no_nat (σ : Fin 7 → Fin 4) : ¬ 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 5
- efx_three_bonus_distinct_no_0_natNo feasible allocation in the specified natural matrix gives old good 0 to agent 0.
- efx_three_bonus_distinct_no_1_natNo feasible allocation in the specified natural matrix gives old good 0 to agent 1.
- efx_three_bonus_distinct_no_2_natNo feasible allocation in the specified natural matrix gives old good 0 to agent 2.
- efx_three_bonus_distinct_no_3_natNo feasible allocation in the specified natural matrix gives old good 0 to agent 3.
- 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…
- Used by 1
- efx_three_bonus_distinct_no_realFor the explicit positive four-agent seven-good instance, if an EFX allocation assigns its four old goods to distinct agents and its three…
The proof, explained
The proof proceeds by an exhaustive case analysis on which agent receives the first item. Since there are four agents, item 0 must be allocated to agent 0, 1, 2, or 3. For each of these four cases, a pre-established helper lemma proves that no assignment can satisfy the feasibility requirements (distinct recipients for old and bonus items, preservation of initial utility, and EFX). Because all four possibilities are infeasible, no such assignment exists.
It suffices to show that σ is not feasible in each of the four cases σ(0) = 0, σ(0) = 1, σ(0) = 2, and σ(0) = 3.
Because the assignment σ maps into the four-element set Fin 4, item 0 must be assigned to agent 0, 1, 2, or 3. Linear integer arithmetic over bounded types (omega) proves this four-way disjunction, and we split the goal into the corresponding four cases.
have h0 : σ 0 = 0 ∨ σ 0 = 1 ∨ σ 0 = 2 ∨ σ 0 = 3 := by omega rcases h0 with h | h | h | h
The assignment σ is not feasible when item 0 is assigned to agent 0.
Feasibility is directly ruled out in this case by the lemma efx_three_bonus_distinct_no_0_nat.
uses
efx_three_bonus_distinct_no_0_nat· exact efx_three_bonus_distinct_no_0_nat σ hThe assignment σ is not feasible when item 0 is assigned to agent 1.
Feasibility is directly ruled out in this case by the lemma efx_three_bonus_distinct_no_1_nat.
uses
efx_three_bonus_distinct_no_1_nat· exact efx_three_bonus_distinct_no_1_nat σ hThe assignment σ is not feasible when item 0 is assigned to agent 2.
Feasibility is directly ruled out in this case by the lemma efx_three_bonus_distinct_no_2_nat.
uses
efx_three_bonus_distinct_no_2_nat· exact efx_three_bonus_distinct_no_2_nat σ hThe assignment σ is not feasible when item 0 is assigned to agent 3, completing the proof.
Feasibility is directly ruled out in the final case by the lemma efx_three_bonus_distinct_no_3_nat.
uses
efx_three_bonus_distinct_no_3_nat· exact efx_three_bonus_distinct_no_3_nat σ h
efx_three_bonus_distinct_no_0_nat- No feasible assignment allocates item 0 to agent 0.
efx_three_bonus_distinct_no_1_nat- No feasible assignment allocates item 0 to agent 1.
efx_three_bonus_distinct_no_2_nat- No feasible assignment allocates item 0 to agent 2.
efx_three_bonus_distinct_no_3_nat- No feasible assignment allocates item 0 to agent 3.
- The computational search ruling out all candidate assignments for each choice of recipient for item 0 is delegated to the four helper lemmas efx_three_bonus_distinct_no_0_nat through efx_three_bonus_distinct_no_3_nat; this theorem only performs the top-level case analysis.
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_nat (σ : Fin 7 → Fin 4) : ¬ efx_three_bonus_distinct_feasible_nat σ := by have h0 : σ 0 = 0 ∨ σ 0 = 1 ∨ σ 0 = 2 ∨ σ 0 = 3 := by omega rcases h0 with h | h | h | h · exact efx_three_bonus_distinct_no_0_nat σ h · exact efx_three_bonus_distinct_no_1_nat σ h · exact efx_three_bonus_distinct_no_2_nat σ h · exact efx_three_bonus_distinct_no_3_nat σ h