AFTD Auto-Formalizing Theoretical Domains

op819_has_online_single_high_alpha_mono

theoremverified

If a deterministic online algorithm guarantees a beta-EFX allocation for n agents and m goods under single-high valuations with ratio R >= 0, then for any alpha <= beta, there exists a deterministic online algorithm guaranteeing an alpha-EFX allocation.

Statement

theorem op819_has_online_single_high_alpha_mono {n m : ℕ} {R α β : ℝ} (hR : 0 ≤ R) (hαβ : α ≤ β)
    (h : has_online_single_high_alpha_efx n m R β) :
    has_online_single_high_alpha_efx n m R α
Source
arXiv:2610.34625
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • has_online_single_high_alpha_efxThere exists a deterministic online allocation algorithm for n agents and m goods that guarantees an alpha-EFX allocation for every…
  • is_alpha_efx_goodsAn allocation of m indivisible goods to n agents is alpha-EFX under additive valuations u if for every pair of distinct agents i and j,…
  • is_single_high_profileA valuation profile of n agents on m goods is a single-high profile with ratio R if every agent has a single-high valuation with ratio R.
  • is_single_high_valuationAn agent's additive valuation vector on m goods is a single-high valuation with ratio R if there exists a good of value R such that all…
  • 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.
  • is_online_allocatorAn allocation algorithm on m goods for n agents is online if the allocation of each arriving good t depends only on the valuation vectors…

Read back from the Lean

For any natural numbers $n$ and $m$, and real numbers $R, \alpha, \beta$, if $0 \le R$ and $\alpha \le \beta$, and if there exists an online allocator for $n$ agents and $m$ items that produces a $\beta$-EFX allocation for every single-high valuation profile with parameter $R$, then there exists an online allocator that produces an $\alpha$-EFX allocation for every single-high valuation profile with parameter $R$.

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 same online algorithm that guarantees a β-EFX allocation also achieves an α-EFX allocation whenever α ≤ β. Because single-high valuations assign non-negative values (either R ≥ 0 or 1) to all items, the valuation of any bundle is non-negative. Multiplying this non-negative valuation by α ≤ β bounds the required guarantee by the known β-EFX guarantee, concluding the proof by transitivity of inequality.

  1. The existing algorithm `alg` can serve as the witness for α-EFX solvability, reducing the theorem to checking the α-EFX inequality.

    From the hypothesis that an online algorithm guarantees β-EFX allocations, extract the algorithm `alg`, its online property `halg_online`, and its guarantee `halg_efx`. Propose `alg` for the α-EFX claim. Since `alg` is already known to be online, it suffices to show that for any single-high profile v, distinct agents i and j, and good g in j's bundle, the α-EFX condition α * v_i(bundle_j \ {g}) ≤ v_i(bundle_i) holds.

    lines 5–6

      rcases h with ⟨alg, halg_online, halg_efx⟩
      refine ⟨alg, halg_online, fun v hv i j hij g hg => ?_⟩
  2. Agent i's valuation of agent j's bundle without good g is non-negative.

    By definition, an additive valuation is the sum over the items in the bundle. Using `Finset.sum_nonneg`, it suffices to show each item x has non-negative value under v i. Under a single-high profile, agent i values some item g0 at R and every other item at 1. In the case x = g0, the value is R, which is non-negative by assumption (hR). In the case x ≠ g0, the value is 1, which is also non-negative (closed by linear arithmetic).

    lines 7–14

    uses Finset.sum_nonneg

      have h_nonneg : 0 ≤ additive_valuation (v i) ((bundle_of (alg v) j).erase g) := by
        dsimp [additive_valuation]
        apply Finset.sum_nonneg
        intro x _
        rcases hv i with ⟨g0, hg0, hrest⟩
        by_cases hx : x = g0
        · rw [hx, hg0]; exact hR
        · rw [hrest x hx]; linarith
  3. The α-EFX inequality holds for alg.

    Since α ≤ β and agent i's valuation of bundle_j \ {g} is non-negative, multiplying by this valuation preserves the inequality via `mul_le_mul_of_nonneg_right`, showing that α * v_i(bundle_j \ {g}) ≤ β * v_i(bundle_j \ {g}). Transitivity (`le_trans`) with the known β-EFX bound β * v_i(bundle_j \ {g}) ≤ v_i(bundle_i) completes the proof.

    line 15

    uses le_trans, mul_le_mul_of_nonneg_right

      exact le_trans (mul_le_mul_of_nonneg_right hαβ h_nonneg) (halg_efx v hv i j hij g hg)
Finset.sum_nonneg
A finite sum of non-negative elements in an ordered additive monoid is non-negative.
le_trans
Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
mul_le_mul_of_nonneg_right
Multiplication on the right by a non-negative element preserves inequality: if b ≤ c and 0 ≤ a, then b * a ≤ c * a.

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

/-- Monotonicity of online single-high alpha-EFX solvability in the approximation ratio alpha. -/theorem op819_has_online_single_high_alpha_mono {n m : ℕ} {R α β : ℝ} (hR : 0 ≤ R) (hαβ : α ≤ β)    (h : has_online_single_high_alpha_efx n m R β) :    has_online_single_high_alpha_efx n m R α := by  rcases h with ⟨alg, halg_online, halg_efx⟩  refine ⟨alg, halg_online, fun v hv i j hij g hg => ?_⟩  have h_nonneg : 0 ≤ additive_valuation (v i) ((bundle_of (alg v) j).erase g) := by    dsimp [additive_valuation]    apply Finset.sum_nonneg    intro x _    rcases hv i with ⟨g0, hg0, hrest⟩    by_cases hx : x = g0    · rw [hx, hg0]; exact hR    · rw [hrest x hx]; linarith  exact le_trans (mul_le_mul_of_nonneg_right hαβ h_nonneg) (halg_efx v hv i j hij g hg)
See it in the graphDiscuss this resultChallenge it