AFTD Auto-Formalizing Theoretical Domains

efx_intact_obstruction_no_coarse

theoremverified

No assignment of the four intact old bundles and new singleton in the explicit seven-good instance is EFX after casting its item values to reals.

Statement

theorem efx_intact_obstruction_no_coarse (p : Fin 5 → Fin 4) :
    ¬ is_efx_goods (fun i g => (efx_intact_obstruction_values i g : ℝ)) (efx_intact_obstruction_coarse p)
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 6
  • is_efx_goods_nat_cast_iffFor natural-number item values, EFX after casting values to the reals is equivalent to all natural-number inequalities comparing each…
  • 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_coarse_natEvery assignment of the four intact old bundles and the new singleton in the explicit seven-good instance violates an EFX inequality,…
  • 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…
  • bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.
Used by 1

The proof, explained

The proof proceeds by contradiction. Assuming the coarse assignment is EFX with item values cast to the real numbers, it uses `is_efx_goods_nat_cast_iff` to translate this into the equivalent discrete EFX condition over natural numbers. It then applies `efx_intact_obstruction_no_coarse_nat`, an established impossibility result showing that no coarse assignment can satisfy this condition when written as sums with indicator functions. Finally, it verifies that the discrete EFX hypothesis implies this indicator-sum formulation by rewriting the bundle sums with `Finset.sum_filter`.

  1. Assuming the coarse assignment is EFX over the real numbers, it satisfies the discrete EFX inequality for natural-number valuations.

    We proceed by contradiction and assume that the coarse assignment `efx_intact_obstruction_coarse p` is EFX with values cast to ℝ (`intro h`). The lemma `is_efx_goods_nat_cast_iff` states that this real-valued EFX condition is equivalent to the natural-number EFX inequality: for all distinct agents i ≠ j and each item g in j's bundle, the sum of i's values for items in j's bundle is at most i's value for its own bundle plus the value of g. Applying the forward direction (`mp`) yields this discrete inequality as hypothesis `hh`.

    lines 5–6

    uses is_efx_goods_nat_cast_iff

      intro h
      have hh := (is_efx_goods_nat_cast_iff efx_intact_obstruction_values (efx_intact_obstruction_coarse p)).mp h
  2. It suffices to show that the coarse assignment satisfies the EFX condition expressed as conditional sums over all items.

    The lemma `efx_intact_obstruction_no_coarse_nat` asserts that no coarse assignment p can satisfy the integer EFX inequalities when bundle sums are expressed as conditional sums over all seven goods. Applying this lemma reduces our goal of deriving a contradiction (`False`) to verifying this conditional-sum inequality.

    line 7

    uses efx_intact_obstruction_no_coarse_nat

      apply efx_intact_obstruction_no_coarse_nat p
  3. The coarse assignment satisfies the conditional-sum EFX inequality, completing the contradiction.

    Fix distinct agents i and j and an item g assigned to j (`efx_intact_obstruction_coarse p g = j`). By definition of `bundle_of`, g belongs to agent j's bundle. Instantiating the discrete EFX hypothesis `hh` with these arguments gives the inequality between bundle sums. Finally, `Finset.sum_filter` rewrites the bundle sums into sums over all seven goods using indicator conditions (`if efx_intact_obstruction_coarse p h = ... then ... else 0`), which matches the target goal and closes the proof.

    lines 8–11

    uses Finset.sum_filter

      intro i j hij g hg
      have hg' : g ∈ bundle_of (efx_intact_obstruction_coarse p) j := by simpa [bundle_of] using hg
      have h' := hh i j hij g hg'
      simpa only [bundle_of, Finset.sum_filter] using h'
is_efx_goods_nat_cast_iff
An allocation of indivisible goods with natural-number valuations is EFX when item values are cast to real numbers if and only if for all distinct agents i ≠ j and each item g in j's bundle, agent i's valuation of j's bundle is at most i's valuation of its own bundle plus i's valuation of g.
efx_intact_obstruction_no_coarse_nat
No coarse assignment p of the five item bundles to the four agents satisfies the natural-number EFX inequalities expressed via indicator-filtered sums over all seven goods.
Finset.sum_filter
Summing a function over elements of a finite set that satisfy a predicate equals summing over the entire set with an if-then-else term that evaluates to the function value when the predicate holds and zero otherwise.

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_no_coarse (p : Fin 5 → Fin 4) :    ¬ is_efx_goods (fun i g => (efx_intact_obstruction_values i g : ℝ)) (efx_intact_obstruction_coarse p) := by  intro h  have hh := (is_efx_goods_nat_cast_iff efx_intact_obstruction_values (efx_intact_obstruction_coarse p)).mp h  apply efx_intact_obstruction_no_coarse_nat p  intro i j hij g hg  have hg' : g ∈ bundle_of (efx_intact_obstruction_coarse p) j := by simpa [bundle_of] using hg  have h' := hh i j hij g hg'  simpa only [bundle_of, Finset.sum_filter] using h'
See it in the graphDiscuss this resultChallenge it