AFTD Auto-Formalizing Theoretical Domains

efx_intact_obstruction_partial_efx

theoremverified

In the explicit seven-good instance restricted to the first six goods, assigning {5} to agent 0, {0,1} to agent 1, {2,3} to agent 2, and {4} to agent 3 is EFX.

Statement

theorem efx_intact_obstruction_partial_efx :
    is_efx_goods (fun i (g : Fin 6) => (efx_intact_obstruction_values i g.castSucc : ℝ))
      ![(1 : Fin 4),1,2,2,3,0]
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 4
  • is_efx_goods_nat_cast_iffFor natural-number item values, EFX after casting values to the reals is equivalent to all natural-number inequalities comparing each…
  • efx_intact_obstruction_valuesThe explicit strictly positive four-agent seven-good valuation matrix used to test completion by keeping old bundles intact: rows…
  • 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…
  • bundle_ofUnder an allocation that gives each item x to agent s(x), agent i's bundle is the set of items given to i.

The proof, explained

The theorem establishes that a specific assignment of six goods among four agents is envy-free up to any good (EFX). The proof uses `is_efx_goods_nat_cast_iff` to rephrase the real-valued EFX condition as an equivalent set of additive inequalities over natural numbers. Since the agents, goods, and valuation matrix are all finite and concrete, the remaining finite verification is completed automatically by kernel computation (`decide +kernel`).

  1. The EFX condition on real valuations reduces to a family of additive inequalities over the natural numbers.

    Applying the backward direction of `is_efx_goods_nat_cast_iff` transforms the EFX requirement into checking that for every pair of distinct agents i, j and each good g allocated to j, the sum of i's valuations over j's bundle is at most the sum over i's own bundle plus the valuation of g. This formulation avoids set erasure and real-number subtraction in favor of natural number arithmetic.

    line 6

    uses is_efx_goods_nat_cast_iff

      apply (is_efx_goods_nat_cast_iff _ _).mpr
  2. The given allocation satisfies all the required EFX inequalities. automation

    Because the set of four agents, the six goods, and their integer valuations are completely concrete and finite, the universal quantification reduces to finitely many numerical inequalities. Lean's kernel verifies each of these finite arithmetic checks directly by evaluation.

    line 7

      decide +kernel
is_efx_goods_nat_cast_iff
An allocation is EFX with respect to integer-valued valuations cast to the real numbers if and only if for all distinct agents i and j and every good g assigned to j, the total value agent i assigns to j's bundle is at most the value agent i assigns to their own bundle plus the value of g.

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_partial_efx :    is_efx_goods (fun i (g : Fin 6) => (efx_intact_obstruction_values i g.castSucc : ℝ))      ![(1 : Fin 4),1,2,2,3,0] := by  apply (is_efx_goods_nat_cast_iff _ _).mpr  decide +kernel
See it in the graphDiscuss this resultChallenge it