AFTD Auto-Formalizing Theoretical Domains

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

Lean source view module on GitHub

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
See it in the graphDiscuss this resultChallenge it