efx_pair_binary_no_one_split_one_nat
For the explicit binary nine-good matrix, every one-split allocation allowing only the old pair indexed 1 to split fails a natural-number total-value EFX inequality.
Statement
theorem efx_pair_binary_no_one_split_one_nat : ∀ (a b c d e f : Fin 4), ¬ (∀ i j : Fin 4, i ≠ j → ∀ g : Fin 9, efx_pair_binary_one_split 1 a b c d e f g = j → (∑ h : Fin 9, if efx_pair_binary_one_split 1 a b c d e f h = j then efx_pair_binary_values i h else 0) ≤ (∑ h : Fin 9, if efx_pair_binary_one_split 1 a b c d e f h = i then efx_pair_binary_values i h else 0) + efx_pair_binary_values i g)
- 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 2
- 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…
- Used by 1
- 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…
The proof, explained
The theorem is proved by exhaustive finite verification. In this four-agent, nine-good instance, a one-split allocation with the pair at index 1 split is parameterized by six assignments $(a, b, c, d, e, f) \in (\mathrm{Fin}\;4)^6$, yielding $4^6 = 4096$ candidate allocations in total. By fixing the agent $a$ who receives the first pair and splitting into four cases, the problem reduces to checking $4^5 = 1024$ allocations per case. Because all domains are finite and valuations are natural numbers, Lean's kernel directly verifies by computation (`decide +kernel`) that every allocation fails the EFX condition.
Fix the agent $a \in \{0, 1, 2, 3\}$ allocated the first pair of goods.
We introduce the universally quantified variable $a$, reducing the goal to showing that no completion $(b, c, d, e, f)$ produces an EFX allocation.
intro aFor each of the four possible values of $a$, no assignment of the remaining bundles $(b, c, d, e, f)$ satisfies the EFX inequality. automation
We split into four cases corresponding to $a \in \{0, 1, 2, 3\}$ using `fin_cases a`. In each case, the remaining five parameters $(b, c, d, e, f) \in (\mathrm{Fin}\;4)^5$ determine $4^5 = 1024$ candidate allocations. For each allocation, verifying whether the EFX inequality holds for all pairs of distinct agents and all goods is a finite arithmetic check. Lean's kernel evaluates all cases directly (`decide +kernel`), confirming that every allocation fails the EFX condition.
fin_cases a <;> decide +kernel
- The proof relies on automated evaluation by the Lean kernel (`decide +kernel`), which exhaustively checks the finite search space without producing an explicit proof trace.
- Splitting into cases on $a$ via `fin_cases a` is an implementation detail to partition the 4096 possible allocations into four batches of 1024 to prevent kernel memory or timeout limits; mathematically, the entire verification is a single finite exhaustion.
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_one_nat : ∀ (a b c d e f : Fin 4), ¬ (∀ i j : Fin 4, i ≠ j → ∀ g : Fin 9, efx_pair_binary_one_split 1 a b c d e f g = j → (∑ h : Fin 9, if efx_pair_binary_one_split 1 a b c d e f h = j then efx_pair_binary_values i h else 0) ≤ (∑ h : Fin 9, if efx_pair_binary_one_split 1 a b c d e f h = i then efx_pair_binary_values i h else 0) + efx_pair_binary_values i g) := by intro a fin_cases a <;> decide +kernel