AFTD Auto-Formalizing Theoretical Domains

DeterministicOnlineChoreRule

structure

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