AFTD Auto-Formalizing Theoretical Domains

efx_intact_obstruction_requires_split

theoremverified

Every EFX allocation of the explicit seven-good positive instance separates goods 0 and 1 or separates goods 2 and 3; hence it splits an old bundle of the stated six-good EFX allocation.

Statement

theorem efx_intact_obstruction_requires_split (σ : Fin 7 → Fin 4) (h01 : σ 0 = σ 1) (h23 : σ 2 = σ 3) :
    ¬ is_efx_goods (fun i g => (efx_intact_obstruction_values i g : ℝ)) σ
Source
Helper for efx_four_agents_additive_exists (OP-7), campaign session IN-404, 2026-11-01. Explicit route obstruction found in experiment 10980; it does not refute EFX existence and carries no research-level advance claim.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • efx_intact_obstruction_valuesThe explicit strictly positive four-agent seven-good valuation matrix used to test completion by keeping old bundles intact: rows…
  • efx_intact_obstruction_coarseAssign the four old bundles {5}, {0,1}, {2,3}, {4} and the new singleton {6} to arbitrary agents p(0),...,p(4), respectively; mergers and…
  • efx_intact_obstruction_no_coarseNo assignment of the four intact old bundles and new singleton in the explicit seven-good instance is EFX after casting its item values to…
  • is_efx_goodsAn allocation is EFX if for every pair of distinct agents i and j, and every good g in j's bundle, agent i values her own bundle at least…

The proof, explained

To show that any EFX allocation must separate either goods 0 and 1 or goods 2 and 3, the proof shows that any allocation σ keeping both pairs intact is equal to a coarse allocation efx_intact_obstruction_coarse p for a 5-item assignment p. It verifies this equality by case exhaustion on the seven goods using the two assumptions, then appeals to the obstruction theorem efx_intact_obstruction_no_coarse, which proves that no coarse allocation can be EFX on this instance.

  1. The allocation σ is identical to the coarse allocation efx_intact_obstruction_coarse p defined by p = ![σ 5, σ 0, σ 2, σ 4, σ 6].

    Because σ assigns goods 0 and 1 to the same agent (h01) and goods 2 and 3 to the same agent (h23), it leaves those two pairs intact and effectively assigns five items: good 5, the pair {0, 1}, the pair {2, 3}, good 4, and good 6. Defining p : Fin 5 → Fin 4 to record the recipient of each item, we apply function extensionality and split into seven cases for g ∈ Fin 7. In each case, simplifying using the definitions of p and efx_intact_obstruction_coarse together with the hypotheses h01 and h23 confirms that σ g = efx_intact_obstruction_coarse p g.

    lines 5–8

      let p : Fin 5 → Fin 4 := ![σ 5, σ 0, σ 2, σ 4, σ 6]
      have heq : σ = efx_intact_obstruction_coarse p := by
        funext g
        fin_cases g <;> simp [efx_intact_obstruction_coarse, p, h01, h23]
  2. The allocation σ is not an EFX allocation.

    Rewriting σ as efx_intact_obstruction_coarse p transforms the goal into showing that this coarse allocation is not EFX. The theorem efx_intact_obstruction_no_coarse asserts that no coarse allocation of this form can be EFX on the given seven-good instance, closing the proof.

    lines 9–10

    uses efx_intact_obstruction_no_coarse

      rw [heq]
      exact efx_intact_obstruction_no_coarse p
efx_intact_obstruction_no_coarse
For any assignment p of five bundles to four agents, the coarse allocation efx_intact_obstruction_coarse p is not an EFX allocation for the seven-good instance.

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

open Function Finsettheorem efx_intact_obstruction_requires_split (σ : Fin 7 → Fin 4) (h01 : σ 0 = σ 1) (h23 : σ 2 = σ 3) :    ¬ is_efx_goods (fun i g => (efx_intact_obstruction_values i g : ℝ)) σ := by  let p : Fin 5 → Fin 4 := ![σ 5, σ 0, σ 2, σ 4, σ 6]  have heq : σ = efx_intact_obstruction_coarse p := by    funext g    fin_cases g <;> simp [efx_intact_obstruction_coarse, p, h01, h23]  rw [heq]  exact efx_intact_obstruction_no_coarse p
See it in the graphDiscuss this resultChallenge it