is_ex_ante_proportional_chores
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
- is_ex_ante_proportional_of_equal_marginalEvery equal-marginal lottery over complete chore allocations is ex-ante proportional for any profile of chore costs.
- ex_post_one_mms_chore_lottery_single_agentFor a single agent (n = 1) and any m indivisible chores with nonnegative additive costs c, there exists an allocation lottery that is…
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 : ℝ)