is_normalized_chores_instance
def
A chores instance is normalized if all costs are nonnegative and every agent's total cost is 1.
Statement
def is_normalized_chores_instance {m n : ℕ} (c : Fin n → Fin m → ℝ) : Prop
- Defined in
- A Fair Allocation is Approximately Optimal for Indivisible Chores, or Is It?, arXiv:2410.15738 v1, Sec. 2 (normalized additive costs, social cost, Def. 4 cost of fairness); formalized by the operator (Claude), 2026-10-03
- Verified
- 03 Oct 2026
- Axioms
- none listed
- Used by 6
- ef1_gap_set_two_agents_leThe set of gaps whose supremum is
cost_of_ef1 2is bounded by3 - 2√2. - 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.
- one_sixth_le_cost_of_ef1_twoThe cost of EF1 for two agents is at least 1/6.
- exists_ef1_social_cost_le_opt_add_two_agentsFor two agents with normalized additive chores, some EF1 allocation has social cost at most the optimum plus 3 - 2 sqrt 2.
- cost_of_ef1The cost of EF1 for n agents: the supremum over normalized instances of the minimum social cost of an EF1 allocation minus the optimal…
- 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…
- ef1_gap_set_two_agents_leThe set of gaps whose supremum is
Lean source view module on GitHub
/-- A chores instance in the model of arXiv:2410.15738 (Sec. 2): every cost is nonnegative and every agent's costs are normalised, `c i (O) = 1`. -/ def is_normalized_chores_instance {m n : ℕ} (c : Fin n → Fin m → ℝ) : Prop := (∀ i j, 0 ≤ c i j) ∧ ∀ i, ∑ j, c i j = 1