AFTD Auto-Formalizing Theoretical Domains

efx_three_bonus_distinct_sanity

theoremverified

Every value in the explicit matrix is positive and each bonus is no larger than every old good for each agent. The old allocation (0,1,2,3) is EFX with utility 38 for each agent. The complete allocation (0,1,2,3,0,0,0) is EFX and gives each agent at least 38.

Statement

theorem efx_three_bonus_distinct_sanity :
    (∀ i g, 0 < efx_three_bonus_distinct_values i g) ∧
    (∀ (i : Fin 4) (g : Fin 3) (h : Fin 4),
      efx_three_bonus_distinct_values i (Fin.natAdd 4 g) ≤ efx_three_bonus_distinct_values i (Fin.castAdd 3 h)) ∧
    is_efx_goods (fun i (g : Fin 4) => (efx_three_bonus_distinct_values i (Fin.castAdd 3 g) : ℝ)) ![(0 : Fin 4),1,2,3] ∧
    is_efx_goods (fun i g => (efx_three_bonus_distinct_values i g : ℝ)) ![(0 : Fin 4),1,2,3,0,0,0] ∧
    (∀ i : Fin 4, additive_valuation (fun g : Fin 4 => (efx_three_bonus_distinct_values i (Fin.castAdd 3 g) : ℝ))
      (bundle_of ![(0 : Fin 4),1,2,3] i) = 38) ∧
    (∀ i : Fin 4, 38 ≤ additive_valuation (fun g => (efx_three_bonus_distinct_values i g : ℝ))
      (bundle_of ![(0 : Fin 4),1,2,3,0,0,0] i))
Source
Finite obstruction to the distinct-recipient exchange route for OP-7, experiments 11403, 11405 and 11406.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • efx_three_bonus_distinct_valuesThe natural-valued four-agent, seven-good matrix whose rows are (38,36,58,56,1,1,17), (18,38,54,36,1,1,17), (18,38,38,36,17,1,1), and…
  • 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.
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.

The proof, explained

The proof verifies six sanity properties of an explicit valuation matrix with 4 agents and 7 goods (4 original and 3 bonus goods). The first two properties—positivity of all valuations and bounding bonus goods by original goods—are verified by kernel evaluation over the finite domain. For the two EFX (envy-free up to any good) claims, the lemma `is_efx_goods_nat_cast_iff` converts the real-valued EFX condition to a decidable condition on natural numbers, which the kernel evaluates directly. Finally, the utility guarantees (each agent gets 38 in the base allocation, and at least 38 in the augmented allocation) are proved by unfolding additive valuation and evaluating the bundle sums for each of the four agents.

  1. All valuations are strictly positive, every bonus good is worth at most as much as each original good to every agent, and the goal reduces to the remaining four claims.

    The goal is a conjunction of six assertions. Kernel evaluation (`decide +kernel`) proves the first two conjuncts by exhaustively checking all 28 entries in the explicit 4 × 7 valuation matrix for positivity, and checking all 48 inequalities showing that each bonus good (indices 4, 5, 6) is valued no more than each original good (indices 0, 1, 2, 3) by each of the four agents. The remaining four subgoals are left open.

    line 11

      refine ⟨by decide +kernel, by decide +kernel, ?_, ?_, ?_, ?_⟩
  2. The initial allocation, assigning good i to agent i for each i ∈ {0, 1, 2, 3}, is envy-free up to any good (EFX).

    The equivalence `is_efx_goods_nat_cast_iff` transforms the EFX condition with real valuations into an equivalent discrete condition over natural numbers: for any distinct agents i and j and any good g in j's bundle, the sum of values i assigns to j's bundle is at most the value i assigns to their own bundle plus the value of g. Because this is a finite universal statement over 4 agents and 4 goods with explicit values, `decide +kernel` verifies it by direct computation.

    lines 12–13

    uses is_efx_goods_nat_cast_iff

      · apply (is_efx_goods_nat_cast_iff _ _).mpr
        decide +kernel
  3. The extended allocation, where the original four goods remain with agents 0, 1, 2, 3 and all three bonus goods are allocated to agent 0, is also EFX.

    Applying `is_efx_goods_nat_cast_iff` again reduces the EFX condition on the complete 7-good allocation to an inequality over natural numbers. Lean's kernel verifies this condition exhaustively across all pairs of agents and items via `decide +kernel`.

    lines 14–15

    uses is_efx_goods_nat_cast_iff

      · apply (is_efx_goods_nat_cast_iff _ _).mpr
        decide +kernel
  4. In the initial allocation, every agent receives a bundle with an additive valuation of exactly 38.

    We introduce an arbitrary agent i and unfold the definition of `additive_valuation` into a sum over the bundle assigned to i. Exhaustive case analysis on the four agents (`fin_cases i`) checks each case: each agent i receives exactly good i, whose value in row i is 38. Then `norm_cast` computes the singleton sum and verifies the equality in ℝ.

    lines 16–18

      · intro i
        dsimp [additive_valuation]
        fin_cases i <;> norm_cast
  5. In the extended allocation, every agent receives a bundle with an additive valuation of at least 38.

    We introduce an arbitrary agent i, unfold `additive_valuation` into a sum over agent i's bundle, and evaluate all four cases (`fin_cases i`). Agents 1, 2, and 3 each retain their original good of value 38 (satisfying 38 ≤ 38), while agent 0 receives goods 0, 4, 5, and 6 with total value 38 + 1 + 1 + 17 = 57 (satisfying 38 ≤ 57). `norm_cast` evaluates these sums and confirms the inequality in ℝ.

    lines 19–21

      · intro i
        dsimp [additive_valuation]
        fin_cases i <;> norm_cast
is_efx_goods_nat_cast_iff
An allocation of goods is EFX with respect to real-valued valuations cast from natural numbers if and only if for any distinct agents i and j and every good g in j's bundle, 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 agent i assigns to g, evaluated over ℕ.

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_three_bonus_distinct_sanity :    (∀ i g, 0 < efx_three_bonus_distinct_values i g) ∧    (∀ (i : Fin 4) (g : Fin 3) (h : Fin 4),      efx_three_bonus_distinct_values i (Fin.natAdd 4 g) ≤ efx_three_bonus_distinct_values i (Fin.castAdd 3 h)) ∧    is_efx_goods (fun i (g : Fin 4) => (efx_three_bonus_distinct_values i (Fin.castAdd 3 g) : ℝ)) ![(0 : Fin 4),1,2,3] ∧    is_efx_goods (fun i g => (efx_three_bonus_distinct_values i g : ℝ)) ![(0 : Fin 4),1,2,3,0,0,0] ∧    (∀ i : Fin 4, additive_valuation (fun g : Fin 4 => (efx_three_bonus_distinct_values i (Fin.castAdd 3 g) : ℝ))      (bundle_of ![(0 : Fin 4),1,2,3] i) = 38) ∧    (∀ i : Fin 4, 38 ≤ additive_valuation (fun g => (efx_three_bonus_distinct_values i g : ℝ))      (bundle_of ![(0 : Fin 4),1,2,3,0,0,0] i)) := by  refine ⟨by decide +kernel, by decide +kernel, ?_, ?_, ?_, ?_⟩  · apply (is_efx_goods_nat_cast_iff _ _).mpr    decide +kernel  · apply (is_efx_goods_nat_cast_iff _ _).mpr    decide +kernel  · intro i    dsimp [additive_valuation]    fin_cases i <;> norm_cast  · intro i    dsimp [additive_valuation]    fin_cases i <;> norm_cast
See it in the graphDiscuss this resultChallenge it