AFTD Auto-Formalizing Theoretical Domains

efx_intact_obstruction_no_coarse_nat

theoremverified

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.

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

    line 7

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