RandomizedOnlineChoreAlgorithm
structure
A structure parameterized by the number of agents n : ℕ, consisting of three bundled fields: a sample space type Ω : Type, a probability mass function dist : PMF Ω, and a function rule : Ω → DeterministicOnlineChoreRule n assigning each sample to a deterministic decision rule.
Statement
structure RandomizedOnlineChoreAlgorithm (n : ℕ)- Defined in
- arXiv:2611.00432 Sec 2 & 4
- Verified
- 06 Nov 2026
- Axioms
- none listed
- Built on 1
- DeterministicOnlineChoreRuleA deterministic prediction-free online chore allocation algorithm for n agents with upgrade recourse: for each sequence of arrival costs…
- Used by 5
- 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…
- expected_chore_costThe expected cost of agent i : Fin n at horizon m : ℕ under a randomized online chore algorithm alg : RandomizedOnlineChoreAlgorithm n for…
- has_randomized_online_mms_barrier_breakerThere exists a strictly positive real ε > 0 and a randomized prediction-free online chore algorithm alg : RandomizedOnlineChoreAlgorithm n…
- deterministic_to_randomizedLifts a deterministic prediction-free online chore rule rule : DeterministicOnlineChoreRule n to a randomized online chore algorithm…
- 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
Given a natural number n (representing the number of agents), RandomizedOnlineChoreAlgorithm n is a structure consisting of:
1. A sample space Ω : Type,
2. A probability mass function dist : PMF Ω on Ω, and
3. A function rule : Ω → DeterministicOnlineChoreRule n mapping each sample ω : Ω to a deterministic online chore rule for n agents.
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
/-- A randomized prediction-free online chore allocation algorithm with upgrade recourse for n agents. -/ structure RandomizedOnlineChoreAlgorithm (n : ℕ) where Ω : Type dist : PMF Ω rule : Ω → DeterministicOnlineChoreRule n