not_has_online_alpha_ef1_four_of_gt_one
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.
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.
intro h simp only [has_online_alpha_ef1_algorithm] at h rcases h with ⟨alg, _halg, hgood⟩
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.
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
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.
uses
Finset.card_eq_sum_card_fiberwise,Finset.mem_univ,Finset.card_univ,Fintype.card_finhave 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
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.
uses
Finset.sum_le_sum,Finset.sum_const,Finset.card_univ,Fintype.card_fin,smul_eq_mulhave 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
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.
uses
Finset.sum_le_sum,Nat.le_of_lt_succ,Finset.sum_const,Finset.card_univ,Fintype.card_fin,smul_eq_mul,mul_onehave 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
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.
uses
Finset.card_pos.mpobtain ⟨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)
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.
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
|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.
uses
Finset.card_erase_of_memhave 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
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.
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.
- The proof does not actually invoke the hypothesis that `alg` is an online algorithm (`_halg`). The impossibility holds even offline, because no allocation of 5 identical goods to 4 agents can satisfy α-EF1 when α > 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
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.
/-- 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]