efx_pair_binary_no_one_split_three_nat
For the explicit binary nine-good matrix, every one-split allocation allowing only the old pair indexed 3 to split fails a natural-number total-value EFX inequality.
Statement
theorem efx_pair_binary_no_one_split_three_nat : ∀ (a b c d e f : Fin 4), ¬ (∀ i j : Fin 4, i ≠ j → ∀ g : Fin 9, efx_pair_binary_one_split 3 a b c d e f g = j → (∑ h : Fin 9, if efx_pair_binary_one_split 3 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 3 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 proof establishes by exhaustive finite search that no one-split allocation splitting the fourth pair of goods can be envy-free up to any good (EFX) under the given valuation matrix. Introducing the first agent parameter and splitting into cases for its four possible values divides the $4^6 = 4096$ candidate allocations into four manageable subgoals. Lean's kernel decision procedure (`decide +kernel`) then exhaustively checks all remaining parameter combinations, verifying that every allocation fails the EFX inequality.
Fix an arbitrary agent $a \in \{0, 1, 2, 3\}$ receiving the first pair of goods.
We introduce the variable $a$, leaving the remaining agent assignments $b, c, d, e, f$ to be checked for each choice of $a$.
intro aFor each value $a \in \{0, 1, 2, 3\}$, no assignment of the remaining agents $b, c, d, e, f$ produces an EFX allocation. automation
The tactic `fin_cases a` splits the problem into four subgoals ($a = 0, 1, 2, 3$). In each branch, the goal is a universally quantified statement over the finite domain $(Fin\ 4)^5$. The `decide +kernel` tactic evaluates the finite proposition by exhaustive computation in the Lean kernel, verifying that every assignment violates the EFX condition for at least one pair of agents and one good.
fin_cases a <;> decide +kernel
- The proof is entirely computational: because the agents and goods are drawn from finite types (Fin 4 and Fin 9), the question of whether an allocation satisfies EFX is decidable. The initial case split on `a` divides the search space of $4^6 = 4096$ candidate allocations into four batches of $4^5 = 1024$, which are evaluated directly by Lean's kernel via `decide +kernel`.
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_three_nat : ∀ (a b c d e f : Fin 4), ¬ (∀ i j : Fin 4, i ≠ j → ∀ g : Fin 9, efx_pair_binary_one_split 3 a b c d e f g = j → (∑ h : Fin 9, if efx_pair_binary_one_split 3 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 3 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