AFTD Auto-Formalizing Theoretical Domains

is_wefx_goods_unit_weights_iff_is_efx_goods

lemmaverified

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]
See it in the graphDiscuss this resultChallenge it