AFTD Auto-Formalizing Theoretical Domains

eefx_imp_approx_efk

theoremverifiedformalization

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.

  1. 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.

    line 7

      intro i j hij
  2. 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.

    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.

    line 8

    uses eefx_bundle_imp_approx_efk

      exact 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

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