AFTD Auto-Formalizing Theoretical Domains

is_pmms_fair_chores

def

Pairwise maximin share (PMMS) for chores: allocation σ is PMMS for agent i if, for every other agent j and every way of splitting X_i ∪ X_j into two parts T and (X_i ∪ X_j) \ T, agent i's cost for her own bundle is at most her cost for the more costly of the two parts. Equivalently c_i(X_i) is at most the minimum over two-way splits of the larger part.

Statement

def is_pmms_fair_chores {m n : ℕ} (c : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) (i : Fin n) : Prop
Defined in
arXiv:2609.10493, Sec. 2 (pairwise maximin share for chores)
Verified
06 Oct 2026
Axioms
none listed
Built on 2
  • 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.
Used by 2
  • pmms3c_verify_soundIf the certificate check accepts w for allocation σ, then σ is not PMMS for agent w mod 3.
  • 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

/-- Pairwise MMS for chores with additive costs `c`: against every other agent `j`, agent `i`'s cost is at most the larger part of every split of `X_i ∪ X_j` in two, in `i`'s own costs. -/
def is_pmms_fair_chores {m n : ℕ} (c : Fin n → Fin m → ℝ) (σ : Fin m → Fin n) (i : Fin n) : Prop :=
  ∀ j, j ≠ i → ∀ T ⊆ bundle_of σ i ∪ bundle_of σ j,
    additive_valuation (c i) (bundle_of σ i) ≤
      max (additive_valuation (c i) T)
        (additive_valuation (c i) ((bundle_of σ i ∪ bundle_of σ j) \ T))
See it in the graphDiscuss this resultChallenge it