AFTD Auto-Formalizing Theoretical Domains

efx_three_bonus_distinct_no_real

theoremverified

For the explicit positive four-agent seven-good instance, if an EFX allocation assigns its four old goods to distinct agents and its three bonuses to distinct agents, some agent has utility less than her old utility 38.

Statement

theorem efx_three_bonus_distinct_no_real (σ : Fin 7 → Fin 4)
    (hold : ∀ (a b : Fin 4), a ≠ b → σ (Fin.castAdd 3 a) ≠ σ (Fin.castAdd 3 b))
    (hbonus : ∀ (a b : Fin 3), a ≠ b → σ (Fin.natAdd 4 a) ≠ σ (Fin.natAdd 4 b))
    (hefx : is_efx_goods (fun i g => (efx_three_bonus_distinct_values i g : ℝ)) σ) :
    ∃ i : Fin 4, additive_valuation (fun g => (efx_three_bonus_distinct_values i g : ℝ)) (bundle_of σ i) < 38
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 8
  • efx_three_bonus_distinct_no_natNo assignment in the explicit matrix simultaneously keeps old and bonus recipients respectively distinct, satisfies EFX, and preserves…
  • 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…
  • 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…
  • additive_valuation_bundle_sum_iteAn additive value of an allocated bundle equals the sum over all goods of the item value when that good has the specified owner, and zero…
  • 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.
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.

The proof, explained

The theorem is proved by contradiction by reducing the real-valued claim to a previously established discrete impossibility theorem (`efx_three_bonus_distinct_no_nat`). Assuming that every agent receives at least utility 38, the allocation would satisfy all four conditions of discrete feasibility: distinct assignment of the four original goods, distinct assignment of the three bonus goods, utility at least 38 for all agents, and the EFX condition. Coercing the real valuations and EFX inequalities back to the natural numbers constructs a valid discrete instance, directly contradicting the discrete impossibility result.

  1. Assume for contradiction that every agent receives at least utility 38.

    We proceed by contradiction. Supposing the negation of the existential goal asserts that no agent receives strictly less than 38 utility; pushing the negation inward establishes that every agent i ∈ {0, 1, 2, 3} has additive valuation at least 38 for their assigned bundle.

    lines 6–8

      classical
      by_contra h
      push Not at h
  2. It suffices to show that σ satisfies the utility bound and the EFX property in natural numbers.

    The theorem `efx_three_bonus_distinct_no_nat` asserts that no allocation σ can be feasible over ℕ (that is, satisfy distinct old goods, distinct bonus goods, valuation at least 38 for each agent, and the discrete EFX condition). Applying this impossibility to derive False and providing the two given distinctness hypotheses (`hold` and `hbonus`) leaves two obligations: the natural-number valuation lower bound of 38 for each agent, and the natural-number EFX condition.

    lines 9–10

    uses efx_three_bonus_distinct_no_nat

      apply efx_three_bonus_distinct_no_nat σ
      refine ⟨hold, hbonus, ?_, ?_⟩
  3. Each agent receives a bundle with natural-number total value at least 38.

    For an arbitrary agent i, the contradiction hypothesis yields 38 ≤ additive_valuation ... . Rewriting the bundle valuation via `additive_valuation_bundle_sum_ite` produces a sum of conditional real values over all goods. Pushing the cast outside the sum reveals it as the real cast of the integer sum, allowing `exact_mod_cast` to cast the inequality 38 ≤ ... from ℝ back to ℕ.

    lines 11–20

    uses additive_valuation_bundle_sum_ite

      · intro i
        have hi := h i
        rw [additive_valuation_bundle_sum_ite] at hi
        have hcast :
            (∑ g, if σ g = i then (efx_three_bonus_distinct_values i g : ℝ) else 0)
              = ((∑ g, if σ g = i then efx_three_bonus_distinct_values i g else 0 : ℕ) : ℝ) := by
          push_cast
          rfl
        rw [hcast] at hi
        exact_mod_cast hi
  4. The allocation σ satisfies the EFX condition over the natural numbers.

    Given distinct agents i ≠ j and an item g assigned to j (so g ∈ bundle_of σ j), the equivalence lemma `is_efx_goods_nat_cast_iff` converts the real EFX assumption `hefx` into the equivalent natural-number bundle inequality. Specializing this inequality to i, j, and g, and converting the sums over bundles into conditional sums over all goods via `Finset.sum_filter` and the definition of `bundle_of`, completes the proof.

    lines 21–25

    uses is_efx_goods_nat_cast_iff, Finset.sum_filter

      · intro i j hij g hg
        have hh := (is_efx_goods_nat_cast_iff efx_three_bonus_distinct_values σ).mp hefx
        have hm : g ∈ bundle_of σ j := by simpa [bundle_of] using hg
        have := hh i j hij g hm
        simpa only [bundle_of, Finset.sum_filter] using this
efx_three_bonus_distinct_no_nat
No allocation of seven goods to four agents can simultaneously assign the four old goods distinctly, the three bonus goods distinctly, grant utility at least 38 to every agent, and satisfy the discrete EFX condition.
additive_valuation_bundle_sum_ite
The additive valuation of an agent's bundle equals the sum over all goods of the value of that good if assigned to the agent, and 0 otherwise.
is_efx_goods_nat_cast_iff
An allocation is EFX with respect to real-cast natural valuations if and only if for all distinct agents i ≠ j and any good g in j's bundle, the sum of i's natural-number values for j's bundle is at most the sum of i's values for i's bundle plus the value of g.
Finset.sum_filter
The sum of a function over the elements of a finite set satisfying a predicate p equals the sum over the entire set of the conditional expression: f(a) if p(a) holds, and 0 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

theorem efx_three_bonus_distinct_no_real (σ : Fin 7 → Fin 4)    (hold : ∀ (a b : Fin 4), a ≠ b → σ (Fin.castAdd 3 a) ≠ σ (Fin.castAdd 3 b))    (hbonus : ∀ (a b : Fin 3), a ≠ b → σ (Fin.natAdd 4 a) ≠ σ (Fin.natAdd 4 b))    (hefx : is_efx_goods (fun i g => (efx_three_bonus_distinct_values i g : ℝ)) σ) :    ∃ i : Fin 4, additive_valuation (fun g => (efx_three_bonus_distinct_values i g : ℝ)) (bundle_of σ i) < 38 := by  classical  by_contra h  push Not at h  apply efx_three_bonus_distinct_no_nat σ  refine ⟨hold, hbonus, ?_, ?_⟩  · intro i    have hi := h i    rw [additive_valuation_bundle_sum_ite] at hi    have hcast :        (∑ g, if σ g = i then (efx_three_bonus_distinct_values i g : ℝ) else 0)          = ((∑ g, if σ g = i then efx_three_bonus_distinct_values i g else 0 : ℕ) : ℝ) := by      push_cast      rfl    rw [hcast] at hi    exact_mod_cast hi  · intro i j hij g hg    have hh := (is_efx_goods_nat_cast_iff efx_three_bonus_distinct_values σ).mp hefx    have hm : g ∈ bundle_of σ j := by simpa [bundle_of] using hg    have := hh i j hij g hm    simpa only [bundle_of, Finset.sum_filter] using this
See it in the graphDiscuss this resultChallenge it