efx_three_bonus_distinct_no_real
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.
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.
classical by_contra h push Not at h
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.
uses
efx_three_bonus_distinct_no_natapply efx_three_bonus_distinct_no_nat σ refine ⟨hold, hbonus, ?_, ?_⟩
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 ℕ.
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
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.
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.
- The core combinatorial impossibility—that no allocation can simultaneously assign old goods distinctly, bonus goods distinctly, guarantee every agent utility at least 38, and satisfy EFX—is encapsulated in `efx_three_bonus_distinct_no_nat`, which was proved by exhaustive computational search.
- The manipulation between `ℕ` and `ℝ` (using `push_cast` and `exact_mod_cast`) is standard proof-assistant bookkeeping to transfer statements between natural numbers and real numbers.
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_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