AFTD Auto-Formalizing Theoretical Domains

exists_ef1_social_cost_le_opt_add_two_agents

theoremverifiedoriginal

For two agents with normalized additive chores, some EF1 allocation has social cost at most the optimum plus 3 - 2 sqrt 2.

Statement

theorem exists_ef1_social_cost_le_opt_add_two_agents {m : ℕ} (c : Fin 2 → Fin m → ℝ)
    (hc : is_normalized_chores_instance c) :
    ∃ σ, is_ef1_chores c σ ∧ ∀ τ, social_cost c σ ≤ social_cost c τ + (3 - 2 * Real.sqrt 2)
Related work
operator (Claude), 2026-10-03: the cost of EF1 for two agents lies in [1/6, 3 - 2 sqrt 2], refuting the lower bound 1 - 1/n of arXiv:2410.15738 v1, Thm 7, at n = 2 (its construction needs a third agent)
Verified
03 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 10
  • ef1cost_alpha_pos3 - 2 sqrt 2 is positive.
  • ef1cost_coreCore lemma (greedy transfer by cost ratio). Agent P (costs u) holds X, agent Q (costs v) holds Xᶜ; every chore is held by an…
  • ef1cost_ef1_of_pairBridging: an EF1 two-bundle split gives an EF1 allocation in the sense of is_ef1_chores.
  • ef1cost_from_coreFrom the core lemma to an EF1 allocation within 3 - 2√2 of the optimum.
  • ef1cost_opt_leFor two agents, giving each item to agent 0 when c_0 <= c_1 and to agent 1 otherwise minimises the item-wise cost sum.
  • ef1cost_pair_okTwo-bundle EF1 condition: the owner of A, with costs w, is EF1 towards B.
  • ef1cost_social_cost_eqThe social cost of an allocation equals the sum over items of the cost of each item to its owner.
  • is_ef1_choresEF1 for chores with additive costs: whenever agent i envies agent j, removing some chore from i's own bundle removes the envy.
  • is_normalized_chores_instanceA chores instance is normalized if all costs are nonnegative and every agent's total cost is 1.
  • social_costThe social cost of an allocation: the sum over agents of their cost for their own bundle.
Used by 1
  • ef1_gap_le_two_agentsFor two agents with normalized additive chores, the best EF1 social cost exceeds the optimal social cost by at most 3 - 2 sqrt 2.

Lean source view module on GitHub

/-- **Upper bound for two agents.** In every normalised two-agent chores instance (any number of chores) there is an EF1 allocation whose social cost exceeds the optimum by at most `3 - 2√2 ≈ 0.1716`. -/theorem exists_ef1_social_cost_le_opt_add_two_agents {m : ℕ} (c : Fin 2 → Fin m → ℝ)    (hc : is_normalized_chores_instance c) :    ∃ σ, is_ef1_chores c σ ∧ ∀ τ, social_cost c σ ≤ social_cost c τ + (3 - 2 * Real.sqrt 2) := by  classical  obtain ⟨hc0, hc1⟩ := hc  set X : Finset (Fin m) := Finset.univ.filter (fun j => c 0 j ≤ c 1 j) with hXdef  have hmemX : ∀ j, j ∈ X ↔ c 0 j ≤ c 1 j := by intro j; simp [hXdef]  have hσ0 : ∀ j, (if c 0 j ≤ c 1 j then (0 : Fin 2) else 1) = if j ∈ X then 0 else 1 := by    intro j; simp only [hmemX]  have hopt0 : ∀ τ : Fin m → Fin 2, ∑ j, c (if j ∈ X then 0 else 1) j ≤ ∑ j, c (τ j) j := by    intro τ    have := ef1cost_opt_le c τ    simp only [hσ0] at this    exact this  by_cases hQ : ef1cost_pair_ok (c 1) Xᶜ X  · by_cases hP : ef1cost_pair_ok (c 0) X Xᶜ    · -- the optimum itself is EF1      refine ⟨fun j => if j ∈ X then 0 else 1, ef1cost_ef1_of_pair c 0 1 (by decide) X hP hQ,        fun τ => ?_⟩      rw [ef1cost_social_cost_eq, ef1cost_social_cost_eq]      linarith [hopt0 τ, ef1cost_alpha_pos]    · -- agent 0 is not EF1: transfer from agent 0 to agent 1      have hcore := ef1cost_core (c 1) (c 0) (hc0 1) (hc0 0) (hc1 1) (hc1 0) Xᶜ        (fun j hj => by          rw [Finset.mem_compl, hmemX] at hj; linarith)        (fun j hj => by          rw [Finset.mem_compl, not_not, hmemX] at hj; exact hj)        (by have hXX : Xᶜᶜ = X := compl_compl X; rw [hXX]; exact hP)      refine ef1cost_from_core c 1 0 (by decide) Xᶜ (fun τ => ?_) hcore      have := hopt0 τ      have e : ∀ j, (if j ∈ Xᶜ then (1 : Fin 2) else 0) = if j ∈ X then 0 else 1 := by        intro j        by_cases h : j ∈ X <;> simp [h]      simp only [e]      exact this  · -- agent 1 is not EF1: transfer from agent 1 to agent 0    have hcore := ef1cost_core (c 0) (c 1) (hc0 0) (hc0 1) (hc1 0) (hc1 1) X      (fun j hj => (hmemX j).mp hj)      (fun j hj => by rw [hmemX] at hj; linarith)      hQ    exact ef1cost_from_core c 0 1 (by decide) X hopt0 hcore
See it in the graphDiscuss this resultChallenge it