is_wefx_goods_unit_weights_iff_is_efx_goods
When all agents have unit entitlements, weighted EFX is equivalent to standard unweighted EFX.
Statement
lemma is_wefx_goods_unit_weights_iff_is_efx_goods {m n : ℕ} (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) : is_wefx_goods (fun _ => 1) u σ ↔ is_efx_goods u σ
- Source
- arXiv:2305.16081, Def. 3
- Verified
- 09 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- is_wefx_goodsAn allocation σ of m goods to n agents with positive entitlements w is weighted EFX (WEFX) if for every pair of distinct agents i and j,…
- 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.
Read back from the Lean
For any natural numbers $m$ and $n$, valuation function $u : \text{Fin } n \to \text{Fin } m \to \mathbb{R}$ (where $u\ i\ g$ is the value agent $i$ assigns to good $g$), and allocation $\sigma : \text{Fin } m \to \text{Fin } n$ (assigning each good to an agent):
The weighted envy-free up to any good condition with all weights equal to 1 (is_wefx_goods (fun _ => 1) u σ) holds if and only if the standard envy-free up to any good condition (is_efx_goods u σ) holds.
Specifically, for all $i \neq j$ and each good $g$ allocated to $j$, the valuation of agent $i$ for $j$'s bundle with $g$ removed divided by $1$ is at most the valuation of agent $i$ for their own bundle divided by $1$, if and only if the valuation of agent $i$ for $j$'s bundle with $g$ removed is at most the valuation of agent $i$ for their own bundle.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- Weighted EFX with all entitlements equal to 1 coincides with standard EFX. -/ lemma is_wefx_goods_unit_weights_iff_is_efx_goods {m n : ℕ} (u : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) : is_wefx_goods (fun _ => 1) u σ ↔ is_efx_goods u σ := by simp [is_wefx_goods, is_efx_goods]