AFTD Auto-Formalizing Theoretical Domains

connected_ef1_po_chores_incompatible

theoremverifiedoriginal

For chores on a path with additive, strictly positive costs, EF1 and Pareto optimality (among connected allocations) can be incompatible: with three agents and five chores, costs (4,2,1,2,2) for agent 0 and (1,4,1,2,2) for agents 1 and 2, each of the 12 connected EF1 allocations is Pareto-dominated by a connected allocation with cost vector (5,1,2), (2,1,5) or (2,5,1). Since EF1outer implies EF1, EF1outer and PO are incompatible as well.

Statement

theorem connected_ef1_po_chores_incompatible :
    ∃ c : Fin 3 → Fin 5 → ℝ, (∀ i e, 0 < c i e) ∧
      ¬ ∃ σ : Fin 5 → Fin 3,
        is_connected_allocation σ ∧ is_ef1_chores c σ ∧ is_connected_po_chores c σ
Related work
operator (Claude), 2026-10-03: answers the question of arXiv:2609.32545 v1, Sec. 4 (are EF1 and PO compatible for connected chores?) negatively; counterexample found by a search agent, checked independently and in the Lean kernel
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • is_connected_allocationAn allocation is connected if every agent's bundle is connected on the path.
  • 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_connected_po_choresAn allocation of chores is Pareto optimal among connected allocations if no connected allocation costs every agent at most as much and…
  • 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.

Lean source view module on GitHub

/-- Costs of the counterexample: agent 0 pays (4, 2, 1, 2, 2), agents 1 and 2 pay (1, 4, 1, 2, 2). -/def chores_path_cost : Fin 3 → Fin 5 → ℕ :=  ![![4, 2, 1, 2, 2], ![1, 4, 1, 2, 2], ![1, 4, 1, 2, 2]]/-- Agent `i`'s cost for agent `k`'s bundle under `σ`, in `ℕ`. -/abbrev chores_path_bc (σ : Fin 5 → Fin 3) (i k : Fin 3) : ℕ :=  ∑ e ∈ bundle_of σ k, chores_path_cost i e/-- `τ` Pareto-dominates `σ` for the costs `chores_path_cost`. -/abbrev chores_path_dom (τ σ : Fin 5 → Fin 3) : Prop :=  (∀ i, chores_path_bc τ i i ≤ chores_path_bc σ i i) ∧ ∃ i, chores_path_bc τ i i < chores_path_bc σ i i/-- Connectedness of an allocation of the five chores, spelled out over `Fin 5`. -/lemma chores_path_conn_iff (σ : Fin 5 → Fin 3) : is_connected_allocation σ ↔    ∀ i : Fin 3, ∀ x ∈ bundle_of σ i, ∀ y ∈ bundle_of σ i, ∀ z : Fin 5,      x ≤ z → z ≤ y → z ∈ bundle_of σ i := Iff.rfl/-- The property checked for each allocation `σ` of the five chores: if `σ` is connected andEF1, one of three connected allocations, with cost vectors (5, 1, 2), (2, 1, 5) and (2, 5, 1),Pareto-dominates it. -/def chores_path_ok (σ : Fin 5 → Fin 3) : Prop :=  (∀ i : Fin 3, ∀ x ∈ bundle_of σ i, ∀ y ∈ bundle_of σ i, ∀ z : Fin 5,      x ≤ z → z ≤ y → z ∈ bundle_of σ i) →    (∀ i j, chores_path_bc σ i i ≤ chores_path_bc σ i j ∨      ∃ x ∈ bundle_of σ i, chores_path_bc σ i i ≤ chores_path_cost i x + chores_path_bc σ i j) →    chores_path_dom ![1, 0, 0, 0, 2] σ ∨ chores_path_dom ![1, 0, 2, 2, 2] σ ∨      chores_path_dom ![2, 0, 1, 1, 1] σinstance chores_path_ok_decidable : DecidablePred chores_path_ok := fun σ => by  unfold chores_path_ok; infer_instance/-- The kernel check, over all 243 allocations. -/lemma chores_path_check : ∀ a b c d e : Fin 3, chores_path_ok ![a, b, c, d, e] := by  decidetheorem connected_ef1_po_chores_incompatible :    ∃ c : Fin 3 → Fin 5 → ℝ, (∀ i e, 0 < c i e) ∧      ¬ ∃ σ : Fin 5 → Fin 3,        is_connected_allocation σ ∧ is_ef1_chores c σ ∧ is_connected_po_chores c σ := by  refine ⟨fun i e => (chores_path_cost i e : ℝ), fun i e => ?_, ?_⟩  · have : 0 < chores_path_cost i e := by revert i e; decide    show (0 : ℝ) < (chores_path_cost i e : ℝ)    exact_mod_cast this  rintro ⟨σ, hconn, hef1, hpo⟩  have hav : ∀ τ : Fin 5 → Fin 3, ∀ i k, additive_valuation (fun e => (chores_path_cost i e : ℝ))      (bundle_of τ k) = (chores_path_bc τ i k : ℝ) := by    intro τ i k; simp [additive_valuation, chores_path_bc]  have hσ : σ = ![σ 0, σ 1, σ 2, σ 3, σ 4] := by    funext x; fin_cases x <;> rfl  have hef : ∀ i j, chores_path_bc σ i i ≤ chores_path_bc σ i j ∨      ∃ x ∈ bundle_of σ i, chores_path_bc σ i i ≤ chores_path_cost i x + chores_path_bc σ i j := by    intro i j    rcases hef1 i j with h | ⟨x, hx, h⟩    · left; rw [hav, hav] at h; exact_mod_cast h    · right; refine ⟨x, hx, ?_⟩      rw [hav, hav] at h      have : (chores_path_bc σ i i : ℝ) ≤ (chores_path_cost i x : ℝ) + chores_path_bc σ i j := by        linarith      exact_mod_cast this  rw [hσ] at hconn hef  have hdom := chores_path_check _ _ _ _ _ ((chores_path_conn_iff _).1 hconn) hef  rw [← hσ] at hdom  apply hpo  have lift : ∀ τ, is_connected_allocation τ → chores_path_dom τ σ →      ∃ τ, is_connected_allocation τ ∧        (∀ i, additive_valuation (fun e => (chores_path_cost i e : ℝ)) (bundle_of τ i) ≤          additive_valuation (fun e => (chores_path_cost i e : ℝ)) (bundle_of σ i)) ∧        ∃ i, additive_valuation (fun e => (chores_path_cost i e : ℝ)) (bundle_of τ i) <          additive_valuation (fun e => (chores_path_cost i e : ℝ)) (bundle_of σ i) := by    rintro τ hτ ⟨hle, i, hlt⟩    refine ⟨τ, hτ, fun k => ?_, i, ?_⟩    · rw [hav, hav]; exact_mod_cast hle k    · rw [hav, hav]; exact_mod_cast hlt  rcases hdom with h | h | h  · exact lift _ ((chores_path_conn_iff _).2 (by decide)) h  · exact lift _ ((chores_path_conn_iff _).2 (by decide)) h  · exact lift _ ((chores_path_conn_iff _).2 (by decide)) h
See it in the graphDiscuss this resultChallenge it