expected_chore_cost
The expected cost of agent i : Fin n at horizon m : ℕ under a randomized online chore algorithm alg : RandomizedOnlineChoreAlgorithm n for arrival costs c : Fin n → ℕ → ℝ, defined as the infinite sum over ω : alg.Ω of (alg.dist ω).toReal * additive_valuation (fun d => c i d.val) (bundle_of ((alg.rule ω).alloc c m) i).
Statement
noncomputable def expected_chore_cost {n : ℕ} (alg : RandomizedOnlineChoreAlgorithm n) (c : Fin n → ℕ → ℝ) (m : ℕ) (i : Fin n) : ℝ
- Defined in
- arXiv:2611.00432 Sec 2 & 4
- Verified
- 06 Nov 2026
- Axioms
- none listed
- Built on 4
- RandomizedOnlineChoreAlgorithmA structure parameterized by the number of agents n : ℕ, consisting of three bundled fields: a sample space type Ω : Type, a probability…
- DeterministicOnlineChoreRuleA deterministic prediction-free online chore allocation algorithm for n agents with upgrade recourse: for each sequence of arrival costs…
- 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 3
- op913_randomized_mms_barrier_under_upgrade_recourseOpen problem OP-913 (arXiv:2611.00432, after Thm 4.1): for every number of agents n ≥ 2, has_randomized_online_mms_barrier_breaker n…
- has_randomized_online_mms_barrier_breakerThere exists a strictly positive real ε > 0 and a randomized prediction-free online chore algorithm alg : RandomizedOnlineChoreAlgorithm n…
- randomized_mms_barrier_breaker_monoMonotonicity of the randomized MMS barrier guarantee: for any number of agents n : ℕ, real numbers ε' ≤ ε, and randomized online chore…
Read back from the Lean
expected_chore_cost alg c m i defines the expected chore cost incurred by agent i : Fin n among the first m chores under cost profile c : Fin n → ℕ → ℝ and randomized algorithm alg : RandomizedOnlineChoreAlgorithm n. It is defined as the infinite sum (tsum) over all sample outcomes ω : alg.Ω of the probability of ω ((alg.dist ω).toReal) multiplied by the additive valuation to agent i of the bundle of chores in Fin m allocated to i by (alg.rule ω).alloc c m.
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
/-- The expected cost of agent i under a randomized online chore algorithm at step m. -/ noncomputable def expected_chore_cost {n : ℕ} (alg : RandomizedOnlineChoreAlgorithm n) (c : Fin n → ℕ → ℝ) (m : ℕ) (i : Fin n) : ℝ := ∑' ω : alg.Ω, (alg.dist ω).toReal * additive_valuation (fun (d : Fin m) => c i d.val) (bundle_of ((alg.rule ω).alloc c m) i)