AFTD Auto-Formalizing Theoretical Domains

is_ex_ante_proportional_chores

def

An allocation lottery p over allocations of m chores among n agents is ex-ante proportional for chore cost functions c if each agent i's expected cost under p is at most her proportional share (∑ e, c i e) / n.

Statement

def is_ex_ante_proportional_chores {m n : ℕ} (c : Fin n → Fin m → ℝ)
    (p : (Fin m → Fin n) → ℝ) : Prop
Defined in
arXiv:2611.04884, Section 2
Verified
04 Nov 2026
Axioms
none listed
Built on 2
  • 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.
  • additive_valuationThe additive valuation with item values u: a bundle is worth the sum of its items' values.
Used by 2

Read back from the Lean

For fixed natural numbers m and n, given a chore cost function c : Fin n → Fin m → ℝ and an assignment weight function p : (Fin m → Fin n) → ℝ, asserts that for every agent i : Fin n, the expected cost to agent i under p—defined as the sum over all allocations σ : Fin m → Fin n of p σ times the sum of c i j over all chores j assigned to i (where σ j = i)—is less than or equal to agent i's total cost of all m chores divided by n (as a real number).

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- An allocation lottery is ex-ante proportional for chores if each agent's expected cost is at most 1/n of her total cost. -/
def is_ex_ante_proportional_chores {m n : ℕ} (c : Fin n → Fin m → ℝ)
    (p : (Fin m → Fin n) → ℝ) : Prop :=
  ∀ i : Fin n, (∑ σ : Fin m → Fin n, p σ * additive_valuation (c i) (bundle_of σ i)) ≤
    (∑ e : Fin m, c i e) / (n : ℝ)
See it in the graphDiscuss this resultChallenge it