AFTD Auto-Formalizing Theoretical Domains

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