ef1_cost_gap_instance
def
The two-agent instance with costs (0, 1/2, 1/2) and (1/3 - 2d, 1/3 + d, 1/3 + d).
Statement
noncomputable def ef1_cost_gap_instance (δ : ℝ) : Fin 2 → Fin 3 → ℝ
- Source
- step towards cost_of_ef1_two_le / one_sixth_le_cost_of_ef1_two (cost of EF1 for two agents lies in [1/6, 3 - 2 sqrt 2]; A Fair Allocation is Approximately Optimal for Indivisible Chores, or Is It?, arXiv:2410.15738 v1, Thm 7 states the lower bound 1 - 1/n, whose construction needs n >= 3)
- Verified
- 06 Oct 2026
- Axioms
- none listed
- Used by 3
- one_sixth_le_cost_of_ef1_twoThe cost of EF1 for two agents is at least 1/6.
- cost_of_ef1_two_leThe cost of EF1 for two agents is at most 3 - 2 sqrt 2.
- ef1_cost_gap_instance_specIn the instance (0, 1/2, 1/2), (1/3 - 2d, 1/3 + d, 1/3 + d) with 0 < d <= 1/6, the optimal social cost is 2/3 + 2d and the best EF1 social…
Lean source view module on GitHub
/-- The two-agent instance with three chores attaining a gap of `1/6 - δ`: agent 0 has costs `(0, 1/2, 1/2)`, agent 1 has costs `(1/3 - 2δ, 1/3 + δ, 1/3 + δ)`. -/ noncomputable def ef1_cost_gap_instance (δ : ℝ) : Fin 2 → Fin 3 → ℝ := ![![0, 1/2, 1/2], ![1/3 - 2 * δ, 1/3 + δ, 1/3 + δ]]