efx_pair_binary_no_one_split_allocation
For the explicit binary nine-good matrix cast to real values, any allocation which preserves all but possibly one of the four old adjacent pairs fails EFX.
Statement
theorem efx_pair_binary_no_one_split_allocation (σ : Fin 9 → Fin 4) (r : Fin 4) (hstay : ∀ j : Fin 4, j ≠ r → σ (![0,2,4,6] j) = σ (![1,3,5,7] j)) : ¬ is_efx_goods (fun i g => (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 4
- 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_splitFor the explicit binary nine-good matrix cast to real values, no allocation encoded by the one-split construction is 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…
- Used by 1
- efx_pair_binary_requires_two_splitsEvery complete EFX allocation of the explicit binary nine-good matrix cast to real values separates the two members of at least two…
The proof, explained
The theorem shows that any allocation of 9 goods among 4 agents that leaves at least three of the four designated pairs (0,1), (2,3), (4,5), and (6,7) unseparated cannot be envy-free up to any good (EFX) under the valuation matrix efx_pair_binary_values. The proof splits into four cases depending on which pair r ∈ {0, 1, 2, 3} may be separated. In each case, preserving the remaining three pairs allows σ to be rewritten in the canonical template efx_pair_binary_one_split r, at which point the lemma efx_pair_binary_no_one_split immediately rules out the EFX property.
It suffices to prove the result for each possible value of r ∈ {0, 1, 2, 3}.
The index r designates the single pair among the four pairs of goods that is allowed to be split across different agents. A case analysis on r in the finite type Fin 4 divides the problem into four subcases: r = 0, 1, 2, and 3.
fin_cases r
When r = 0, the allocation σ is not EFX.
When r = 0, the hypothesis hstay applied to j = 1, 2, 3 ensures that the other three pairs remain unsplit: σ(2) = σ(3), σ(4) = σ(5), and σ(6) = σ(7). By evaluating on each of the nine goods, σ matches the parameterized template efx_pair_binary_one_split 0 (σ 0) (σ 1) (σ 2) (σ 4) (σ 6) (σ 8). Applying efx_pair_binary_no_one_split shows that this allocation cannot be EFX.
uses
efx_pair_binary_no_one_split· have h1 : σ 2 = σ 3 := hstay 1 (by decide) have h2 : σ 4 = σ 5 := hstay 2 (by decide) have h3 : σ 6 = σ 7 := hstay 3 (by decide) have heq : σ = efx_pair_binary_one_split 0 (σ 0) (σ 1) (σ 2) (σ 4) (σ 6) (σ 8) := by funext g fin_cases g <;> simp [efx_pair_binary_one_split, h1, h2, h3] rw [heq] exact efx_pair_binary_no_one_split 0 (σ 0) (σ 1) (σ 2) (σ 4) (σ 6) (σ 8)
When r = 1, the allocation σ is not EFX.
When r = 1, pairs 0, 2, and 3 remain intact: σ(0) = σ(1), σ(4) = σ(5), and σ(6) = σ(7). Checking each of the nine goods shows that σ coincides with efx_pair_binary_one_split 1 (σ 0) (σ 2) (σ 3) (σ 4) (σ 6) (σ 8). Applying efx_pair_binary_no_one_split completes this case.
uses
efx_pair_binary_no_one_split· have h0 : σ 0 = σ 1 := hstay 0 (by decide) have h2 : σ 4 = σ 5 := hstay 2 (by decide) have h3 : σ 6 = σ 7 := hstay 3 (by decide) have heq : σ = efx_pair_binary_one_split 1 (σ 0) (σ 2) (σ 3) (σ 4) (σ 6) (σ 8) := by funext g fin_cases g <;> simp [efx_pair_binary_one_split, h0, h2, h3] rw [heq] exact efx_pair_binary_no_one_split 1 (σ 0) (σ 2) (σ 3) (σ 4) (σ 6) (σ 8)
When r = 2, the allocation σ is not EFX.
When r = 2, pairs 0, 1, and 3 remain intact: σ(0) = σ(1), σ(2) = σ(3), and σ(6) = σ(7). Evaluating on all nine goods shows that σ is identical to efx_pair_binary_one_split 2 (σ 0) (σ 2) (σ 4) (σ 5) (σ 6) (σ 8). Applying efx_pair_binary_no_one_split completes this case.
uses
efx_pair_binary_no_one_split· have h0 : σ 0 = σ 1 := hstay 0 (by decide) have h1 : σ 2 = σ 3 := hstay 1 (by decide) have h3 : σ 6 = σ 7 := hstay 3 (by decide) have heq : σ = efx_pair_binary_one_split 2 (σ 0) (σ 2) (σ 4) (σ 5) (σ 6) (σ 8) := by funext g fin_cases g <;> simp [efx_pair_binary_one_split, h0, h1, h3] rw [heq] exact efx_pair_binary_no_one_split 2 (σ 0) (σ 2) (σ 4) (σ 5) (σ 6) (σ 8)
When r = 3, the allocation σ is not EFX.
When r = 3, pairs 0, 1, and 2 remain intact: σ(0) = σ(1), σ(2) = σ(3), and σ(4) = σ(5). Evaluating on all nine goods shows that σ is identical to efx_pair_binary_one_split 3 (σ 0) (σ 2) (σ 4) (σ 6) (σ 7) (σ 8). Applying efx_pair_binary_no_one_split completes the final case.
uses
efx_pair_binary_no_one_split· have h0 : σ 0 = σ 1 := hstay 0 (by decide) have h1 : σ 2 = σ 3 := hstay 1 (by decide) have h2 : σ 4 = σ 5 := hstay 2 (by decide) have heq : σ = efx_pair_binary_one_split 3 (σ 0) (σ 2) (σ 4) (σ 6) (σ 7) (σ 8) := by funext g fin_cases g <;> simp [efx_pair_binary_one_split, h0, h1, h2] rw [heq] exact efx_pair_binary_no_one_split 3 (σ 0) (σ 2) (σ 4) (σ 6) (σ 7) (σ 8)
efx_pair_binary_no_one_split- For any index r ∈ Fin 4 and agent assignments a, b, c, d, e, f ∈ Fin 4, the allocation efx_pair_binary_one_split r a b c d e f fails to satisfy the EFX property with respect to the binary valuation matrix efx_pair_binary_values.
- The equality between σ and the template allocation efx_pair_binary_one_split is established by functional extensionality and an automated exhaustive check on all nine goods (fin_cases g <;> simp ...).
- The four pairs of adjacent goods are represented by the vectors ![0,2,4,6] and ![1,3,5,7], which correspond to (0,1), (2,3), (4,5), and (6,7), while good 8 remains unpaired.
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_allocation (σ : Fin 9 → Fin 4) (r : Fin 4) (hstay : ∀ j : Fin 4, j ≠ r → σ (![0,2,4,6] j) = σ (![1,3,5,7] j)) : ¬ is_efx_goods (fun i g => (efx_pair_binary_values i g : ℝ)) σ := by fin_cases r · have h1 : σ 2 = σ 3 := hstay 1 (by decide) have h2 : σ 4 = σ 5 := hstay 2 (by decide) have h3 : σ 6 = σ 7 := hstay 3 (by decide) have heq : σ = efx_pair_binary_one_split 0 (σ 0) (σ 1) (σ 2) (σ 4) (σ 6) (σ 8) := by funext g fin_cases g <;> simp [efx_pair_binary_one_split, h1, h2, h3] rw [heq] exact efx_pair_binary_no_one_split 0 (σ 0) (σ 1) (σ 2) (σ 4) (σ 6) (σ 8) · have h0 : σ 0 = σ 1 := hstay 0 (by decide) have h2 : σ 4 = σ 5 := hstay 2 (by decide) have h3 : σ 6 = σ 7 := hstay 3 (by decide) have heq : σ = efx_pair_binary_one_split 1 (σ 0) (σ 2) (σ 3) (σ 4) (σ 6) (σ 8) := by funext g fin_cases g <;> simp [efx_pair_binary_one_split, h0, h2, h3] rw [heq] exact efx_pair_binary_no_one_split 1 (σ 0) (σ 2) (σ 3) (σ 4) (σ 6) (σ 8) · have h0 : σ 0 = σ 1 := hstay 0 (by decide) have h1 : σ 2 = σ 3 := hstay 1 (by decide) have h3 : σ 6 = σ 7 := hstay 3 (by decide) have heq : σ = efx_pair_binary_one_split 2 (σ 0) (σ 2) (σ 4) (σ 5) (σ 6) (σ 8) := by funext g fin_cases g <;> simp [efx_pair_binary_one_split, h0, h1, h3] rw [heq] exact efx_pair_binary_no_one_split 2 (σ 0) (σ 2) (σ 4) (σ 5) (σ 6) (σ 8) · have h0 : σ 0 = σ 1 := hstay 0 (by decide) have h1 : σ 2 = σ 3 := hstay 1 (by decide) have h2 : σ 4 = σ 5 := hstay 2 (by decide) have heq : σ = efx_pair_binary_one_split 3 (σ 0) (σ 2) (σ 4) (σ 6) (σ 7) (σ 8) := by funext g fin_cases g <;> simp [efx_pair_binary_one_split, h0, h1, h2] rw [heq] exact efx_pair_binary_no_one_split 3 (σ 0) (σ 2) (σ 4) (σ 6) (σ 7) (σ 8)