efx_pair_binary_full_efx
For the explicit binary nine-good valuation matrix cast to real values, the full allocation (3,3,1,2,0,2,1,1,0), listing the owner of each good, is EFX.
Statement
theorem efx_pair_binary_full_efx : is_efx_goods (fun i g => (efx_pair_binary_values i g : ℝ)) ![(3 : Fin 4),3,1,2,0,2,1,1,0]
- 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 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_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).
- 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 proof shows that the given allocation of nine goods among four agents is EFX (envy-free up to any good) with respect to the binary valuations cast to real numbers. It first reduces the real-valued EFX definition to an equivalent finite condition on natural numbers via `is_efx_goods_nat_cast_iff`. Because the agents, goods, valuations, and allocation are all explicit and finite, the remaining universally quantified inequality is verified exhaustively by computational evaluation (`decide`).
The real-valued EFX property is equivalent to a system of additive inequalities in natural numbers.
Rewriting with `is_efx_goods_nat_cast_iff` transforms the condition that the allocation is EFX under real-valued additive valuations into an equivalent condition on the underlying natural numbers: for every pair of distinct agents i ≠ j and every good g allocated to j, the sum of agent i's valuations for the goods in j's bundle is at most the sum of i's valuations for i's own bundle plus the valuation i assigns to g.
uses
is_efx_goods_nat_cast_iffrw [is_efx_goods_nat_cast_iff]The EFX inequalities hold for all pairs of distinct agents and all allocated goods. automation
Because the set of four agents, nine goods, valuation matrix `efx_pair_binary_values`, and allocation vector are all concrete and finite, this universal statement is decidable. The `decide` tactic checks all finitely many cases by direct evaluation and closes the goal.
decide
is_efx_goods_nat_cast_iff- An allocation of goods is EFX under natural-number valuations cast to real numbers if and only if for every pair of distinct agents i ≠ j and each good g assigned to j, the total value agent i assigns to bundle j is at most the total value i assigns to bundle i plus the value of g to i.
- The verification of the inequalities for all pairs of agents and assigned goods is carried out entirely by kernel computation via `decide` without explicit manual case analysis.
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_full_efx : is_efx_goods (fun i g => (efx_pair_binary_values i g : ℝ)) ![(3 : Fin 4),3,1,2,0,2,1,1,0] := by rw [is_efx_goods_nat_cast_iff] decide