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
- weighted_propx_po_chores_incompatible_three_seventhsFor two agents with shares (3/7, 4/7), six chores and strictly positive additive costs (262,111,258,100,1,103) and (135,75,113,1,43,53),…
- weighted_propx_po_chores_incompatible_nine_twentiethsFor two agents with shares (9/20, 11/20), six chores and strictly positive additive costs (114,222,1,177,64,166) and…
- weighted_propx_po_chores_incompatible_two_fifthsFor 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…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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τ⟩