AFTD Auto-Formalizing Theoretical Domains

efx_pair_binary_partial_value

theoremverified

In the explicit binary instance, restrict to the first eight goods and assign the adjacent pairs to the four agents in order. Every agent values every assigned bundle at exactly 3.

Statement

theorem efx_pair_binary_partial_value : ∀ i j : Fin 4,
    additive_valuation (fun g : Fin 8 => (efx_pair_binary_values i g.castSucc : ℝ))
      (bundle_of ![(0 : Fin 4),0,1,1,2,2,3,3] j) = 3
Source
Structural helper for efx_four_agents_additive_exists (OP-7), campaign IN-404, 2026-11-01. Exact route obstruction from experiment 10993, not a counterexample to EFX existence; no novelty claim.
Verified
01 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • efx_pair_binary_valuesA positive four-agent nine-good valuation matrix: the first two rows are (2,1,2,1,2,1,2,1,2), and the last two rows are (1,2,1,2,1,2,1,2,2).
  • 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 theorem is proved by finite computational evaluation. After unfolding the definition of additive valuation into a sum over the goods in agent $j$'s assigned bundle, the equality is verified in $\mathbb{N}$ for all $4 \times 4 = 16$ agent-bundle pairs simultaneously using Lean's kernel decision procedure (`decide +kernel`). The resulting identity is specialized to the chosen agents and cast to $\mathbb{R}$.

  1. For arbitrary agents $i$ and $j$, the valuation reduces to the sum over the goods in bundle $j$: $\sum_{g \in \text{bundle\_of } \sigma \, j} v_i(g) = 3$ in $\mathbb{R}$.

    We introduce arbitrary agents $i, j \in \{0, 1, 2, 3\}$ and unfold the definition of `additive_valuation`, which replaces the bundle valuation with an explicit finite sum over the goods assigned to agent $j$.

    lines 6–7

      intro i j
      dsimp [additive_valuation]
  2. The sum of the values of the goods in bundle $j$ is 3 for agent $i$. automation

    Each bundle $j$ contains the two adjacent goods $2j$ and $2j+1$, whose values under agent $i$'s valuation profile are either $(2, 1)$ or $(1, 2)$, summing to 3 in all cases. Since the domains are finite (16 pairs of agents and bundles), the universal statement over $\mathbb{N}$ is verified by finite computation in the Lean kernel via `decide +kernel`. Specializing this universal identity to the given $i$ and $j$ and casting the equality from $\mathbb{N}$ to $\mathbb{R}$ using `exact_mod_cast` closes the goal.

    lines 8–9

      exact_mod_cast ((by decide +kernel : ∀ i j : Fin 4,
        (∑ g ∈ bundle_of ![(0 : Fin 4),0,1,1,2,2,3,3] j, efx_pair_binary_values i g.castSucc) = 3) i j)

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_pair_binary_partial_value : ∀ i j : Fin 4,    additive_valuation (fun g : Fin 8 => (efx_pair_binary_values i g.castSucc : ℝ))      (bundle_of ![(0 : Fin 4),0,1,1,2,2,3,3] j) = 3 := by  intro i j  dsimp [additive_valuation]  exact_mod_cast ((by decide +kernel : ∀ i j : Fin 4,    (∑ g ∈ bundle_of ![(0 : Fin 4),0,1,1,2,2,3,3] j, efx_pair_binary_values i g.castSucc) = 3) i j)
See it in the graphDiscuss this resultChallenge it