efx_pair_binary_requires_two_splits
Every complete EFX allocation of the explicit binary nine-good matrix cast to real values separates the two members of at least two distinct old adjacent pairs among goods 0 through 7.
Statement
theorem efx_pair_binary_requires_two_splits (σ : Fin 9 → Fin 4) (hσ : is_efx_goods (fun i g => (efx_pair_binary_values i g : ℝ)) σ) : ∃ a b : Fin 4, a ≠ b ∧ σ (![0,2,4,6] a) ≠ σ (![1,3,5,7] a) ∧ σ (![0,2,4,6] b) ≠ σ (![1,3,5,7] b)
- 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 3
- 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_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…
- 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…
The proof, explained
The theorem is proved by leveraging an auxiliary impossibility result: an allocation for this valuation matrix cannot be EFX if at most one adjacent pair is split. From this, the proof derives that avoiding any single pair index still leaves at least one split pair. Instantiating this fact once yields a first split pair a, and instantiating it again to avoid a yields a second, distinct split pair b.
For any pair index r ∈ {0, 1, 2, 3}, there exists a different pair index j ≠ r whose two goods are allocated to different agents.
We proceed by contradiction. If no such j existed, then every pair j ≠ r would have its two goods assigned to the same agent. However, `efx_pair_binary_no_one_split_allocation` proves that no allocation that splits at most one pair can be EFX for this binary valuation matrix, contradicting the assumption hσ that σ is an EFX allocation.
uses
efx_pair_binary_no_one_split_allocationclassical have h (r : Fin 4) : ∃ j : Fin 4, j ≠ r ∧ σ (![0,2,4,6] j) ≠ σ (![1,3,5,7] j) := by by_contra h push Not at h exact efx_pair_binary_no_one_split_allocation σ r h hσ
There exist two distinct pair indices a and b such that both pairs are split by σ.
Applying the intermediate claim to r = 0 yields an index a whose pair is split. Applying it again with r = a yields a second split pair b with b ≠ a. By symmetry of inequality, a ≠ b, so a and b furnish the two distinct split pairs required by the theorem.
obtain ⟨a, _, ha⟩ := h 0 obtain ⟨b, hb, hbs⟩ := h a exact ⟨a, b, hb.symm, ha, hbs⟩
efx_pair_binary_no_one_split_allocation- No allocation of the 9 goods to 4 agents under the binary valuation matrix can be EFX if all adjacent pairs among goods 0 through 7, except possibly a single designated pair r, are kept together (assigned to the same agent).
- The adjacent pairs {0, 1}, {2, 3}, {4, 5}, and {6, 7} are represented formally via the two 4-tuples `![0, 2, 4, 6]` and `![1, 3, 5, 7]`, so that for each index j : Fin 4, the j-th pair consists of goods `![0, 2, 4, 6] j` and `![1, 3, 5, 7] j`.
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_requires_two_splits (σ : Fin 9 → Fin 4) (hσ : is_efx_goods (fun i g => (efx_pair_binary_values i g : ℝ)) σ) : ∃ a b : Fin 4, a ≠ b ∧ σ (![0,2,4,6] a) ≠ σ (![1,3,5,7] a) ∧ σ (![0,2,4,6] b) ≠ σ (![1,3,5,7] b) := by classical have h (r : Fin 4) : ∃ j : Fin 4, j ≠ r ∧ σ (![0,2,4,6] j) ≠ σ (![1,3,5,7] j) := by by_contra h push Not at h exact efx_pair_binary_no_one_split_allocation σ r h hσ obtain ⟨a, _, ha⟩ := h 0 obtain ⟨b, hb, hbs⟩ := h a exact ⟨a, b, hb.symm, ha, hbs⟩