eefx_imp_approx_efk
Let n ≥ 3 and let σ be an allocation of m goods among n agents with nonnegative additive valuations u such that every agent's bundle is nonempty. If σ is an EEFX allocation, then σ is a 1/(n-1)-EF(n-2) allocation.
Statement
theorem eefx_imp_approx_efk {m n : ℕ} (hn : 3 ≤ n) (u : Fin n → Fin m → ℝ) (hu : ∀ i g, 0 ≤ u i g) (σ : Fin m → Fin n) (h_nonempty : ∀ k : Fin n, (bundle_of σ k).Nonempty) (h_eefx : is_alpha_eefx_allocation (fun i => additive_valuation (u i)) 1 σ) : is_alpha_efk_allocation (fun i => additive_valuation (u i)) (1 / ((n : ℝ) - 1)) (n - 2) σ
- Formalizes
- arXiv:2610.34625 Lemma 3.2 -- Online Fair Division with Frequency Predictions
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- eefx_bundle_imp_approx_efkLet n ≥ 3 and let σ be an allocation of m goods among n agents with nonnegative additive valuations u such that every agent's bundle is…
- is_alpha_eefx_allocationAn allocation is alpha-EEFX if each agent's bundle is alpha-EEFX for that agent.
- is_alpha_efk_allocationAn allocation σ : Fin m → Fin n of m goods among n agents is α-EFk under valuations v : Fin n → Finset (Fin m) → ℝ if for all distinct…
- additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
- 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.
Read back from the Lean
Let $m, n \in \mathbb{N}$ with $n \ge 3$. Suppose we have: - a valuation profile $u : \mathrm{Fin}\ n \to \mathrm{Fin}\ m \to \mathbb{R}$ such that $u(i, g) \ge 0$ for all agents $i \in \mathrm{Fin}\ n$ and goods $g \in \mathrm{Fin}\ m$, - an allocation $\sigma : \mathrm{Fin}\ m \to \mathrm{Fin}\ n$ assigning each item to an agent, such that every agent's bundle $\sigma^{-1}(\{k\})$ is non-empty, - the condition that $\sigma$ is a $1$-EEFX allocation with respect to the additive valuations induced by $u$ (that is, for every agent $i$, the items not assigned to $i$, $\mathrm{Fin}\ m \setminus \sigma^{-1}(\{i\})$, can be partitioned into $n - 1$ pairwise disjoint sets $Y_0, \dots, Y_{n-2}$ such that for each $p \in \mathrm{Fin}(n-1)$ and each $g \in Y_p$, agent $i$'s additive value for $Y_p \setminus \{g\}$ is at most agent $i$'s additive value for their own bundle $\sigma^{-1}(\{i\})$). Then $\sigma$ is an $\alpha$-approximate EF$k$ allocation with $\alpha = \frac{1}{n - 1}$ and $k = n - 2$: for all distinct agents $i, j \in \mathrm{Fin}\ n$ ($i \ne j$), $\frac{1}{n - 1}$ times the infimum of agent $i$'s additive value of $\sigma^{-1}(\{j\}) \setminus X$ over all subsets $X \subseteq \sigma^{-1}(\{j\})$ with $|X| \le n - 2$ is at most agent $i$'s additive value of $\sigma^{-1}(\{i\})$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof reduces the allocation-wide approximation guarantee to the bundle-level theorem `eefx_bundle_imp_approx_efk`. By definition, an allocation is 1/(n-1)-EF(n-2) if no agent i envies another agent j beyond a factor of 1/(n-1) once the n - 2 most valuable items are removed from bundle j. Because the allocation is EEFX, agent i's bundle satisfies the EEFX bundle property, so applying the bundle-level lemma to any pair of distinct agents immediately yields the required bound.
To show that σ is a 1/(n-1)-EF(n-2) allocation, it suffices to consider arbitrary distinct agents i and j and establish the approximate envy bound between them.
By definition, an allocation is α-EF(k) if the approximate envy-freeness inequality up to k items holds between every pair of distinct agents i ≠ j. We therefore introduce arbitrary distinct agents i and j with the assumption i ≠ j.
intro i j hijAgent i's valuation of bundle j after removing the n - 2 most valuable items, scaled by 1/(n - 1), is at most agent i's valuation of their own bundle.
This pairwise inequality is given directly by `eefx_bundle_imp_approx_efk`. The lemma's hypotheses are satisfied because n ≥ 3, every agent's bundle is nonempty, valuations are additive and nonnegative, and agent i's bundle satisfies the EEFX condition by the hypothesis that σ is an EEFX allocation.
uses
eefx_bundle_imp_approx_efkexact eefx_bundle_imp_approx_efk hn u hu σ h_nonempty i j hij (h_eefx i)
eefx_bundle_imp_approx_efk- In an allocation with nonempty bundles among at least three agents with nonnegative additive valuations, if an agent i's bundle satisfies the EEFX property, then for any other agent j ≠ i, agent i's valuation of bundle j after removing the n - 2 most valuable items, scaled by 1/(n - 1), is at most agent i's valuation of their own bundle.
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.
/-- An EEFX allocation with nonempty bundles among at least three agents with additive valuations is a 1/(n-1)-EF(n-2) allocation. -/theorem eefx_imp_approx_efk {m n : ℕ} (hn : 3 ≤ n) (u : Fin n → Fin m → ℝ) (hu : ∀ i g, 0 ≤ u i g) (σ : Fin m → Fin n) (h_nonempty : ∀ k : Fin n, (bundle_of σ k).Nonempty) (h_eefx : is_alpha_eefx_allocation (fun i => additive_valuation (u i)) 1 σ) : is_alpha_efk_allocation (fun i => additive_valuation (u i)) (1 / ((n : ℝ) - 1)) (n - 2) σ := by intro i j hij exact eefx_bundle_imp_approx_efk hn u hu σ h_nonempty i j hij (h_eefx i)