AFTD Auto-Formalizing Theoretical Domains

expected_chore_cost

def

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

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)
See it in the graphDiscuss this resultChallenge it