AFTD Auto-Formalizing Theoretical Domains

efx_three_bonus_distinct_no_nat

theoremverified

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
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.

  1. 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.

    lines 2–3

      have h0 : σ 0 = 0 ∨ σ 0 = 1 ∨ σ 0 = 2 ∨ σ 0 = 3 := by omega
      rcases h0 with h | h | h | h
  2. 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.

    line 4

    uses efx_three_bonus_distinct_no_0_nat

      · exact efx_three_bonus_distinct_no_0_nat σ h
  3. The 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.

    line 5

    uses efx_three_bonus_distinct_no_1_nat

      · exact efx_three_bonus_distinct_no_1_nat σ h
  4. The 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.

    line 6

    uses efx_three_bonus_distinct_no_2_nat

      · exact efx_three_bonus_distinct_no_2_nat σ h
  5. The 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.

    line 7

    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.

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

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
See it in the graphDiscuss this resultChallenge it