AFTD Auto-Formalizing Theoretical Domains

efx_pair_binary_no_one_split_three_nat

theoremverified

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.

  1. 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$.

    line 8

      intro a
  2. For 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.

    line 9

      fin_cases a <;> 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

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
See it in the graphDiscuss this resultChallenge it