wpropx_gadget_to_nat
lemmaverified
Weighted PROPX for natural-number costs cast to the reals with shares num_i/den implies its natural-number version multiplied through by den.
Statement
lemma wpropx_gadget_to_nat {m n : ℕ} (C : Fin n → Fin m → ℕ) (num : Fin n → ℕ) (den : ℕ) (hden : 0 < den) (σ : Fin m → Fin n) (h : is_weighted_propx_chores (fun i e => (C i e : ℝ)) (fun i => (num i : ℝ) / den) σ) : wpropx_gadget_wpropx_nat C num den σ
- 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
- 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.
- 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_bcAgent i's cost for her own bundle under an allocation, for natural-number costs.
- wpropx_gadget_totAgent i's cost for all chores, for natural-number costs.
- wpropx_gadget_wpropx_natWeighted PROPX for natural-number costs and shares num_i/den, multiplied through by den.
- Used by 1
- 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…
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.
lemma wpropx_gadget_to_nat {m n : ℕ} (C : Fin n → Fin m → ℕ) (num : Fin n → ℕ) (den : ℕ) (hden : 0 < den) (σ : Fin m → Fin n) (h : is_weighted_propx_chores (fun i e => (C i e : ℝ)) (fun i => (num i : ℝ) / den) σ) : wpropx_gadget_wpropx_nat C num den σ := by intro i e he have h1 := h i e he have hsplit : additive_valuation (fun e => (C i e : ℝ)) (bundle_of σ i \ {e}) = (wpropx_gadget_bc C σ i : ℝ) - C i e := by rw [Finset.sdiff_singleton_eq_erase] unfold additive_valuation wpropx_gadget_bc push_cast rw [Finset.sum_erase_eq_sub he] have htot : additive_valuation (fun e => (C i e : ℝ)) Finset.univ = (wpropx_gadget_tot C i : ℝ) := by unfold additive_valuation wpropx_gadget_tot; push_cast; rfl simp only at h1 rw [hsplit, htot, div_mul_eq_mul_div, le_div_iff₀ (by exact_mod_cast hden)] at h1 have : (den : ℝ) * wpropx_gadget_bc C σ i ≤ den * C i e + num i * wpropx_gadget_tot C i := by linarith exact_mod_cast this