AFTD Auto-Formalizing Theoretical Domains

not_has_online_alpha_ef1_four_of_gt_one

theoremverified

For any alpha > 1, there is no deterministic online algorithm guaranteeing an alpha-EF1 allocation for four agents under exact frequency predictions.

Statement

theorem not_has_online_alpha_ef1_four_of_gt_one {α : ℝ} (hα : 1 < α) :
    ¬ has_online_alpha_ef1_algorithm 4 α
Source
step towards op561_tight_ef1_factor_four_agents
Verified
28 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • has_online_alpha_ef1_algorithmThere exists a deterministic online algorithm for n agents that, for any number of goods m, given exact frequency predictions a_hat and…
  • is_exact_predictionFrequency predictions a_hat : Fin n → Fin m → ℝ are exact for valuations v : Fin n → Fin m → ℝ if for every agent i : Fin n, the sorted…
  • 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.
  • sorted_tupleFor any tuple u : Fin m → ℝ, its sorted tuple is u ∘ Tuple.sort u, which reorders the values of u in nondecreasing order.
  • is_online_algorithmFor an allocation algorithm alg taking a number of goods m : ℕ, predicted valuation profiles a_hat : Fin n → Fin m → ℝ, and true valuation…
  • is_alpha_ef1_goodsAn allocation of m indivisible goods to n agents is alpha-EF1 under additive valuations u if for every pair of distinct agents i and j…

The proof, explained

The theorem is proved by contradiction by testing the hypothetical algorithm on an instance with 4 agents and 5 items, all valued at 1, under exact predictions. By the pigeonhole principle, any allocation of 5 items to 4 agents must give some agent i at most 1 item and another agent j at least 2 items. The α-EF1 condition implies that removing an item from agent j's bundle leaves its value bounded by 1/α times agent i's bundle value; since the remaining bundle has at least 1 item and agent i has at most 1 item, this forces α ≤ 1, contradicting α > 1.

  1. Assume for contradiction that there exists an online α-EF1 algorithm for four agents.

    We assume the negation of the theorem and unfold the definition of `has_online_alpha_ef1_algorithm`. This provides an algorithm `alg` guaranteed to output an α-EF1 allocation on any instance with exact predictions.

    lines 4–6

      intro h
      simp only [has_online_alpha_ef1_algorithm] at h
      rcases h with ⟨alg, _halg, hgood⟩
  2. Running the algorithm on 5 items where every agent values every item at 1 yields an α-EF1 allocation σ.

    We specialize the algorithm's guarantee to 5 goods with all valuations and predicted values identically equal to 1. The non-negativity of valuations holds trivially, and the prediction is exact by reflexivity. Unfolding the definition of `is_alpha_ef1_goods`, the resulting allocation σ : Fin 5 → Fin 4 satisfies the α-EF1 property.

    lines 7–10

      let σ : Fin 5 → Fin 4 := alg 5 (fun _ _ => (1:ℝ)) (fun _ _ => (1:ℝ))
      have hEF1 : is_alpha_ef1_goods (fun _ _ => (1:ℝ)) α σ :=
        hgood 5 (fun _ _ => (1:ℝ)) (fun _ _ => (1:ℝ)) (by intro i g; norm_num) (by intro i; rfl)
      simp only [is_alpha_ef1_goods] at hEF1
  3. The sum of the four bundle sizes is 5.

    By partitioning the 5 items into fibers according to which agent receives them (`Finset.card_eq_sum_card_fiberwise`), the total number of items equals the sum of the cardinalities of the four bundles.

    lines 11–14

    uses Finset.card_eq_sum_card_fiberwise, Finset.mem_univ, Finset.card_univ, Fintype.card_fin

      have hsum : ∑ j : Fin 4, (bundle_of σ j).card = 5 := by
        have h := Finset.card_eq_sum_card_fiberwise (s := (Finset.univ : Finset (Fin 5)))
          (f := σ) (t := (Finset.univ : Finset (Fin 4))) (by intro x _; exact Finset.mem_univ _)
        simpa [bundle_of, Finset.card_univ, Fintype.card_fin] using h.symm
  4. There exists an agent i receiving at most 1 item.

    If every agent received at least 2 items, the sum of bundle sizes would be at least 4 × 2 = 8 items, contradicting the fact that there are only 5 items in total. Linear integer arithmetic (`omega`) closes this contradiction.

    lines 15–23

    uses Finset.sum_le_sum, Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul

      have hex_i : ∃ i : Fin 4, (bundle_of σ i).card ≤ 1 := by
        by_contra hc
        push_neg at hc
        have hle : ∑ j : Fin 4, (2:ℕ) ≤ ∑ j : Fin 4, (bundle_of σ j).card := by
          apply Finset.sum_le_sum
          intro j _
          exact hc j
        simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul] at hle
        omega
  5. There exists an agent j receiving at least 2 items.

    If every agent received strictly fewer than 2 items (at most 1 item each), the sum of bundle sizes would be at most 4 × 1 = 4 items, contradicting the total of 5 items. Linear integer arithmetic (`omega`) closes this contradiction.

    lines 24–32

    uses Finset.sum_le_sum, Nat.le_of_lt_succ, Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul, mul_one

      have hex_j : ∃ j : Fin 4, 2 ≤ (bundle_of σ j).card := by
        by_contra hc
        push_neg at hc
        have hle : ∑ j : Fin 4, (bundle_of σ j).card ≤ ∑ j : Fin 4, (1:ℕ) := by
          apply Finset.sum_le_sum
          intro j _
          exact Nat.le_of_lt_succ (hc j)
        simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul, mul_one] at hle
        omega
  6. The agents i and j are distinct, and agent j's bundle is nonempty.

    Since agent i receives at most 1 item and agent j receives at least 2 items, they cannot be the same agent. Moreover, agent j's bundle size is at least 2 > 0, so it is nonempty.

    lines 33–39

    uses Finset.card_pos.mp

      obtain ⟨i, hi⟩ := hex_i
      obtain ⟨j, hj⟩ := hex_j
      have hne : i ≠ j := by
        intro heq
        rw [heq] at hi
        omega
      have hnonempty : (bundle_of σ j).Nonempty := Finset.card_pos.mp (by omega)
  7. There is an item g in agent j's bundle such that α · |bundle(j) \ {g}| ≤ |bundle(i)|.

    Applying the α-EF1 condition between distinct agents i and j gives an item g in j's bundle such that α times the valuation of bundle(j) \ {g} is at most the valuation of bundle(i). Because all valuations are identically 1, the additive valuation of any set of items is simply its cardinality.

    lines 40–47

      obtain ⟨g, hg, hineq⟩ := hEF1 i j hne hnonempty
      have hval_erase : additive_valuation (fun x : Fin 5 => (1:ℝ)) ((bundle_of σ j).erase g)
          = (((bundle_of σ j).erase g).card : ℝ) := by
        simp [additive_valuation]
      have hval_i : additive_valuation (fun x : Fin 5 => (1:ℝ)) (bundle_of σ i)
          = ((bundle_of σ i).card : ℝ) := by
        simp [additive_valuation]
      simp only [hval_erase, hval_i] at hineq
  8. |bundle(j) \ {g}| ≥ 1 and |bundle(i)| ≤ 1 over the real numbers.

    Because g is in bundle(j) and |bundle(j)| ≥ 2, removing g leaves at least 2 - 1 = 1 item by `Finset.card_erase_of_mem`. Casting this inequality and |bundle(i)| ≤ 1 to the real numbers gives the required bounds.

    lines 48–54

    uses Finset.card_erase_of_mem

      have hcard_erase : (1:ℝ) ≤ (((bundle_of σ j).erase g).card : ℝ) := by
        have h1 : 1 ≤ ((bundle_of σ j).erase g).card := by
          rw [Finset.card_erase_of_mem hg]
          omega
        exact_mod_cast h1
      have hcard_i : ((bundle_of σ i).card : ℝ) ≤ 1 := by
        exact_mod_cast hi
  9. A contradiction is reached, concluding the proof.

    Combining α · |bundle(j) \ {g}| ≤ |bundle(i)| with 1 ≤ |bundle(j) \ {g}| and |bundle(i)| ≤ 1 yields α ≤ 1, which directly contradicts the hypothesis that 1 < α. Non-linear arithmetic (`nlinarith`) closes the goal.

    line 55

      nlinarith [hineq, hα, hcard_erase, hcard_i]
Finset.card_eq_sum_card_fiberwise
For any mapping f : s → t between finite sets, the size of s is the sum over b ∈ t of the sizes of the preimages (fibers) f⁻¹(b) ∩ s.
Finset.mem_univ
Every element of a finite type belongs to the universal finset `Finset.univ`.
Finset.card_univ
The cardinality of the universal finset of a finite type equals the cardinality of the type.
Fintype.card_fin
The cardinality of `Fin n` is n.
Finset.sum_le_sum
A sum of values indexed by a finite set is bounded by the sum of pointwise upper bounds.
Finset.sum_const
Summing a constant over a finite set equals the cardinality of the set multiplied by the constant.
smul_eq_mul
Scalar multiplication by a natural number equals standard multiplication.
Nat.le_of_lt_succ
If m < n + 1 for natural numbers m and n, then m ≤ n.
mul_one
Multiplying a number by 1 leaves it unchanged.
Finset.card_pos.mp
A finite set with strictly positive cardinality is nonempty.
Finset.card_erase_of_mem
Removing an element present in a finite set decreases its cardinality by 1.

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

/-- No online algorithm can guarantee an alpha-EF1 allocation for four agents when alpha > 1. -/theorem not_has_online_alpha_ef1_four_of_gt_one {α : ℝ} (hα : 1 < α) :    ¬ has_online_alpha_ef1_algorithm 4 α := by  intro h  simp only [has_online_alpha_ef1_algorithm] at h  rcases h with ⟨alg, _halg, hgood⟩  let σ : Fin 5 → Fin 4 := alg 5 (fun _ _ => (1:ℝ)) (fun _ _ => (1:ℝ))  have hEF1 : is_alpha_ef1_goods (fun _ _ => (1:ℝ)) α σ :=    hgood 5 (fun _ _ => (1:ℝ)) (fun _ _ => (1:ℝ)) (by intro i g; norm_num) (by intro i; rfl)  simp only [is_alpha_ef1_goods] at hEF1  have hsum : ∑ j : Fin 4, (bundle_of σ j).card = 5 := by    have h := Finset.card_eq_sum_card_fiberwise (s := (Finset.univ : Finset (Fin 5)))      (f := σ) (t := (Finset.univ : Finset (Fin 4))) (by intro x _; exact Finset.mem_univ _)    simpa [bundle_of, Finset.card_univ, Fintype.card_fin] using h.symm  have hex_i : ∃ i : Fin 4, (bundle_of σ i).card ≤ 1 := by    by_contra hc    push_neg at hc    have hle : ∑ j : Fin 4, (2:ℕ) ≤ ∑ j : Fin 4, (bundle_of σ j).card := by      apply Finset.sum_le_sum      intro j _      exact hc j    simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul] at hle    omega  have hex_j : ∃ j : Fin 4, 2 ≤ (bundle_of σ j).card := by    by_contra hc    push_neg at hc    have hle : ∑ j : Fin 4, (bundle_of σ j).card ≤ ∑ j : Fin 4, (1:ℕ) := by      apply Finset.sum_le_sum      intro j _      exact Nat.le_of_lt_succ (hc j)    simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul, mul_one] at hle    omega  obtain ⟨i, hi⟩ := hex_i  obtain ⟨j, hj⟩ := hex_j  have hne : i ≠ j := by    intro heq    rw [heq] at hi    omega  have hnonempty : (bundle_of σ j).Nonempty := Finset.card_pos.mp (by omega)  obtain ⟨g, hg, hineq⟩ := hEF1 i j hne hnonempty  have hval_erase : additive_valuation (fun x : Fin 5 => (1:ℝ)) ((bundle_of σ j).erase g)      = (((bundle_of σ j).erase g).card : ℝ) := by    simp [additive_valuation]  have hval_i : additive_valuation (fun x : Fin 5 => (1:ℝ)) (bundle_of σ i)      = ((bundle_of σ i).card : ℝ) := by    simp [additive_valuation]  simp only [hval_erase, hval_i] at hineq  have hcard_erase : (1:ℝ) ≤ (((bundle_of σ j).erase g).card : ℝ) := by    have h1 : 1 ≤ ((bundle_of σ j).erase g).card := by      rw [Finset.card_erase_of_mem hg]      omega    exact_mod_cast h1  have hcard_i : ((bundle_of σ i).card : ℝ) ≤ 1 := by    exact_mod_cast hi  nlinarith [hineq, hα, hcard_erase, hcard_i]
See it in the graphDiscuss this resultChallenge it