AFTD Auto-Formalizing Theoretical Domains

pmms3c_verify

def

Checks 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) \ T cost agent i strictly less than X_i.

Statement

def pmms3c_verify (σ : Fin 9 → Fin 3) (w : ℕ) : Bool
Source
step towards pmms_chores_three_agents_may_not_exist (three-agent chores PMMS, not posed in arXiv:2609.10493) (violation-certificate machinery and instance data)
Verified
26 Oct 2026
Axioms
none listed
Built on 2
Used by 29
  • pmms3c_check_022Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 0, 2, 2.
  • pmms3c_check_122Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 1, 2, 2.
  • pmms3c_check_200Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 2, 0, 0.
  • pmms3c_checkEvery one of the 3^9 allocations passes the certificate check.
  • pmms3c_verify_soundIf the certificate check accepts w for allocation σ, then σ is not PMMS for agent w mod 3.
  • pmms3c_check_220Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 2, 2, 0.
  • pmms3c_check_002Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 0, 0, 2.
  • pmms3c_check_011Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 0, 1, 1.
  • pmms3c_check_020Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 0, 2, 0.
  • pmms3c_check_010Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 0, 1, 0.
  • pmms3c_check_210Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 2, 1, 0.
  • pmms3c_check_211Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 2, 1, 1.
  • pmms3c_check_001Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 0, 0, 1.
  • pmms3c_check_111Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 1, 1, 1.
  • pmms3c_check_120Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 1, 2, 0.
  • pmms3c_check_112Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 1, 1, 2.
  • pmms3c_check_121Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 1, 2, 1.
  • pmms3c_check_202Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 2, 0, 2.
  • pmms3c_check_201Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 2, 0, 1.
  • pmms3c_check_021Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 0, 2, 1.
  • pmms3c_check_110Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 1, 1, 0.
  • pmms3c_check_100Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 1, 0, 0.
  • pmms3c_check_102Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 1, 0, 2.
  • pmms3c_check_212Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 2, 1, 2.
  • pmms3c_check_222Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 2, 2, 2.
  • pmms3c_check_101Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 1, 0, 1.
  • pmms3c_check_221Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 2, 2, 1.
  • pmms3c_check_000Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 0, 0, 0.
  • pmms3c_check_012Kernel check of the stored certificates for the 729 allocations that give chores 0, 1, 2 to agents 0, 1, 2.

Lean source view module on GitHub

/-- Certificate check: `w = i + 3 j + 9 T` with `T` a bitmask inside `X_i ∪ X_j` whose two parts both cost agent `i` strictly less than her own bundle. -/
def pmms3c_verify (σ : Fin 9 → Fin 3) (w : ℕ) : Bool :=
  let i := pmms3c_agent_of w
  let j := pmms3c_agent_of (w / 3)
  let m := w / 9
  decide (i ≠ j) &&
    (List.finRange 9).all (fun g => !(m.testBit g) || σ g == i || σ g == j) &&
    decide (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)
See it in the graphDiscuss this resultChallenge it