AFTD Auto-Formalizing Theoretical Domains

has_consistent_online_alpha_mms

deforiginal

Given ratio r and approximation factor α, there exists a consistent online allocator for two agents that, whenever each agent's cost for each chore is in {1, r} (not necessarily identical between the two agents), guarantees an α-MMS allocation after every prefix of every length.

Statement

def has_consistent_online_alpha_mms (r α : ℝ) : Prop
Related work
arXiv:2505.24321
Verified
12 Nov 2026
Axioms
none listed
Built on 2
  • is_consistent_online_allocatorA horizon-indexed family of two-agent allocation algorithms is a consistent online allocator if each alg m is an online allocator on m…
  • is_prefix_alpha_mms_choresAn allocation σ of m chores between two agents is α-MMS after every prefix if for every k with 1 ≤ k ≤ m, the restriction of σ to the…

Read back from the Lean

Given two real numbers $r$ and $\alpha$, the proposition asserts the existence of an allocation algorithm alg : (m : ℕ) → (Fin 2 → Fin m → ℝ) → Fin m → Fin 2 such that: 1. alg is a consistent online allocator: - For every $m \in \mathbb{N}$, alg m is online: for any two cost profiles $v, v' : \text{Fin } 2 \to \text{Fin } m \to \mathbb{R}$ and any chore $t \in \text{Fin } m$, if $v$ and $v'$ agree on all chores $s \le t$ for both agents, then alg m v t = alg m v' t. - alg is consistent across chore counts: for any $m_1, m_2 \in \mathbb{N}$ with $m_1 \le m_2$, any cost profile $c : \text{Fin } 2 \to \text{Fin } m_2 \to \mathbb{R}$, and any $t \in \text{Fin } m_1$, the chore $t$ is allocated to the same agent by alg m₁ on the restriction of $c$ to the first $m_1$ chores as it is by alg m₂ on $c$. 2. For every $m \in \mathbb{N}$ and every cost profile $c : \text{Fin } 2 \to \text{Fin } m \to \mathbb{R}$ such that every chore's cost to every agent is either $1$ or $r$ (i.e., $\forall i \in \text{Fin } 2, g \in \text{Fin } m, c(i, g) = 1 \lor c(i, g) = r$), the allocation produced by alg m c is prefix-$\alpha$-MMS for chores: - For every prefix length $k \in \mathbb{N}$ with $1 \le k \le m$, restricting the cost profile and the allocation to the first $k$ chores gives an $\alpha$-chore-MMS allocation: for each agent $i \in \text{Fin } 2$, the sum of costs of the chores among the first $k$ assigned to $i$ is at most $\alpha$ times the chore maximin share (MMS) of agent $i$ for those $k$ chores among 2 agents (where the chore MMS is the infimum over all 2-partitions of $\{0, \dots, k-1\}$ of the maximum bundle cost for agent $i$).

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

/-- Given ratio r and factor alpha, there exists a consistent online allocator guaranteeing alpha-MMS after every prefix for two agents with chore costs in {1, r}. -/
def has_consistent_online_alpha_mms (r α : ℝ) : Prop :=
  ∃ alg, is_consistent_online_allocator alg ∧
    ∀ (m : ℕ) (c : Fin 2 → Fin m → ℝ),
      (∀ i g, c i g = 1 ∨ c i g = r) →
      is_prefix_alpha_mms_chores m α c (alg m c)
See it in the graphDiscuss this resultChallenge it