AFTD Auto-Formalizing Theoretical Domains

efx_no_self_three_split_sanity

theoremverified

The matrix is positive; each agent values every old triple equally at her baseline, values every good in her own triple at least as much as charity, and each triple has a good that some foreign agent values below charity. The initial partial allocation is EFX.

Statement

theorem efx_no_self_three_split_sanity :
  (∀ i g, 0 < efx_no_self_three_split_values i g) ∧
  (∀ i j, efx_no_self_three_split_value i (efx_no_self_three_split_old j) = efx_no_self_three_split_baseline i) ∧
  (∀ i g, g ∈ efx_no_self_three_split_old i → efx_no_self_three_split_values i 12 ≤ efx_no_self_three_split_values i g) ∧
  (∀ j, ∃ i : Fin 4, i ≠ j ∧ ∃ g ∈ efx_no_self_three_split_old j,
      efx_no_self_three_split_values i g < efx_no_self_three_split_values i 12) ∧
  is_efx_goods (fun i (g : Fin 12) => (efx_no_self_three_split_values i g.castSucc : ℝ))
    ![(0 : Fin 4),0,0,1,1,1,2,2,2,3,3,3]
Source
Positive equal-triple no-self-champion obstruction to the OP-7 two-bundle exchange route, experiments 11462–11471.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • efx_no_self_three_split_valuesThe positive natural-valued matrix with rows (3,23,43,1,38,30,35,1,33,2,47,20,3), (1,25,44,40,9,21,1,41,28,34,1,35,3),…
  • efx_no_self_three_split_valueThe natural additive value to i of the goods in S.
  • efx_no_self_three_split_oldThe old partial allocation consists of four consecutive triples; good 12 is unallocated.
  • efx_no_self_three_split_baselineEach agent’s value of every old triple, and hence her initial utility.
  • 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…
  • 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.
Used by 1

The proof, explained

The theorem verifies that a concrete 4-agent, 13-good valuation matrix and initial partition of the first 12 goods satisfy the five structural properties required of a counterexample in fair division. The proof decomposes the conjunction into five finite verification goals: positivity, equal triple valuation at baseline, lower bounds on own items versus charity, existence of items valued strictly below charity by an outside agent, and EFX of the partial allocation. Each condition is verified by finite exhaustive computation via `decide`, with the EFX property first rewritten from real arithmetic to natural arithmetic via `is_efx_goods_nat_cast_iff`.

  1. The goal is decomposed into five independent sanity conditions.

    Using `refine ⟨...⟩`, the conjunction is split into five subgoals: strict positivity of all valuations, equality of bundle values to baseline, lower bounds on own goods relative to charity, existence in each bundle of a good valued below charity by an outside agent, and envy-freeness up to any good (EFX) of the initial allocation.

    line 9

      refine ⟨?_, ?_, ?_, ?_, ?_⟩
  2. All entries in the valuation matrix are strictly positive.

    For all 4 agents and 13 goods, the valuation satisfies 0 < v_{i,g}. Direct evaluation across the finite matrix via `decide` confirms the claim.

    line 10

      · decide
  3. Each agent values every triple bundle equally at her baseline.

    For every agent i and each of the four triples j, the sum of agent i's valuations for the items in bundle j equals agent i's baseline value (69, 70, 51, and 37 for agents 0 through 3, respectively). All 16 equalities are verified by computation with `decide`.

    line 11

      · decide
  4. Each agent values every good in her own bundle at least as much as the charity good.

    For each agent i and every item g in bundle i, the inequality v_{i, 12} ≤ v_{i, g} holds, where good 12 is the charity item. This is verified across all 12 allocated goods by direct evaluation with `decide`.

    line 12

      · decide
  5. Every bundle contains a good that some foreign agent values strictly below charity.

    For each bundle j, there exists an agent i ≠ j and an item g in bundle j such that v_{i, g} < v_{i, 12}. Lean's `decide` tactic checks this existential condition by exhaustively searching over the finite agent and item domains.

    line 13

      · decide
  6. The initial allocation of the first 12 goods is envy-free up to any good (EFX).

    Rewriting with `is_efx_goods_nat_cast_iff` converts the EFX condition on real valuations into an equivalent inequality on natural numbers: for every pair of distinct agents i ≠ j and every item g in bundle j, the value of bundle j to agent i is bounded by the value of bundle i to agent i plus the value of g to agent i. The resulting finite set of arithmetic checks is closed by exhaustive evaluation (`decide`).

    lines 14–15

    uses is_efx_goods_nat_cast_iff

      · rw [is_efx_goods_nat_cast_iff]
        decide
is_efx_goods_nat_cast_iff
An allocation of goods is EFX under real-valued valuations given by casting from natural numbers if and only if for all distinct agents i ≠ j and each good g in agent j's bundle, agent i's total valuation for bundle j is at most her valuation for bundle i plus her valuation for 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

theorem efx_no_self_three_split_sanity :  (∀ i g, 0 < efx_no_self_three_split_values i g) ∧  (∀ i j, efx_no_self_three_split_value i (efx_no_self_three_split_old j) = efx_no_self_three_split_baseline i) ∧  (∀ i g, g ∈ efx_no_self_three_split_old i → efx_no_self_three_split_values i 12 ≤ efx_no_self_three_split_values i g) ∧  (∀ j, ∃ i : Fin 4, i ≠ j ∧ ∃ g ∈ efx_no_self_three_split_old j,      efx_no_self_three_split_values i g < efx_no_self_three_split_values i 12) ∧  is_efx_goods (fun i (g : Fin 12) => (efx_no_self_three_split_values i g.castSucc : ℝ))    ![(0 : Fin 4),0,0,1,1,1,2,2,2,3,3,3] := by  refine ⟨?_, ?_, ?_, ?_, ?_⟩  · decide  · decide  · decide  · decide  · rw [is_efx_goods_nat_cast_iff]    decide
See it in the graphDiscuss this resultChallenge it