efx_intact_obstruction_no_coarse_nat
Every assignment of the four intact old bundles and the new singleton in the explicit seven-good instance violates an EFX inequality, checked with exact natural-number sums.
Statement
theorem efx_intact_obstruction_no_coarse_nat : ∀ p : Fin 5 → Fin 4, ¬ (∀ i j : Fin 4, i ≠ j → ∀ g : Fin 7, efx_intact_obstruction_coarse p g = j → (∑ h : Fin 7, if efx_intact_obstruction_coarse p h = j then efx_intact_obstruction_values i h else 0) ≤ (∑ h : Fin 7, if efx_intact_obstruction_coarse p h = i then efx_intact_obstruction_values i h else 0) + efx_intact_obstruction_values i g)
- Source
- Helper for efx_four_agents_additive_exists (OP-7), campaign session IN-404, 2026-11-01. Explicit route obstruction found in experiment 10980; it does not refute EFX existence and carries no research-level advance claim.
- Verified
- 01 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- efx_intact_obstruction_valuesThe explicit strictly positive four-agent seven-good valuation matrix used to test completion by keeping old bundles intact: rows…
- efx_intact_obstruction_coarseAssign the four old bundles {5}, {0,1}, {2,3}, {4} and the new singleton {6} to arbitrary agents p(0),...,p(4), respectively; mergers and…
- Used by 1
- efx_intact_obstruction_no_coarseNo assignment of the four intact old bundles and new singleton in the explicit seven-good instance is EFX after casting its item values to…
The proof, explained
The theorem states that in an explicit fair-division instance with four agents and seven goods grouped into five coarse bundles, no allocation of these bundles can be envy-free up to any good (EFX). Because the space of candidate allocations is finite ($4^5 = 1024$ functions) and all valuations are given by explicit natural numbers, the assertion is decidable. The proof verifies the claim by exhaustive computational evaluation directly inside Lean's trusted kernel.
Every coarse assignment $p$ of the five bundles to the four agents violates at least one EFX inequality. automation
The assertion is a bounded sentence over finite types: there are $4^5 = 1024$ candidate assignments $p : \mathrm{Fin}\ 5 \to \mathrm{Fin}\ 4$, and for each assignment, the condition that agent $i$ does not envy agent $j$ after removing good $g \in A_j$ (formulated as $\sum_{h \in A_j} v_i(h) \le \sum_{h \in A_i} v_i(h) + v_i(g)$ to avoid subtraction in $\mathbb{N}$) involves finitely many pairs of agents and goods with values from an explicit $4 \times 7$ matrix. Because all types, quantifiers, and arithmetic operations are decidable, the `decide +kernel` tactic delegates the check to Lean's trusted kernel, which exhaustively computes the truth value across all 1024 cases and closes the goal.
decide +kernel
- The entire proof is executed via kernel evaluation (`decide +kernel`), which exhaustively checks all 1024 possible assignments without generating an explicit paper-style derivation.
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_intact_obstruction_no_coarse_nat : ∀ p : Fin 5 → Fin 4, ¬ (∀ i j : Fin 4, i ≠ j → ∀ g : Fin 7, efx_intact_obstruction_coarse p g = j → (∑ h : Fin 7, if efx_intact_obstruction_coarse p h = j then efx_intact_obstruction_values i h else 0) ≤ (∑ h : Fin 7, if efx_intact_obstruction_coarse p h = i then efx_intact_obstruction_values i h else 0) + efx_intact_obstruction_values i g) := by decide +kernel