AFTD Auto-Formalizing Theoretical Domains

weighted_propx_po_chores_incompatible_two_fifths

theoremverifiedoriginal

For two agents with shares (2/5, 3/5), five chores and strictly positive additive costs (38,1,111,72,48) and (31,54,113,40,1), no allocation is weighted PROPX and Pareto optimal.

Statement

theorem weighted_propx_po_chores_incompatible_two_fifths :
    ∃ c : Fin 2 → Fin 5 → ℝ, (∀ i e, 0 < c i e) ∧
      ¬ ∃ σ : Fin 5 → Fin 2, is_weighted_propx_chores c ![2 / 5, 3 / 5] σ ∧
        is_pareto_optimal_chores c σ
Related work
operator (Claude), 2026-10-03: two-agent counterexamples to weighted PROPX + PO for share vectors not covered by arXiv:2608.16130 v1 (Thm 3.1 covers (3/10, 7/10) only; Thm 3.2 needs n >= 3); found by a search agent, checked independently in exact arithmetic and in the Lean kernel
Verified
03 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • no_weighted_propx_po_of_nat_checkReduction for kernel checking: if, for natural-number costs C and shares num/den, every allocation that is weighted PROPX (multiplied…
  • is_weighted_propx_choresWeighted PROPX for chores (zero-tolerant): for every agent i and every chore e in her bundle, her cost for the bundle without e is at most…
  • is_pareto_optimal_choresAn allocation of chores is Pareto optimal if no allocation Pareto-dominates it.
  • wpropx_gadget_wpropx_natWeighted PROPX for natural-number costs and shares num_i/den, multiplied through by den.
  • wpropx_gadget_domPareto domination between allocations for natural-number costs.

Lean source view module on GitHub

/-- Costs: agent 0 pays (38, 1, 111, 72, 48), agent 1 pays (31, 54, 113, 40, 1). -/def wpropx_gadget_cost_a : Fin 2 → Fin 5 → ℕ :=  ![![38, 1, 111, 72, 48], ![31, 54, 113, 40, 1]]/-- The only weighted PROPX allocations, (0,0,1,1,0) with costs (87, 153) and (1,1,0,1,1) withcosts (111, 126), are dominated by (1,0,1,0,1) with costs (73, 145) and (0,0,1,0,1) with costs(111, 114). -/def wpropx_gadget_ok_a (σ : Fin 5 → Fin 2) : Prop :=  wpropx_gadget_wpropx_nat wpropx_gadget_cost_a ![2, 3] 5 σ →    wpropx_gadget_dom wpropx_gadget_cost_a ![1, 0, 1, 0, 1] σ ∨      wpropx_gadget_dom wpropx_gadget_cost_a ![0, 0, 1, 0, 1] σinstance wpropx_gadget_ok_a_decidable : DecidablePred wpropx_gadget_ok_a := fun σ => by  unfold wpropx_gadget_ok_a; infer_instance/-- Kernel check over all 32 allocations. -/lemma wpropx_gadget_check_a : ∀ a b c d e : Fin 2, wpropx_gadget_ok_a ![a, b, c, d, e] := by  decidetheorem weighted_propx_po_chores_incompatible_two_fifths :    ∃ c : Fin 2 → Fin 5 → ℝ, (∀ i e, 0 < c i e) ∧      ¬ ∃ σ : Fin 5 → Fin 2, is_weighted_propx_chores c ![2 / 5, 3 / 5] σ ∧        is_pareto_optimal_chores c σ := by  refine ⟨fun i e => (wpropx_gadget_cost_a i e : ℝ), fun i e => ?_, ?_⟩  · have : 0 < wpropx_gadget_cost_a i e := by revert i e; decide    show (0 : ℝ) < (wpropx_gadget_cost_a i e : ℝ)    exact_mod_cast this  have hw : (![2 / 5, 3 / 5] : Fin 2 → ℝ) =      fun i => (((![2, 3] : Fin 2 → ℕ) i : ℕ) : ℝ) / ((5 : ℕ) : ℝ) := by    funext i; fin_cases i <;> norm_num  rw [hw]  refine no_weighted_propx_po_of_nat_check _ _ _ (by norm_num) fun σ h => ?_  have hσ : σ = ![σ 0, σ 1, σ 2, σ 3, σ 4] := by funext x; fin_cases x <;> rfl  have hc := wpropx_gadget_check_a (σ 0) (σ 1) (σ 2) (σ 3) (σ 4)  rw [← hσ] at hc  rcases hc h with h' | h'  · exact ⟨_, h'⟩  · exact ⟨_, h'⟩
See it in the graphDiscuss this resultChallenge it