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
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.
/-- 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'⟩