efx_pair_binary_partial_value
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}$.
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$.
intro i j dsimp [additive_valuation]
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.
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)
- The equality is verified by exhaustive computational reflection in the Lean kernel (`decide +kernel`) over all 16 agent-bundle pairs, rather than by symbolic reasoning about the alternating pattern of values.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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)