DeterministicOnlineChoreRule
A deterministic prediction-free online chore allocation algorithm for n agents with upgrade recourse: for each sequence of arrival costs c, it outputs a sequence of allocations A m such that A m depends only on the chore costs before step m, and for any nonnegative arrival costs c, the sequence of allocations has upgrade recourse.
Statement
structure DeterministicOnlineChoreRule (n : ℕ)- Defined in
- arXiv:2611.00432 Sec 2 & 4
- Verified
- 06 Nov 2026
- Axioms
- none listed
- Built on 1
- has_upgrade_recourseAn online chore allocation sequence A : ∀ m : ℕ, Fin m → Fin n for n agents has upgrade recourse with respect to chore costs c : Fin n → ℕ…
- Used by 4
- 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…
- deterministic_to_randomizedLifts a deterministic prediction-free online chore rule rule : DeterministicOnlineChoreRule n to a randomized online chore algorithm…
- RandomizedOnlineChoreAlgorithmA structure parameterized by the number of agents n : ℕ, consisting of three bundled fields: a sample space type Ω : Type, a probability…
Read back from the Lean
The structure DeterministicOnlineChoreRule (n : ℕ) defines a deterministic online chore allocation rule for n agents with the following fields:
1. alloc: a function that takes a cost profile c : Fin n → ℕ → ℝ (giving the cost c i t to agent i for chore/item t) and produces, for each m : ℕ, an allocation alloc c m : Fin m → Fin n assigning each of the first m items to an agent.
2. prediction_free: the requirement that the allocation is online/non-anticipating: for every m : ℕ and all cost profiles c, c' : Fin n → ℕ → ℝ, if c i k = c' i k for all agents i : Fin n and all items k < m, then alloc c m = alloc c' m.
3. upgrade_recourse: the requirement that whenever costs are non-negative (for all i : Fin n and t : ℕ, c i t ≥ 0), the allocation rule satisfies has_upgrade_recourse n c (alloc c).
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 deterministic prediction-free online chore allocation algorithm with upgrade recourse for n agents. -/ structure DeterministicOnlineChoreRule (n : ℕ) where alloc : (Fin n → ℕ → ℝ) → (∀ m : ℕ, Fin m → Fin n) prediction_free : ∀ (m : ℕ) (c c' : Fin n → ℕ → ℝ), (∀ i, ∀ k < m, c i k = c' i k) → alloc c m = alloc c' m upgrade_recourse : ∀ (c : Fin n → ℕ → ℝ), (∀ i t, 0 ≤ c i t) → has_upgrade_recourse n c (alloc c)