pmms3c_verify_sound
theoremverified
If the certificate check accepts w for allocation σ, then σ is not PMMS for agent w mod 3.
Statement
theorem pmms3c_verify_sound (σ : Fin 9 → Fin 3) (w : ℕ) (h : pmms3c_verify σ w = true) : ¬ is_pmms_fair_chores (fun i g => (pmms3c_cost i g : ℝ)) σ (pmms3c_agent_of w)
- Source
- step towards pmms_chores_three_agents_may_not_exist (three-agent chores PMMS, not posed in arXiv:2609.10493): certificate checker and its soundness
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 7
- pmms3c_verifyChecks a violation certificate w = i + 3j + 9T for allocation σ: i ≠ j, the bitmask T lies inside X_i ∪ X_j, and both T and (X_i ∪ X_j) \…
- is_pmms_fair_choresPairwise maximin share (PMMS) for chores: allocation σ is PMMS for agent i if, for every other agent j and every way of splitting X_i ∪…
- pmms3c_cost_nat_eqThe fold computing agent i's cost of the chores selected by P agrees with the additive cost of that set.
- 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.
- pmms3c_costInteger costs of three agents for nine chores: agent 0 (21,38,28,24,20,35,29,41,18), agent 1 (15,41,27,25,23,26,28,35,21), agent 2…
- pmms3c_agent_ofThe agent w mod 3.
- pmms3c_cost_natThe cost to agent i of the set of chores {g : P g}, as a natural number.
- Used by 1
- pmms_chores_three_agents_may_not_existPMMS allocations of chores need not exist already for three agents: there are strictly positive additive costs of three agents for nine…
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 pmms3c_verify_sound (σ : Fin 9 → Fin 3) (w : ℕ) (h : pmms3c_verify σ w = true) : ¬ is_pmms_fair_chores (fun i g => (pmms3c_cost i g : ℝ)) σ (pmms3c_agent_of w) := by unfold pmms3c_verify at h simp only [Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true, List.mem_finRange, true_implies, Bool.or_eq_true, Bool.not_eq_true', beq_iff_eq] at h obtain ⟨⟨hij, hsub⟩, hlt⟩ := h intro hp set i := pmms3c_agent_of w set j := pmms3c_agent_of (w / 3) set m := w / 9 have hT : (Finset.univ.filter fun g : Fin 9 => m.testBit g = true) ⊆ bundle_of σ i ∪ bundle_of σ j := by intro g hg simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hg simp only [bundle_of, Finset.mem_union, Finset.mem_filter, Finset.mem_univ, true_and] simpa [hg] using hsub g have key := hp j (Ne.symm hij) _ hT have e1 : bundle_of σ i = Finset.univ.filter fun g => (σ g == i) = true := by ext g; simp [bundle_of] have e2 : (bundle_of σ i ∪ bundle_of σ j) \ (Finset.univ.filter fun g : Fin 9 => m.testBit g = true) = Finset.univ.filter fun g => ((σ g == i || σ g == j) && !(m.testBit g)) = true := by ext g; simp [bundle_of] rw [e2, e1, ← pmms3c_cost_nat_eq, ← pmms3c_cost_nat_eq, ← pmms3c_cost_nat_eq] at key have : (max (pmms3c_cost_nat i fun g => m.testBit g) (pmms3c_cost_nat i fun g => (σ g == i || σ g == j) && !(m.testBit g)) : ℝ) < (pmms3c_cost_nat i fun g => σ g == i : ℝ) := by exact_mod_cast hlt linarith