efx_pair_binary_no_one_split
For the explicit binary nine-good matrix cast to real values, no allocation encoded by the one-split construction is EFX.
Statement
theorem efx_pair_binary_no_one_split (r a b c d e f : Fin 4) : ¬ is_efx_goods (fun i g => (efx_pair_binary_values i g : ℝ)) (efx_pair_binary_one_split r a b c d e f)
- Source
- Structural helper for efx_four_agents_additive_exists (OP-7), campaign IN-404, 2026-11-01. Exact route obstruction from experiment 10993, not a counterexample to EFX existence; no novelty 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_pair_binary_valuesA positive four-agent nine-good valuation matrix: the first two rows are (2,1,2,1,2,1,2,1,2), and the last two rows are (1,2,1,2,1,2,1,2,2).
- efx_pair_binary_one_splitAssign the four old adjacent pairs among goods 0 through 7 and the new good 8 to arbitrary agents, except the pair indexed r may have its…
- efx_pair_binary_no_one_split_natFor the explicit binary nine-good matrix, every allocation encoded by the one-split construction fails a natural-number total-value EFX…
- 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
- efx_pair_binary_no_one_split_allocationFor the explicit binary nine-good matrix cast to real values, any allocation which preserves all but possibly one of the four old adjacent…
The proof, explained
The proof proceeds by contradiction, assuming that the one-split allocation is EFX under the real-cast binary valuation matrix. Using `is_efx_goods_nat_cast_iff`, this assumption is converted into an equivalent inequality on natural-number bundle sums. The proof then applies `efx_pair_binary_no_one_split_nat`, which establishes that no one-split allocation satisfies this EFX inequality when formulated using indicator sums over all goods. Finally, rewriting the bundle sums as indicator sums over all nine goods using `Finset.sum_filter` shows that the allocation satisfies that condition, reaching the desired contradiction.
Assuming the allocation is EFX, the valuations satisfy the natural-number EFX inequality on agent bundles.
We assume for contradiction that the one-split allocation is EFX under the real-cast valuations (line 6). Using `is_efx_goods_nat_cast_iff`, we convert the EFX condition on real numbers into an equivalent natural-number condition: for every pair of distinct agents i ≠ j and every good g in j's bundle, the sum of i's valuations on j's bundle is at most the sum on i's own bundle plus the value of g to agent i (line 7).
uses
is_efx_goods_nat_cast_iffintro h have hh := (is_efx_goods_nat_cast_iff efx_pair_binary_values (efx_pair_binary_one_split r a b c d e f)).mp h
It suffices to show that the allocation satisfies the indicator-sum formulation of the EFX condition.
We invoke `efx_pair_binary_no_one_split_nat`, which proves that no one-split allocation satisfies the EFX condition when written as sums over all goods with indicator conditionals. This reduces reaching a contradiction to proving that our allocation satisfies this indicator-sum inequality.
uses
efx_pair_binary_no_one_split_natapply efx_pair_binary_no_one_split_nat r a b c d e fThe allocation satisfies the indicator-sum formulation of the EFX condition.
To discharge the premise of `efx_pair_binary_no_one_split_nat`, we take distinct agents i ≠ j and an item g assigned to agent j (line 9). By definition of `bundle_of`, the assignment σ(g) = j means g belongs to j's bundle (line 10). Applying our natural-number EFX hypothesis hh gives the EFX inequality in terms of bundle sums (line 11). Finally, converting the sums over bundles into sums over all nine goods with indicator functions via `Finset.sum_filter` matches the target inequality and completes the proof (line 12).
uses
Finset.sum_filterintro i j hij g hg have hm : g ∈ bundle_of (efx_pair_binary_one_split r a b c d e f) j := by simpa [bundle_of] using hg have h' := hh i j hij g hm simpa only [bundle_of, Finset.sum_filter] using h'
is_efx_goods_nat_cast_iff- An allocation of goods is EFX for integer valuations cast to real numbers if and only if for all distinct agents i and j and every good g in j's bundle, the sum of i's values on j's bundle is at most the sum of i's values on i's own bundle plus i's value for g.
efx_pair_binary_no_one_split_nat- For any parameters defining a one-split allocation of nine goods among four agents, the allocation does not satisfy the discrete EFX condition formulated with indicator sums over all goods.
Finset.sum_filter- The sum of a function over elements of a finite set satisfying a predicate equals the sum over the entire finite set where terms not satisfying the predicate are replaced by zero.
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.
open Function Finsettheorem efx_pair_binary_no_one_split (r a b c d e f : Fin 4) : ¬ is_efx_goods (fun i g => (efx_pair_binary_values i g : ℝ)) (efx_pair_binary_one_split r a b c d e f) := by intro h have hh := (is_efx_goods_nat_cast_iff efx_pair_binary_values (efx_pair_binary_one_split r a b c d e f)).mp h apply efx_pair_binary_no_one_split_nat r a b c d e f intro i j hij g hg have hm : g ∈ bundle_of (efx_pair_binary_one_split r a b c d e f) j := by simpa [bundle_of] using hg have h' := hh i j hij g hm simpa only [bundle_of, Finset.sum_filter] using h'