AFTD Auto-Formalizing Theoretical Domains

no_weighted_propx_po_of_nat_check

theoremverified

Reduction for kernel checking: if, for natural-number costs C and shares num/den, every allocation that is weighted PROPX (multiplied through by den) is Pareto-dominated in N, then no allocation is weighted PROPX and Pareto optimal for the real costs.

Statement

theorem no_weighted_propx_po_of_nat_check {m n : ℕ} (C : Fin n → Fin m → ℕ) (num : Fin n → ℕ) (den : ℕ)
    (hden : 0 < den)
    (hok : ∀ σ, wpropx_gadget_wpropx_nat C num den σ → ∃ τ, wpropx_gadget_dom C τ σ) :
    ¬ ∃ σ, is_weighted_propx_chores (fun i e => (C i e : ℝ)) (fun i => (num i : ℝ) / den) σ ∧
      is_pareto_optimal_chores (fun i e => (C i e : ℝ)) σ
Source
step towards weighted_propx_po_chores_incompatible_two_fifths / _nine_twentieths / _three_sevenths (two-agent weighted PROPX + PO counterexamples, arXiv:2608.16130 v1 (its Thm 3.1 covers shares (3/10, 7/10) only))
Verified
06 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • is_pareto_optimal_choresAn allocation of chores is Pareto optimal if no allocation Pareto-dominates it.
  • 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…
  • wpropx_gadget_domPareto domination between allocations for natural-number costs.
  • wpropx_gadget_of_domPareto domination for natural-number costs implies Pareto domination for the costs cast to the reals.
  • wpropx_gadget_to_natWeighted PROPX for natural-number costs cast to the reals with shares num_i/den implies its natural-number version multiplied through by…
  • wpropx_gadget_wpropx_natWeighted PROPX for natural-number costs and shares num_i/den, multiplied through by den.
Used by 3

Lean source view module on GitHub

theorem no_weighted_propx_po_of_nat_check {m n : ℕ} (C : Fin n → Fin m → ℕ) (num : Fin n → ℕ) (den : ℕ)    (hden : 0 < den)    (hok : ∀ σ, wpropx_gadget_wpropx_nat C num den σ → ∃ τ, wpropx_gadget_dom C τ σ) :    ¬ ∃ σ, is_weighted_propx_chores (fun i e => (C i e : ℝ)) (fun i => (num i : ℝ) / den) σ ∧      is_pareto_optimal_chores (fun i e => (C i e : ℝ)) σ := by  rintro ⟨σ, hw, hpo⟩  obtain ⟨τ, hτ⟩ := hok σ (wpropx_gadget_to_nat C num den hden σ hw)  exact hpo ⟨τ, wpropx_gadget_of_dom C τ σ hτ⟩
See it in the graphDiscuss this resultChallenge it